Design a Data Structure for Dynamic Top-K Frequent Items

Question and when to use it

An unending stream of integer IDs arrives one item at a time. add(x) records one more occurrence of ID x. topK(k) returns up to k distinct IDs with the highest current frequencies and their counts; tied IDs may appear in any order, and k can change between queries. Design exact solutions for read-heavy and write-heavy workloads and analyze their time and space costs. If the number of distinct IDs can grow without bound while memory is fixed, provide an approximate design and define what its error means.

This question fits software engineering and algorithms interviews. The exact contract permits frequency increments only: no deletion, sliding window, or distributed merge. Let N be the number of updates so far and D the number of distinct IDs, with k << D in the typical case. Public versions of the prompt explicitly ask for workload-dependent designs and a bounded-memory streaming extension, so “hash map plus min-heap” is only the beginning of the answer.

What the interviewer is evaluating

First, does the candidate establish the operation contract and workload ratio? A batch that asks once after the stream ends should not pay the same maintenance cost as an online leaderboard queried after every update.

Second, do the stated complexities match the maintained state? Counting in a hash map and building a size-k min-heap at query time gives expected O(1) for add and O(D log k) for topK. A claim of O(log k) heap maintenance per update also requires heap-position tracking and an explanation of when an item outside the heap enters it.

Third, can the candidate prove a dynamic structure correct? A strong answer states three invariants: every ID belongs to exactly one frequency bucket; bucket frequencies are strictly increasing and no bucket is empty; and an ID's bucket frequency equals its true accumulated count. The complexity argument should follow from those invariants.

Fourth, can the candidate distinguish exact top-k, heavy hitters, and frequency estimation? Space-Saving retains candidate keys with count bounds under a fixed counter budget. Count-Min Sketch primarily estimates the frequency of a supplied key and does not itself retain an enumerable set of IDs. Treating a sketch alone as a top-k list leaves candidate discovery unexplained.

Questions to clarify before answering

• Is k fixed or query-specific? A fixed K permits an indexed size-K heap. Arbitrary k favors a structure ordered across all frequencies.
• What is the update-to-query ratio? A write-heavy system can defer work until query time. Frequent queries justify maintaining order on every add.
• Must ties have a deterministic order? This contract permits any order, so a hash set inside each bucket is sufficient. Requiring ascending IDs calls for an ordered set and removes expected O(1) updates.
• Are deletion or time windows required? With increments only, an item moves from frequency f to adjacent frequency f + 1. Deletion adds reverse movement; a window also needs expiration state.
• Does D fit in memory? An exact answer for an unrestricted distribution retains every distinct ID's count. Fixed memory requires approximation or a replayable second pass.
• What error is acceptable? “Approximately correct” is not testable. Specify additive count error, an uncertain candidate set, or a frequency-separation condition that certifies top-k.
• Can counters overflow? A long-lived service needs 64-bit or wider counters. The example uses JavaScript number and is exact only within the safe-integer range.

30-second answer framework

“I would first clarify whether k varies, the read-write ratio, tie ordering, and the memory limit. For write-heavy and query-light traffic, I would use a hash map for expected O(1) adds, then scan D counts into a size-k min-heap in O(D log k) per query. If arbitrary-k queries are frequent, I would maintain an increasing doubly linked list of frequency buckets plus an ID → bucket map. An update moves one ID only from bucket f to adjacent bucket f + 1, giving expected O(1) updates; walking backward for k results costs O(min(k, D)), with O(D) space. If D cannot fit in memory, I would use fixed Space-Saving counters with error bounds and claim certified top-k only when the bounds separate. Count-Min Sketch still needs a candidate set to enumerate IDs.”

Step-by-step solution

Step 1: Compare exact designs by workload

“Hash map plus min-heap” is not a universal winner. It deliberately places ordering work on the query path, which is appropriate when writes dominate. If the product renders a leaderboard after every add, repeatedly scanning D keys becomes the bottleneck and the more involved frequency-bucket structure earns its cost.

Step 2: Establish frequency-bucket invariants

Keep a doubly linked list of buckets in increasing frequency order. Each bucket owns a set of IDs with that frequency, while a hash map locates an ID's bucket directly. A new ID joins the frequency-1 bucket. An existing ID moves from bucket f to bucket f + 1. Because one update increments by exactly one, a new bucket can only be inserted between the source and its successor; no list search is needed. Remove the source bucket as soon as it becomes empty.

Three invariants prove the result:

1. Every ID in locations appears in exactly one bucket set.
2. Every nonempty bucket's frequency equals the true count of every ID it contains.
3. Frequencies increase strictly from head to tail.

