We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Hash Tables: Ice Cream Parlor
  5. Discussions

Hash Tables: Ice Cream Parlor

  • zoomis_gogo + 6 comments

    I didn't use binary search tree but use dictionary for memory. Here is my Python code

    t = int(raw_input().strip())
for a0 in xrange(t):
    m = int(raw_input().strip())
    n = int(raw_input().strip())
    a = map(int, raw_input().strip().split(' '))

    # find matched number
    cost_map = {}
    for i, cost in enumerate(a):
        sunny = cost
        johnny = m - cost
        if johnny in cost_map.keys():
            print cost_map[johnny]+1, i+1
        else:
            cost_map[cost] = i
    • SidSethi + 0 comments
      [deleted]
    • danrl + 1 comment

      Mine looks similar but I chose Python3. It should work for many "find pair of sum" problems, not just this special problem.

      hs = { }
    for i in range(len(a)):
        if a[i] in hs:
            print(hs[a[i]], i + 1)
            break
        hs[m - a[i]] = i + 1
    • DagnyT + 0 comments

      Hi @zoomis_gogo!

      Your code here looks very clean, and it passes all of the HackerRank test suite for this problem.

      However, when I tested a couple cases to understand why Gayle would use BinarySearch for this problem; I found a bug in this Map approach. I believe this test could be helpful to add to the Hacker Rank suite to align with the original Problem as stated by Gayle:

      def find_matched_flavors(m, a):
    print "TOTAL MONEY is:  {0}".format(m)
    cost_map = {}
    for i, cost in enumerate(a):
        print "(i, cost) is ({0},{1})".format(i, cost)
        sunny = cost
        johnny = m - cost
        print "prior cost_map {0}".format(cost_map)
        print "johnny, sunny {0}, {1}".format(johnny, sunny)
        if johnny in cost_map.keys():
            print "FOUND MATCHED FLAVORS IN ORDER OFFSET +1:"
            print cost_map[johnny]+1, i+1
        # BUGFIXED:  following else blocks add of NEW cost:flavorIdx if complement already found pre-loaded
        # else:
        # BUG-UNFIXED:  following with OVERWRITE-LOSE prior flavor with cost duplicating CURRENT flavor cost!
        #               eg. (5, 0) gets overwritten with (5, 1)
        #               i.e. complement must be found on FIRST cost map entry; otherwise we lose all history of
        #               that entry when a duplicate cost entry is added!
        cost_map[cost] = i
        print "updated cost_map {0}".format(cost_map)
  
# MY TEST SCRIPT 

m = 8
flavorsToCost = [5, 5, 3, 4, 4]
find_matched_flavors(m, flavorsToCost)
    • eranhare + 4 comments

      I've got the same algorithm implemented in C# but got runtime error when submitting it. I tried using either a Dictionary or my own array, but failed with both. Any idea what could cause that problem?

      • s_zeno + 0 comments

        I got the same problem.

      • hackrank10 + 0 comments

        Same here! Checked my code in LINQPad and it runs fine. Runtime error in HR.

      • edvardpitka + 3 comments

        you need to trim input :(

        int[] arr = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), arrTemp => Convert.ToInt32(arrTemp));

        • eellor + 0 comments

          I wasted an hour just to figure out this "Trim()" issue, obviously at least twice of the time taken to write the actual code.

          The problem is, the bug is in the predefined part of the code! I wish HackerRank can have the predefined section refined more, or they shall not provide it at all. Also the test data itself is buggy. It shall not have the trailing whitespace though it is really common in the real world.

        • alexcucul08 + 0 comments

          Yep, I have seen this issue also. When I copied the code locally in a new project and I also copied one of the test cases, the lines containing the array contained empty spaces at the end. So I have erased those lines at the end and it worked fine. But with a "buggy" input from hacker rank, there is no other option but to trim the input :-). At least we figured it out :-).

        • amandal1810 + 1 comment

          this comment saved my day. Spent over 30 mins only debugging. :(

          • sebagomez + 0 comments

            30 mins? I've been running my code for 2 f*cking hours trying to figure out where the problem in my code was

      • tallapudi + 0 comments

        Same here in Kotlin. Calling trim() on cost array solved the issue.

    • ga_bar + 0 comments
      [deleted]
    • woldegebrielkeb1 + 2 comments

      here is my java solution. short and sweet. 

       static void whatFlavors(int[] cost, int money) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(money-cost[0],1);
        for(int i=1; i<cost.length; i++) {
            if(map.containsKey(cost[i])) {
                System.out.println(map.get(cost[i])+" "+(i+1));
                break;
            }
            else if(!map.containsKey(cost[i])&&money-cost[i]>0) {
                map.put(money-cost[i], i+1);
            }
        }

    }
      • falkun2 + 0 comments

        Same solution - even shorter 

         static void whatFlavors(int[] costs, int money) {
    Map<Integer, Integer> values = new HashMap();
    for (int i = 0; i < costs.length; i++) {
        if (values.keySet().contains(money - costs[i])) {
            System.out.println(String.format("%s %s", values.get(money - costs[i]), i+1));
            break;
        }
        values.put(costs[i], i+1);
    }
}
      • jojos + 0 comments

        Some of your statements can be omitted, namely the initial put in the map and the second check if the map does not contain the key, like so:

        static void whatFlavors(int[] cost, int money) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0; i<cost.length; i++) {
        if(map.containsKey(cost[i])) {
            System.out.println(map.get(cost[i])+" "+(i+1));
            break;
        }
        else map.put(money-cost[i], i+1);
    }
}