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

Question

Sigiloso · 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

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas