Monday, January 14, 2013

[Google Interview] Query the most frequent element

Design a data structure which supports the below operation
Insertion of an integer
Deletion removes the element with highest frequency at that instant. In case of tie, go by the FIFO startegy.

For e.g

Insert 5,6,5,7,5,7
1st removal -- 5,6,5.7,7
2nd removal -- 5,6,5,7,
3rd removal -- 5,6,7
and so on

Perform both the operations in O(1).