Ice Cream Parlor – Part I

Decided to take a stab at “Binary Search: Ice Cream Parlor” challenge in Hacker Rank. If interested you can get the requirements at the following URL:  https://www.hackerrank.com/challenges/ctci-ice-cream-parlor

The general idea is to solve the sum of two numbers. I will address more on the subject of sum of two numbers on the second part of this post.

It is nice that Hacker Rank has been putting links to short videos with some challenges. In this case there is a video on Binary Search by Gayle Laakmann McDowell author of “Cracking the Coding Interview”. I watched the video. It was simple and to the point. Gayle covers the subject with an implementation using a recursive approach which she then converts to a loop implementation.

I am running on a DELL machine with dual processors and multiple cores with 24 GBs of RAM running Windows 10.

Take a look at the following set of screen captures from the console of the Eclipse IDE:

main <<< N: 10000
main <<< N: 10000
main <<< LOOPS: 7
main <<<      loop duration:   746826 ns
main <<< recursive duration:  1618770 ns

main <<< N: 11000
main <<< N: 11000
main <<< LOOPS: 7
main <<<      loop duration:   831038 ns
main <<< recursive duration:  1305024 ns

main <<< N: 12000
main <<< N: 12000
main <<< LOOPS: 7
main <<<      loop duration:   981174 ns
main <<< recursive duration:  1794888 ns

main <<< N: 13000
main <<< N: 13000
main <<< LOOPS: 7
main <<<      loop duration:   845474 ns
main <<< recursive duration:  2586949 ns

main <<< N: 14000
main <<< N: 14000
main <<< LOOPS: 7
main <<<      loop duration:   929685 ns
main <<< recursive duration:  2802527 ns

main <<< N: 15000
main <<< N: 15000
main <<< LOOPS: 7
Exception in thread "main" java.lang.StackOverflowError
	at Solution.recursiveCount(Solution.java:32)
	::::::::::::
	at Solution.recursiveCount(Solution.java:32)

Please note that the recursive approach seems to take longer than the loop one. No big deal, the requirements for no more than 10^4 == 10,000 on all parameters :o)

That said, as we increased the number to be decremented (N) from 10,000 to 14,000 all was well. When we tried 15,000 the program crashed with a stack overflow exception. It seems that it is always best to use the loop implementation than a recursive approach.  The stack overflow exception was an extreme case and would not have been encountered with this challenge due to the fact that the bounds were set to 10,000. If you have multiple implementations of a recursive algorithm running on the same machine, additional number of resources (time and memory) will be consumed by the recursive implementation.

I spent a few years working developing software on custom and real-time hardware. I do not recall ever implementing an algorithm using recursion. Resources are quite scarce. This is also the case when implementing software for products on the IoT.

On a separate note, the Binary Search approach does not seem to fit in a solution for the problem at hand. That said; this seems to happen on occasions with challenges on this and other web sites. It makes you take the time to refresh, try and solve the challenge in at least two different ways; the suggested and the best approach.

You probably have seen the challenge that requires you to split a sentence of a number of words and convert them to upper or lower case not using the String.split() method. As an exercise on states it seems to work. In practice you might never find such a requirement. One way or the other you hopefully have the chance to refresh existing concepts and perhaps learn something new.

If you read the discussions and implementations more than one person brought up the use of Binary Search for the challenge at hand. I also thought it was not at the core of the problem. That said, I spent time and getting my code in Java to be accepted as a solution.

One more thing before I get to the actual challenge. The challenge has three test cases. My first approach passed the first two. Before switching it I wanted to understand how a single test case could fail. The issue was not a timeout but a wrong answer. Because of that I purchased the test case and the expected output. This was a first for me. I noticed that the test case was a set of 50 test cases. My code was working but it was just slow enough to fail on the last set.

I speculated that getting to the second flavor using a sequential approach was too slow. I gave up and decided to modify the main() method of the solution. Apparently more than one person did that. It was for me a first time to alter the code in main().

I did enjoy the challenge. It made me think I was missing something.

Following is the console output using the test samples and two additional test cases:

4
4
5
1 4 5 3 2
4
4
2 2 4 3
16
7
2 7 8 5 8 3 8
16
21
1 1 1 1 1 1 1 1 1 1 1 1 10000 10000 5 3 10000 8 1 8 8
1 4
1 2
3 5
18 20

Following is the run with the test case #3 that I purchased from HackerRank (not sure how many Hackos had to change hands):

2 3
1 4
4 5
29 46
11 56
84 240
413 584
28 80
380 633
190 242
450 667
7 126
208 636
301 831
243 649
258 429
18 49
7 32
750 965
196 718
292 1236
539 935
20 263
30 107
3 94
425 484
623 923
219 656
133 242
691 800
317 338
207 485
63 64
13 206
407 421
654 972
205 275
499 883
471 633
371 393
25 170
64 521
28 78
949 1590
1 1043
636 773
240 908
6 47
81 288
274 983

Following is the complete code for my solution in Java:

import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map.Entry;
import java.util.Scanner;

