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
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
Thanks for the suggestion. Will do moving forward.
Regards; John