Frequency Tracker

Frequency Tracker

What is this problem about?

The Frequency Tracker interview question asks you to design a data structure that can keep track of the frequencies of a stream of numbers. You need to support three operations efficiently:

1. add(number): Add a number to the data structure.
2. deleteOne(number): Remove one occurrence of a number (if it exists).
3. hasFrequency(frequency): Return true if there is any number in the data structure that currently has the exact given frequency.

Why is this asked in interviews?

Microsoft uses this Design coding problem to test your ability to manage state across multiple interconnected Hash Tables. While tracking frequencies is easy (using a simple map), checking if a specific frequency exists in $O(1)$ time requires a "reverse lookup" table. It evaluates whether you can keep two data structures synchronized during additions and deletions without introducing bugs or performance bottlenecks.

Algorithmic pattern used

This problem relies on a Double Hash Table (or Array) Pattern.

1. Map 1 (counts): Tracks the frequency of each number (number -> frequency).
2. Map 2 (freqCounts): Tracks how many numbers currently have a specific frequency (frequency -> count_of_numbers). When you add or deleteOne, you must update counts first, and then update freqCounts by decrementing the count for the old frequency and incrementing the count for the new frequency.

Example explanation

1. add(3): counts[3] becomes 1. freqCounts[1] becomes 1.
2. add(3): counts[3] becomes 2. freqCounts[1] becomes 0. freqCounts[2] becomes 1.
3. hasFrequency(2): Looks up freqCounts[2]. It is > 0. Returns True.
4. deleteOne(3): counts[3] becomes 1. freqCounts[2] becomes 0. freqCounts[1] becomes 1.
5. hasFrequency(2): Looks up freqCounts[2]. It is 0. Returns False.

Common mistakes candidates make

• $O(N)$ Frequency Check: Iterating through the entire counts map to answer hasFrequency, which is too slow for large streams.
• Sync Errors: Forgetting to decrement the old frequency in freqCounts when a number's count changes.
• Deleting Non-existent Elements: Decrementing counts[number] below zero when deleteOne is called on a number that isn't in the structure.

Interview preparation tip

Whenever a problem asks for $O(1)$ lookups based on a property that changes (like frequency), you almost always need a secondary Hash Table to index that property directly.