Walking backward from tail therefore cannot leave a higher-frequency ID behind, while ties may be returned in any order. Every visited bucket yields at least one result, so the number of visited buckets is no greater than the output size and query time is O(min(k, D)).

Step 3: Implement exact arbitrary-k queries

interface Bucket {
  frequency: number;
  values: Set<number>;
  prev: Bucket | null;
  next: Bucket | null;
}

interface TopKEntry {
  value: number;
  count: number;
}

class FrequencyIndex {
  private readonly locations = new Map<number, Bucket>();
  private head: Bucket | null = null;
  private tail: Bucket | null = null;

  add(value: number): void {
    const source = this.locations.get(value);

    if (!source) {
      let target = this.head;
      if (!target || target.frequency !== 1) {
        target = this.insertBefore(this.head, 1);
      }
      target.values.add(value);
      this.locations.set(value, target);
      return;
    }

    let target = source.next;
    if (!target || target.frequency !== source.frequency + 1) {
      target = this.insertAfter(source, source.frequency + 1);
    }

    source.values.delete(value);
    target.values.add(value);
    this.locations.set(value, target);

    if (source.values.size === 0) {
      this.removeBucket(source);
    }
  }

  topK(k: number): TopKEntry[] {
    if (!Number.isInteger(k) || k < 0) {
      throw new RangeError("k must be a non-negative integer");
    }

    const result: TopKEntry[] = [];
    let bucket = this.tail;

    while (bucket && result.length < k) {
      for (const value of bucket.values) {
        result.push({ value, count: bucket.frequency });
        if (result.length === k) break;
      }
      bucket = bucket.prev;
    }

    return result;
  }

  private insertBefore(next: Bucket | null, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev: next?.prev ?? null,
      next,
    };

    if (bucket.prev) bucket.prev.next = bucket;
    else this.head = bucket;

    if (next) next.prev = bucket;
    else this.tail = bucket;

    return bucket;
  }

  private insertAfter(prev: Bucket, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev,
      next: prev.next,
    };

    if (prev.next) prev.next.prev = bucket;
    else this.tail = bucket;

    prev.next = bucket;
    return bucket;
  }

  private removeBucket(bucket: Bucket): void {
    if (bucket.prev) bucket.prev.next = bucket.next;
    else this.head = bucket.next;

    if (bucket.next) bucket.next.prev = bucket.prev;
    else this.tail = bucket.prev;
  }
}

The complexity uses the usual expected constant-time assumptions for Map and Set, not a JavaScript specification guarantee of strict worst-case O(1). topK(0) returns an empty array, k > D returns all IDs, and a negative or non-integer k throws.

Step 4: State the approximation guarantee under bounded memory

The exact hash map grows with D. Space-Saving instead keeps only m counters containing an ID, an estimated count, and a maximum error; m > k is required to compare against boundary candidate k + 1. An observed tracked ID increments its counter. When an untracked ID arrives after all counters are occupied, it replaces the ID with minimum estimated count c_min; the new estimate becomes c_min + 1, with recorded error c_min.

For every monitored ID, true frequency lies in [estimate - error, estimate], and the paper bounds maximum overestimation by N / m. The top-k set can be certified when the smallest lower bound among the first k candidates is no smaller than the estimated upper bound of candidate k + 1. If those intervals overlap, return approximate candidates rather than presenting the estimated order as exact. When the entire stream has D <= m, no replacement occurs and counts remain exact.

Count-Min Sketch uses a fixed width × depth counter array. With width = ceil(e / ε) and depth = ceil(ln(1 / δ)) on an increment-only stream, an estimate for a supplied ID never falls below its true count and, with probability at least 1 - δ, is no greater than true count + εN. The sketch does not retain IDs, so it still needs a candidate heap, candidate set, or enumerable domain. A sketch alone cannot answer “which IDs are top-k?”

Step 5: Verify against an oracle, not only one example

Start with [1, 2, 1, 3, 2, 1] and verify that topK(2) returns the two IDs with frequencies 3 and 2. Then cover an empty structure, k = 0, k > D, all ties, one hot item plus many singletons, and one ID moving through many buckets.

Finally, generate a random update stream and use naive hash counts plus full sorting as the oracle. At intervals, verify that the result length is min(k, D), IDs are unique, every reported count is exact, and no excluded ID has a count above the smallest selected count. The implementation above passed this differential check over 10,000 deterministic random updates and several k values.

Example of a strong answer

