Most Frequent IDs
Asked at Snowflake
Problem
Most Frequent IDs processes a stream of updates (id, delta) that add or remove copies of an ID, and after each update asks for the count of the most frequent ID (0 if the collection is empty). You need a structure that returns a maximum while counts go up and down — a max-heap with lazy deletion, or an ordered multiset of counts.
Asked At
| Company | Difficulty | |
|---|---|---|
| Snowflake | Medium | View all Snowflake questions → |
How to Think About It
Keep a hash map count[id]. Scanning it for the maximum after every step is O(n) per step.
Key insight: push (count, id) onto a max-heap every time an ID's count changes. Old entries become stale, but you can detect them: an entry is valid only if its count equals the current count[id].
After each update, pop stale entries from the top until the top is valid (or the heap is empty). The top is then the answer.
Ordered-set alternative: maintain a multiset (or a map from count to how many IDs have it) and read its largest key.
Counts can reach 10^5 * 10^5 = 10^10, so use 64-bit integers.
Optimal Approach
Step 1: count = {}, heap = [], res = [].
Step 2: For each (id, delta):
count[id] += delta; push (-count[id], id).
While the top (c, i) has -c != count[i]: pop.
Append -heap[0][0] if the heap is non-empty, else 0.
Step 3: Return res.
Time: O(n log n). Space: O(n).
What Trips People Up in Real Interviews
Scanning all IDs after each update — O(n²) overall.
Trying to update or remove entries inside a heap directly. Lazy deletion avoids it.
Returning the ID instead of its count.
Overflow in C++/Java; the answer array is long.
Solution Code
import heapq
def mostFrequentIDs(nums, freq):
count = {}
heap = []
res = []
for x, f in zip(nums, freq):
count[x] = count.get(x, 0) + f
heapq.heappush(heap, (-count[x], x))
while heap and -heap[0][0] != count[heap[0][1]]:
heapq.heappop(heap)
res.append(-heap[0][0] if heap else 0)
return resFrequently Asked Questions
What is the Most Frequent IDs problem?
Most Frequent IDs processes a stream of updates `(id, delta)` that add or remove copies of an ID, and after each update asks for the count of the most frequent ID (0 if the collection is empty). You need a structure that returns a maximum while counts go up and down — a max-heap with lazy deletion, or an ordered multiset of counts.
How do you solve Most Frequent IDs?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Most Frequent IDs?
Most Frequent IDs is asked at Snowflake. It is a medium difficulty problem.
What are common mistakes on Most Frequent IDs?
- Scanning all IDs after each update — `O(n²)` overall.
- Trying to update or remove entries inside a heap directly. Lazy deletion avoids it.
- Returning the ID instead of its count.
- Overflow in C++/Java; the answer array is `long`.