import com.google.common.collect.HashMultimap;
import com.google.common.collect.Multimap;

class IceCream implements Comparable<IceCream> {
	
	// **** members ****
	
	int price;
	int index;
	
	/**
	 * Constructor
	 */
	public IceCream(int price, int index) {
		this.price = price;
		this.index = index;
	}

	/**
	 * Comparator.
	 */
	public int compareTo(final IceCream ic) {
		return  Integer.compare(this.price, ic.price);
	}
}

public class Solution {

	/**
	 * Binary search.
	 */
	static int binSearch(int price, IceCream[] iceCreams) {
		int lo = 0;
		int hi = iceCreams.length - 1;
		
		// **** ****
		
		while (lo <= hi) {

			// **** compute mid point ****
			
			int mid = lo + (hi - lo) / 2;
			
			// **** update hi limit ****
			
			if (price < iceCreams[mid].price) { hi = mid - 1; } // **** update lo limit **** else if (price > iceCreams[mid].price) {
				lo = mid + 1;
			}
			
			// **** found price ****
			
			else {
				return mid;
			}
		}
		
		// **** price NOT found ****
		
		return -1;
	}
	
	/**
	 * Select and print the two flavors using binary search.
	 */
	static void selectFlavors(int money, IceCream[] iceCreams) {
		int firstPrice 	= 0;
		int secondPrice	= 0;

		// **** sort array of ice cream ****
		
		Arrays.sort(iceCreams);

		// **** traverse the price array looking for two entries that add to money ****

		for (int i = 0; i < iceCreams.length; i++) { // **** first price (from prices array) **** firstPrice = iceCreams[i].price; // **** check if price is too high for the money we have **** if (firstPrice >= money) {
				continue;
			}		

			// **** compute the second price ****
			
			secondPrice = money - firstPrice;

			// **** look up second ice cream ****

			int mid = binSearch(secondPrice, iceCreams);
			
			// **** look for the second price index and print solution (if needed) ****

			if (mid != -1) {
				
				// **** adjust mid (if needed) ****
				
				if (i == mid) {
					mid++;
				}
				
				// **** print result in order ****
				
				if (iceCreams[i].index < iceCreams[mid].index) {
					System.out.println((iceCreams[i].index + 1) + " " + (iceCreams[mid].index + 1));
				} else {
					System.out.println((iceCreams[mid].index + 1) + " " + (iceCreams[i].index + 1));					
				}
				
				// **** all done ****
				
				break;
			}
		}
	}
	
	/**
	 * Select and print two flavors using Guava's HashMultimap instead of binary search.
	 * !!! WORK IN PROGRESS !!!
	 */
	static void getFlavors(int money, LinkedHashMap<Integer, Integer> iceCreams) {
		
		System.out.println("getFlavors <<< iceCreams: " + iceCreams);
		
		
		Multimap<Integer, Integer> multiMap = HashMultimap.create();
		
		for (Entry<Integer, Integer> entry : iceCreams.entrySet()) {
		  multiMap.put(entry.getValue(), entry.getKey());
		}
		System.out.println();	
		
		for (Entry<Integer, Collection<Integer>> entry : multiMap.asMap().entrySet()) {
			  System.out.println("Original value: " + entry.getKey() + " was mapped to keys: "
			      + entry.getValue());
			}
	}
	
	/**
	 * Solution approach selections.
	 */
	static enum Approach {
		BinarySearch,
		HashMapSearch
	}

	/**
	 * Test code.
	 */
	public static void main(String[] args) {
		
		// **** select approach to use ****
		
		Approach approach = Approach.BinarySearch;
		
		// **** open scanner ****
		
		Scanner in = new Scanner(System.in);
		
		// **** number of test cases ****
		
        int t = in.nextInt();
        
        // **** loop once per test ****
        
        for(int a0 = 0; a0 < t; a0++) {
        	
        	// **** money ****
        	
            int m = in.nextInt();
            
            // **** number of flavors ****
            
            int n = in.nextInt();            

            // **** select approach ****
            
            switch (approach) {
            case BinarySearch:
                IceCream a[] = new IceCream[n];
        	
                // **** loop loading flavors ****
                
                 for(int a_i=0; a_i < n; a_i++){
                    a[a_i] = new IceCream(in.nextInt(), a_i);
                }

                // **** select and print flavors ****

                selectFlavors(m, a);
            	break;
            	
            case HashMapSearch:
            	LinkedHashMap<Integer, Integer> iceCreams = new LinkedHashMap<Integer, Integer>();
            	
            	// **** loop loading flavors ****
            	
                for(int flavor = 0; flavor < n; flavor++){
                	iceCreams.put(flavor, in.nextInt());
                }

                // **** select and print flavor ****
            	
                getFlavors(m, iceCreams);
            	break;
            }
        }
        
        // **** close scanner ****
        
        in.close();
	}

}

I was planning on have the second approach completed this morning but I was working on this post and cooking :o) Hope the food turns out delicious.

If you have a comment regarding this or any other post please do not hesitate and send me a message. I will replay and will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.