“I will constrain the exact contract to increment-only updates, query-specific k, and arbitrary tie order. For many writes and rare queries, I would maintain only an ID → count hash map for expected O(1) adds. A query scans D IDs through a size-k min-heap, costing O(D log k) time and O(k) extra space.

For frequent leaderboard queries, I would use doubly linked frequency buckets. Buckets are ordered from low to high frequency and contain IDs tied at that frequency; a hash map locates each ID's bucket. One add moves an ID only from f to f + 1, so it examines an adjacent bucket and removes an empty source bucket. Updates are expected O(1), walking backward from the tail returns results in O(min(k, D)), and total space is O(D). Correctness follows from unique bucket membership, exact bucket counts, and strictly increasing bucket order.

If D does not fit in memory, the exact contract must change. I would retain m Space-Saving counters with candidate error intervals; maximum overestimation is bounded by N / m, and I would certify the set only when the first k lower bounds separate from later upper bounds. Count-Min Sketch can estimate a supplied ID but still needs candidate discovery. Before release, I would run randomized differential tests against full sorting and explicitly test ties, invalid k, and counter-overflow boundaries.”

Common mistakes

• Choosing a min-heap before asking about workload → Frequent queries scan all D IDs, while rare queries may not justify ongoing maintenance → Place the cost on the update or query path according to the actual ratio.
• Maintaining one fixed K when k varies → A query larger than the maintained K has no complete candidate set → Bound k explicitly or use frequency buckets or an ordered structure that supports arbitrary k.
• Mutating a heap key in place → An ordinary heap does not know an item's position, so its ordering breaks or stale records accumulate → Maintain ID → heap index, or remove and reinsert the old key with stated complexity.
• Leaving empty frequency buckets linked → A query can walk gaps from frequency 1 to the maximum count → Unlink a bucket immediately after its final ID moves.
• Claiming strict O(1) hashing → Map and Set support the usual expected-complexity analysis, not a strict language guarantee → State the hash assumption; use a balanced tree and accept O(log D) when worst-case bounds matter.
• Returning top-k directly from Count-Min Sketch → The sketch answers supplied-key queries and cannot enumerate unknown IDs → Maintain candidate discovery separately or use Space-Saving, which retains candidate keys.
• Reporting approximation without error → The interviewer cannot tell whether ranks k and k + 1 are distinguishable → Return estimates, lower and upper bounds, and whether the set is certified.
• Testing only the sample → Broken links, empty buckets, and tie boundaries often appear only after long update sequences → Differential-test against a full-sort oracle and assert the invariants.

Follow-up questions and responses

Follow-up 1: If topK always uses K = 100, do you still need frequency buckets?

Not necessarily. A count map, size-100 min-heap, and ID → heap index can adjust a heap member or compare against the minimum after each update in O(log 100). It may be simpler in code and memory layout, but it cannot answer topK(1000). Frequency buckets earn their complexity when k is arbitrary and expected constant-time updates matter.

Follow-up 2: What changes if tied IDs must be ascending?

Replace each bucket's Set with an ordered set, or sort only the boundary bucket that is partially consumed by a query. The first choice adds O(log s) to each movement for a bucket of size s; the second pays a boundary-sort cost only at query time. Choose according to how often deterministic order is required.

Follow-up 3: How would you add remove(x)?

Move an ID from frequency f to f - 1 by symmetrically checking the predecessor bucket, removing the ID from locations when it reaches zero. Define whether removing a missing ID throws or is ignored. With concurrent add and remove, locating, moving, and unlinking an empty bucket must share one atomic critical section, or the same ID can appear in two buckets.

Follow-up 4: What if the query asks for the last 10 minutes only?

Frequencies are no longer monotonic. The bucket index also needs timestamped events or time-bucketed counts so expiration can issue reverse updates. A per-event queue is exact but uses space proportional to events in the window. Time buckets reduce state while introducing an explicit boundary error. An all-history Space-Saving summary cannot subtract arbitrary expired events directly.

Follow-up 5: What if Space-Saving intervals for ranks k and k + 1 overlap?

Increase the counter budget m, report that the candidate set is not yet certified, or replay the data to count a candidate set exactly. A second pass only corrects retained candidates. If the summary was too small to guarantee that the true top-k entered that set, enlarge the candidate set before replay.

Follow-up 6: How do you obtain global top-k across shards?

Local top-k lists cannot produce exact global top-k for an arbitrary distribution. An ID just below the cutoff on every shard may rank globally after aggregation. An exact design must aggregate all relevant counts or maintain candidate bounds that prove coverage. An approximate design can merge mergeable summaries, but its contract must include the additional error and reporting delay.