Discussion on Hash Tables: Ice Cream Parlor Challenge

Dan_Golding 2 years ago+ 3 comments

That's not a problem. For each value, check if the compliment is in the keys of the map. If it is then you've found your pair, duplicate or not. If it isn't then add the cost of the flavour to the map. O(n) and you don't need any special consideration for the case when the answer is two ice creams with the ame cost. Example in Python3:

def get_flavours(money,flavours):
    map = {}
    for pos in range(len(flavours)):
        cost = flavours[pos]
        compliment = money - cost
        if compliment in map:
            return (flavours.index(compliment) + 1, pos + 1)
        else:
            map[cost] = compliment

or even

def get_flavours(money,flavours):
    map = {}
    for pos, cost in enumerate(flavours):
        if cost in map:
            return (map[cost], pos + 1)
        else:
            map[money-cost] = pos + 1

DagnyT 2 years ago+ 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 2 years ago+ 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 2 years ago+ 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 2 years ago+ 0 comments

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

karanj54321 11 months ago+ 0 comments

def solve(flavours, money):
    map = {}
    for pos, cost in enumerate(flavours):
        compliment = money - cost
        if compliment in map:
            return (map[compliment], pos + 1)   #map[compliment] is index of cost of flavor complimentary to current cost | pos+1 is index of current cost 
        else:
            map[cost] = pos + 1 # adding index of current cost to map

billchenxi 8 months ago+ 0 comments

The first one should have used a list instead of dictionary:

def whatFlavors(cost, money):
    map = []
    for pos in range(len(cost)):
        f1 = cost[pos]
        f2 = money - f1
        if f2 in map:
            # print(f2)
            print(cost.index(f2) + 1, pos + 1)
        else:
            map.append(f1)  
        #print(map)