This is solution for HackerRank Hash Tables: Ice Cream Parlor challenge, in python. This is a problem in the Interview Preparation Kit > Search Algorithms and is considered of medium difficulty.
The problem
The problem is simple: 2 friends want to buy ice cream and they must spend all their money each trip. some rules:
- Every flavor has a different value.
- They must choose the flavors (numbered) to sum up to money they have
- they can't buy the same flavor
- You need to return the index starting by 1 (not 0)
The naive solution
The naive solution is to traverse the entire set almost twice. Almost because for friend 2 we will traverse only the positions not chose yet
# inefficient, naive solution: O(n²)
def whatFlavors_inneficient(cost, money):
for i1, c1 in enumerate(cost, 1):
for i2, c2 in enumerate(cost[i1:], i1 + 1):
if (c1 + c2) == money:
print(i1, i2)
return
The final solution
In the final solution, we must trade time for space, creating a dictionary. The reason is to find, after we spend the money on the first ice cream, if there is another flavor to sum up to the money we got there.
# cost: [1, 4, 5, 3, 2]
dcost = dict(enumerate([c for c in cost], 1))
# {1: 1, 2: 4, 3: 5, 4: 3, 5: 2}
dcost = {v: k for k, v in dcost.items()}
# {1: 1, 4: 2, 5: 3, 3: 4, 2: 5}
So, we still need to traverse all the flavors, but just once.
The complete solution is as follows
def whatFlavors(cost, money):
# inverted (v,k) dictionary of costs
# to find easily the value that complements the first iteration
dcost = dict(enumerate([c for c in cost], 1))
dcost = {v: k for k, v in dcost.items()}
# traverse once
for i1, c1 in enumerate(cost, 1):
# the cost of second ice cream must be
c2 = money - c1
i2 = dcost.get(c2)
# if found, return
if i2 and (i2 != i1):
print(i1, i2)
return
Top comments (0)