Implement a stack that pops out the most frequently added item.

Question

Anonymous · Accepted Answer

You could have a combination of two heaps: one indexed by value, and the other indexed by frequency of addition. Or a hash table and a heap, respectively. It depends on the applications and the balance between memory and processing time resources.

Noel C. · Answer

An additional comment: Nodes in the hash table and the heap must be shared (to save memory, and for convenience). Which means nodes should have links not only to their children, but their parents as well, so that rotations on the heap can be performed by lookup in the hashtable.

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches