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