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.
  1. Hash Tables: Ice Cream Parlor
  2. Discussions

Hash Tables: Ice Cream Parlor

  • Dan_Golding
     + 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