Pinterest Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Algo:
Store <pinId, IntegerCount> in a Map.
On every 'like' update the respective count for corresponding pinId. O(1) for update
On every page request, scan the list to obtain 'Top 50'. O(N) to scan for top 50 (use LRU concept to weed out min)
Smarter: As opposed to on every page req and to save on processing, update the top 50 list every N minutes
Create a max heap of 50 elements. Also keep a hash for all the elements. Updating the element will take O(1) time. Now once the heap is build, updating the elements or replacing will take constant time.
I'll maintain top_50_list = []
top_50_list has (score, id) tuple with min score.
e.g. top_50_list = [(888, 12), (992, 28381), ..., (823, 1293)]
min_score = 823
you can make it O(N). N = 10M
Whenever score update happen, this logic
def update(id, score):
if score < min_score:
return
if id in top_k_list: # somehow
# find index i
top_k_list[i] = (score, id)
else:
# delete min_score element
top_k_list.append((score, id))
min_score = min([score for score, id in top_k_list])
Use a hashtable to store the pin_id <-> score mappings.
- Anonymous February 24, 2013Maintain a min heap of the top 50 pins with the highest scores.
Whenever the score of a pin is updated, compare with the score at the root of the heap. If more, pop out the root and push the new pin into the heap.