A support desk pushes the product id of every incoming complaint onto a pile. When an engineer frees up, they take a complaint about whichever product currently has the most complaints on the pile. If several products are tied, they take the one whose complaint is nearest the top of the pile (the most recently pushed among the tied ones).
Write a class FrequencyStack:
FrequencyStack()creates an empty pile.push(x)pushes the valuex.pop()removes one copy of the value that occurs most often and returns it. On a tie, it removes the copy closest to the top.
pop is only called when the pile is non-empty.
s = FrequencyStack()
for x in [4, 8, 4, 6, 8, 4]:
s.push(x)
s.pop() # 4 (4 appears three times)
s.pop() # 8 (4 and 8 both appear twice; the top-most of them is an 8)
s.pop() # 4 (4: 2 copies, 8 and 6: 1 each)
s.pop() # 6 (all tied at 1; the pile is now 4, 8, 6 from bottom to top)
s.pop() # 8
s.pop() # 4
Constraints: up to 2 * 10^5 calls in total; values are in [-10^9, 10^9].
Scanning the pile on every pop is O(n) per call and too slow. Aim for O(1) per call.
Show hint
think of the pile as layers: the first copy of each value goes to layer 1, the second copy to layer 2, and so on. Each layer is itself a pile in push order, and the answer always lives on top of the highest non-empty layer.