Design structure for top-K frequent elements

You are working with a large collection of items represented by integer IDs (e.g., product IDs, user IDs, etc.). Updates and queries arrive over time.

You need to support the following operations:

• add(x): record one occurrence of item x (increment its frequency count).
• topK(k): return any ordering of the k most frequent items seen so far, along with their frequencies.

Design data structures and algorithms to support these operations, and discuss different approaches under two workload patterns:

1. Read-heavy workload

   • The system receives relatively few add(x) updates but many topK(k) queries.
   • Example: A daily batch job loads all events once, and then the UI serves thousands of top-K queries per minute.

2. Write-heavy workload

   • The system receives many add(x) updates but relatively few topK(k) queries.
   • Example: A logging system where events stream in continuously, and an analyst occasionally queries the current top-K items.

Requirements

• For each workload type (read-heavy and write-heavy):
  1. Propose suitable data structures to implement add(x) and topK(k).
  2. Analyze the time complexity of each operation (add and topK).
  3. Analyze the space complexity.
  4. Explain the trade-offs and why your design is better suited to that workload pattern.
• You may assume that:
  • The domain of x (possible IDs) is large.
  • k is much smaller than the total number of distinct items.
  • The system should scale to millions of updates.

Example

Given the sequence of operations:

• add(1)
• add(2)
• add(1)
• add(3)
• add(2)
• add(1)

A call to topK(2) should return items [1, 2] (since 1 appeared 3 times, 2 appeared 2 times, 3 appeared 1 time).

Task

Describe, in detail:

• At least one design optimized for read-heavy scenarios.
• At least one design optimized for write-heavy scenarios.
• How you would adapt or approximate the solution if the data is a never-ending stream and you must use limited memory (high level is sufficient).

Implementation (code) is optional; focus primarily on explaining data structures, algorithms, and their trade-offs.