Java Dequeue

It is a relatively warm day in the Twin Cities of Minneapolis and St. Paul. My son tweeted an hour or so ago that the temperature by his place was 46F. Not a day to wear swim trunks and T-shirts but a very welcomed change.

I was going to clean up the code for this post but I have a Docker webinar to watch soon.

The subject for this post is the Java Dequeue (https://www.hackerrank.com/challenges/java-dequeue/problem) challenge from HackerRank. It is a mix of double ended (doubly linked) queue and hash map.

The idea is to insert a set of n integers in a queue and then take m at a time to process. In other words, we need to set a window of m integers and check. On each pass we move the window once and check again. We repeat until all windows of m numbers have been covered. When done we display the sum of windows that hold all different numbers. The actual challenge seems to do a good job describing the requirements. There is only a single test example.

A screen capture of the program running the sample test case follows:

6 3
5 3 5 2 3 2

3

Following is the provided scaffolding code to run and test the software:

	/*
	 * 
	 */
	public static void main(String[] args) {

		 Scanner in = new Scanner(System.in);
         Deque<Integer> deque = new ArrayDeque<Integer>();
         
         int n = in.nextInt();
         int m = in.nextInt();

//         System.out.println("n: " + n + " m: " + m);
         
         // **** ****
         for (int i = 0; i < n; i++) {
        	 int num = in.nextInt();
        	 
//        	 System.out.println("num: " + num);
        	 
        	 deque.addLast(num);
         }
         
//         System.out.println("deque: " + deque.toString());
         
         // **** ****
         System.out.println(maxUnique(n, m, deque));
         
         // **** ****
         in.close();
	}

Finally the maxUnique() function follows:

	/*
	 * 
	 */
	static int maxUnique(int n, int m, Deque<Integer> deque) {
		
		int globalMax = 0;
		
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		
//		// ???? ????
//		int first 	= deque.getFirst();
//		int last 	= deque.getLast();
//		System.out.println("first: " + first + " last: " + last);
//		System.out.println("deque.size: " + deque.size());
		
		// **** set deque first iterator ****
		Iterator<Integer> dqfit = deque.iterator();
		
		// **** set deque second iterator ****
		Iterator<Integer> dqsit = deque.iterator();
		
		// **** load the initial hash map with m elements ****
		for (int i = 0; i < m; i++) {
			
			// **** get the next key from the queue ****
			int key = (int)dqfit.next();

			// **** load hash map ****
			if (hm.containsKey(key)) {
				int count = hm.get(key);
				hm.put(key, ++count);
			} else {
				hm.put(key, 1);
			}
		}
//		System.out.println("hm: " + hm.toString());
//		System.out.println();
		
		// **** loop processing the queue ****
		for (int i = 0; i < deque.size() - m + 1; i++) { // System.out.println("i: " + i); // **** get the current max **** int max = hm.size(); // System.out.println("max: " + max); // **** update the global max **** if (max > globalMax)
				globalMax = max;
//			System.out.println("globalMax: " + globalMax);

			// **** check if we are done ****
			if (i >= deque.size() - m)
				continue;

			// **** get the next key from the queue ****
			int key = (int)dqsit.next();
//			System.out.println("key: " + key);

			// **** remove this key,value entry from the hash map ****
			int value = hm.get(key);
			if (value == 1) {
				hm.remove(key);
			} else {
				hm.put(key, --value);
			}
//			System.out.println("hm: " + hm.toString());

			// **** get the next key from the queue ****
			key = (int)dqfit.next();
//			System.out.println("key: " + key);
			
			// **** add this key to the hash map ****
			if (hm.containsKey(key)) {
				int count = hm.get(key);
				hm.put(key, ++count);
			} else {
				hm.put(key, 1);
			}
//			System.out.println("hm: " + hm.toString() + "\n");
		}

		// **** ****
		return globalMax;
	}

In this solution I decided to use the suggested queue, a hash map used to decide if all numbers in a window are unique, and two iterators. I used an Iterator to move in front of the window and a second one to move behind it.  All this was prompted by the note which specifies an execution time limit of 3 seconds.

If interested, my entire solution generated in the Eclipse IDE can be found in my GitHub repository.

If you have comments or questions regarding this or any other post in this blog, or if you have software development needs, please do not hesitate and leave me a note below. Requests for assistance will be kept confidential.

Keep on reading and practicing, which is the only way to learn.

Enjoy;

John

Follow me on Twitter:  @john_canessa