Live Top-K Frequency
MediumHash Map ยท Bloomberg
Implement FrequencyTracker, a multiset of integers that starts empty.
add(x)inserts one occurrence ofx.remove(x)deletes one occurrence ofx, or does nothing ifxis absent.top(k)returns thekdistinct values with the highest occurrence counts, ordered by count descending and then by value ascending. If fewer thankdistinct values are present, it returns all of them.
Example 1
- Input:
- FrequencyTracker(), add(5), add(3), add(5), add(3), add(8), top(2), remove(5), remove(5), top(3)
- Output:
- [null, null, null, null, null, null, [3, 5], null, null, [3, 8]]
- Explanation
- Values
3and5tie at two occurrences, so3comes first. After both5s are removed it is no longer present, leaving only two distinct values.
Example 2
- Input:
- FrequencyTracker(), top(1), remove(4), add(4), top(5)
- Output:
- [null, [], null, null, [4]]
Example 3
- Input:
- FrequencyTracker(), add(-1), add(2), add(2), remove(2), top(2)
- Output:
- [null, null, null, null, null, [-1, 2]]
- Explanation
- Both values have one occurrence left, so the smaller value
-1is listed first.
Constraints
-10^9 <= x <= 10^91 <= k <= 10^5- At most
10^5calls are made