Ice Cream Parlor – Part II

I decided to try a different approach for a solution to the Binary Search: Ice Cream Parlor HackerRank challenge. On this pass I am using the HashMultimap class from Guava by Google.

Following is a screen capture of the Eclipse IDE console using the third test case:

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
0 468
196 718
292 1236
539 935
20 263
30 107
3 94
425 484
0 550
219 656
133 242
0 244
317 338
207 485
63 64
13 206
0 388
654 972
205 275
0 195
471 633
371 393
25 170
64 521
28 78
949 1590
1 1043
636 773
0 136
6 47
81 288
274 983

My entire Java code which includes the methods and classes for the binary search and the hash map approaches follows:

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

// **** Google Guava ****

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) {
		int firstPrice 	= 0;
		int secondPrice = 0;
		
		// **** could have load multimap in main :o( ****
		
		Multimap<Integer, Integer> multiMap = HashMultimap.create();
		for (Entry<Integer, Integer> entry : iceCreams.entrySet()) {
			multiMap.put(entry.getValue(), entry.getKey());
		}
		
		// **** traverse list of ice creams ****
		
		for (int firstFlavor = 0; firstFlavor < iceCreams.size(); firstFlavor++) {
			
			// **** get price of current ice cream ****
			
			firstPrice = iceCreams.get(firstFlavor);
		
			// **** compute second price of ice cream ****
			
			secondPrice = money - firstPrice;
			if (secondPrice < 0) {
				continue;
			}
			
			// **** look for the second price in the multiMap ****
			
			if (multiMap.containsKey(secondPrice)) {
										
				// **** get index of the second flavor ****
				
				if (multiMap.containsKey(secondPrice)) {
					
					// **** ****
					
					Collection<Integer> flavors = multiMap.get(secondPrice);
					
					// **** ****
					
					int[] flavorArr = new int[flavors.size()];
					int i = 0;
					for (Integer p : flavors) {
						flavorArr[i++] = p;
					}

					// **** sort the array of flavors ****
					
					Arrays.sort(flavorArr);
										
					// **** select the second flavor ****
					
					int secondFlavor = -1;
					for (int f : flavorArr) {
						if (f != firstFlavor) {
							secondFlavor = f;
							break;
						}
					}
					
					// **** display flavors in specified order (smaller & larger) ****
										
					if (firstFlavor < secondFlavor) {
						System.out.println((firstFlavor + 1) + " " + (secondFlavor + 1));
					} else {
						System.out.println((secondFlavor + 1) + " " + (firstFlavor + 1));					
					}
					
					// **** we are done ****
					
					return;
				}
			}
		}
	}
		
	/**
	 * Solution approach selections.
	 */
	static enum Approach {
		BinarySearch,
		HashMapSearch
	}

	/**
	 * Test code.
	 */
	public static void main(String[] args) {
		
		// **** select approach to use ****
		
		Approach approach = Approach.HashMapSearch;
		
		// **** 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();
	}

}

If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will replay as soon as possible and will not use your name unless you allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa