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

2 thoughts on “Ice Cream Parlor – Part II”

  1. Good posts. Would be nice, if you would link at the end of the previous part the following part. That would simplify switching between the content. Your content is great, very interesting, keep going!
    Regards, Lasse Schultebraucks

Leave a Reply

Your email address will not be published. Required fields are marked *

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