PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates ability to design efficient in-memory data structures for frequency tracking, including handling recency-based tie-breaking, memory bounds under churn, and concurrency implications.

  • Medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

Design top-K frequency structure

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Design an in-memory data structure that supports: add(x) to observe an item, inc(x) to increment its frequency, dec(x) to decrement (deleting when zero), and topK(k) to return the k items with highest frequency, breaking ties by most recent update. Target O( 1) amortized updates and O(k) retrieval using hash maps plus a doubly linked list of frequency buckets. Describe node layout, how buckets are created/merged, how recency is tracked, tie-breaking, memory bounds under churn, and concurrency considerations.

Quick Answer: This question evaluates ability to design efficient in-memory data structures for frequency tracking, including handling recency-based tie-breaking, memory bounds under churn, and concurrency implications.

Design an in-memory structure that tracks item frequencies and answers top-K queries. You will implement a single driver function `solution(operations)` that replays a list of operations against the structure and returns the result of every `topK` query, in order. Each operation is a 2-element list: - `["add", x]` — observe item `x` (increments its frequency by 1, creating it if absent). - `["inc", x]` — increment the frequency of `x` by 1 (creating it if absent). Semantically identical to `add`. - `["dec", x]` — decrement the frequency of `x` by 1; when its frequency reaches 0 the item is deleted. A `dec` on an unknown item is a no-op. - `["topK", k]` — return the `k` items with the highest frequency. **Ties are broken by most-recent update** (the item updated more recently comes first). If fewer than `k` items exist, return all of them. Return a list containing the result list of each `topK` operation, in the order the `topK` operations appear. A recency 'update' is any `add`, `inc`, or any `dec` that does NOT delete the item. The intended efficient design uses a hash map of item -> node plus a doubly linked list of frequency buckets (each bucket a recency-ordered list of items) to get O(1) amortized updates and O(k) retrieval; the reference here uses a clear simulation, but your console solution may implement the bucket-list design. Example: operations `[["add","a"],["add","b"],["inc","a"],["topK",2]]` → `[["a","b"]]` because `a` has frequency 2 and `b` has frequency 1.

Constraints

  • 1 <= number of operations <= 10^5
  • Items are strings; k is a non-negative integer
  • A 'dec' on an item not currently present is a no-op
  • An item is deleted exactly when its frequency reaches 0
  • Tie-break among equal frequencies is by most-recent update (recency descending)
  • topK with k greater than the number of live items returns all live items

Examples

Input: ([['add', 'a'], ['add', 'b'], ['inc', 'a'], ['topK', 2]],)

Expected Output: [['a', 'b']]

Explanation: a is incremented to frequency 2, b stays at 1, so a outranks b.

Input: ([['inc', 'x'], ['inc', 'y'], ['inc', 'y'], ['inc', 'z'], ['inc', 'z'], ['topK', 1]],)

Expected Output: [['z']]

Explanation: x=1, y=2, z=2; y and z tie at frequency 2, but z was updated most recently, so topK(1) returns z.

Input: ([['add', 'a'], ['add', 'b'], ['topK', 2]],)

Expected Output: [['b', 'a']]

Explanation: a and b both have frequency 1; b was added more recently, so the recency tie-break puts b first.

Input: ([['inc', 'a'], ['inc', 'a'], ['dec', 'a'], ['dec', 'a'], ['topK', 3]],)

Expected Output: [[]]

Explanation: a rises to 2 then is decremented back to 0 and deleted, leaving the structure empty.

Input: ([['inc', 'p'], ['inc', 'q'], ['inc', 'p'], ['inc', 'q'], ['inc', 'q'], ['dec', 'q'], ['topK', 2]],)

Expected Output: [['q', 'p']]

Explanation: p=2 and q ends at 2 after the dec; the dec is a non-deleting update that refreshes q's recency, making q more recent than p, so q comes first.

Input: ([['topK', 5]],)

Expected Output: [[]]

Explanation: Querying an empty structure returns an empty list even though k=5.

Input: ([['add', 'a'], ['add', 'a'], ['add', 'b'], ['add', 'c'], ['add', 'b'], ['topK', 10]],)

Expected Output: [['b', 'a', 'c']]

Explanation: Frequencies a=2, b=2, c=1; a and b tie at 2 but b was updated last, so order is b, a, then c. k=10 exceeds the 3 live items so all are returned.

Hints

  1. Track two maps: item -> frequency and item -> a monotonically increasing recency stamp. Bump the recency stamp on every add/inc and on every dec that does not delete the item.
  2. For O(1) amortized updates, keep a doubly linked list of frequency buckets; each bucket holds the items at that frequency in recency order, so inc/dec moves an item to an adjacent bucket in constant time.
  3. When sorting for topK, the key is (frequency descending, recency descending). The optimal retrieval walks buckets from the highest frequency downward, taking items front-to-back until k are collected.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Deep Equality of Two Records - Uber (medium)
  • Shortest Path in a Grid with Blocked Cells - Uber (medium)
  • Reconstruct the Alphabet Order of an Alien Language - Uber (medium)
  • Design and Implement an LRU Cache - Uber (medium)
  • Maximize Throughput and Count Trigger Components - Uber (medium)