Learn-dsa..in 30 days!



























CC-16 : : Find first unique integer in a stream.

Description:

Given a stream of integers, process the same one by one and find first unique integer from the already processed integers.

Test cases and expected outputs:

Input Parameters Expected outputs
QueueFirstUnique queue=new QueueFirstUnique();
System.out.println("Add 2");
queue.addToUniQueue(2);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 3");
queue.addToUniQueue(3);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 5");
queue.addToUniQueue(5);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 2");
queue.addToUniQueue(2);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 3");
queue.addToUniQueue(3);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 5");
queue.addToUniQueue(5);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 7");
queue.addToUniQueue(7);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 7");
queue.addToUniQueue(7);
System.out.println("First Unique:"+queue.getFirstUnique());
System.out.print("Add 9");
queue.addToUniQueue(9);
System.out.println("\nFirst Unique: "+queue.getFirstUnique()); 		Add 2
First Unique: 2
Add 3
First Unique: 2
Add 5
First Unique: 2
Add 2
First Unique: 3
Add 3
First Unique: 5
Add 5
First Unique: -2147483648
Add 7
First Unique: 7
Add 7
First Unique: -2147483648
Add 9
First Unique: 9

Note: -2147483648 indicates no unique integer exists in the stream.

Pseudocode:

Declare and initialize a HashMap to hold frequencies of occurrence of data elements in the input stream of integers.
Declare and initialize a Queue to unique integers found in the input stream of integers.
addtoUniQueue() method:
If the current element does not exist in the HashMap, add it to HashMap with frequency of 1, else increment its current frequency by 1.
If frequency of current integer is 1, it means it is unique number found so far, so add it to Queue holding unique numbers.
getFirstUnique() method:
While Queue holding unique numbers is not empty and the current element from Queue holding unique numbers is non unique (check this using HashMap holding frequencies of numbers), remove the number from the queue.
When above while loop completes and Queue size is non zero then the first number in the queue is the first unique number in the Queue. If the Queue size is 0 after above while loop, that means there is no current first unique number in the Queue.

Code:

public class QueueFirstUnique {
	
private Queue< Integer > uniQueue=new LinkedList< Integer >();

private HashMap< Integer, Integer > cnts=new HashMap< Integer, Integer >();

public void addToUniQueue(int data) {
	cnts.put(data, cnts.getOrDefault(data,0)+1);
	if (cnts.getOrDefault(data,0)==1) {
		uniQueue.add(data);
	}
}

public int getFirstUnique() {
	while ((uniQueue.size() > 0) && ( cnts.getOrDefault(uniQueue.element(),0) > 1)) {
		uniQueue.remove();
	}
	if (uniQueue.size() > 0) {
		return uniQueue.element();
	} else {
		return Integer.MIN_VALUE;
	}
	
}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us