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

  • DagnyT + 1 comment

    @Dan_Golding

    I just ran a small test to check if the Map[cost] to FlavorIdx approach has a bug in it. It does. This is why Gayle's YouTube video uses BinarySearch on Cost entries ordered by FlavorIdx.

    In this test sequence; the Flavor at position 2 overwrites/loses the flavor at position 1.

    What's interesting though; is that this test case appears to be missing from the Hacker Rank test suite; because this Map[cost] code approach was passing all of their test suite.

    Here's my Python code (formatted on next comment):

    • DagnyT + 1 comment
      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)
      • Dan_Golding + 1 comment

        The problem specifies that there will only be one unique solution. Your test case has three valid solutions (i.e. (0,2), (1,2) and (3,4)) and so it is not a valid test case for the problem defined.

        • MisterTB + 0 comments

          i agree, undefined in case there are 3 (or more) similar costs.