Most Frequent IDs

Most Frequent IDs

What is this problem about?

The Most Frequent IDs problem gives you a sequence of events where each event adds or removes an ID from a collection. After each event, report the ID that has appeared most frequently so far. This Most Frequent IDs coding problem requires maintaining a dynamic frequency count with an efficient maximum query. The combination of a hash map and a max-heap or ordered set is the natural solution.

Why is this asked in interviews?

Amazon and Bloomberg ask this to test real-time frequency tracking with efficient maximum retrieval. It validates knowledge of ordered data structures (heaps or TreeMap) for maintaining a dynamic maximum. The array, hash table, ordered set, and heap interview pattern is the core, and the challenge of handling deletions and lazy updates makes this more nuanced than standard frequency problems.

Algorithmic pattern used

Hash map + max-heap with lazy deletion. Maintain freq[id] = current frequency of each ID. Use a max-heap of (frequency, id) pairs. When frequency updates, push the new (freq, id) to the heap. When querying max, pop from the heap until the top entry matches the current frequency in the hash map (lazy deletion of stale entries). Return the current max ID.

Example explanation

Events: [("add", 1), ("add", 2), ("add", 1), ("remove", 2), ("add", 3)].

• After "add 1": freq={1:1}. Max ID = 1.
• After "add 2": freq={1:1,2:1}. Tie → return smaller = 1 (or by problem convention).
• After "add 1": freq={1:2,2:1}. Max ID = 1 (freq 2).
• After "remove 2": freq={1:2,2:0}. Max ID = 1.
• After "add 3": freq={1:2,3:1}. Max ID = 1.

Common mistakes candidates make

• Not handling lazy deletion in the heap (stale entries give wrong max).
• Removing IDs from the heap directly (heaps don't support efficient deletion).
• Not handling tie-breaking correctly between IDs with equal frequency.
• Decrementing frequency below 0 for IDs not in the collection.

Interview preparation tip

Dynamic maximum problems where frequencies change require lazy deletion heaps. The pattern: push updates to the heap without removing old entries; when querying, skip stale entries (where heap top doesn't match current hash map value). Practice lazy deletion on heaps — it's the most common heap optimization technique in dynamic frequency problems and appears frequently in streaming data interview questions at Bloomberg and Amazon.