Uber·Software Engineer·Onsite - System Design / Architecture·Senior

Senior

Jul 2026

Summary

Uber system design round for a software engineer role. The whole session was focused on one meaty data structure problem, and they really wanted you to go deep on the implementation details rather than just sketch a high-level architecture.

Questions Asked (1)

Design an in-memory data structure that supports adding items, incrementing or decrementing their frequency (with deletion at zero), and returning the top K items by frequency, where ties are broken by most recent update. Updates should be O(1) amortized and retrieval O(k).

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one took me a while to even understand what they were asking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a design using a hash map for O(1) access to item nodes and a doubly linked list of frequency buckets to maintain order. Explain how updates adjust frequencies and move nodes between buckets, and how top K retrieval traverses buckets from highest frequency, using a recency list within each bucket for tie-breaking.

Pro tip: Mention that this is essentially an LFU cache with recency tie-breaking, and that the same design can be adapted for real-time trending items at Uber by adding time-decay or sliding windows.

1. Clarify Requirements and Constraints

Ask about expected data size, update patterns, and whether K is fixed or variable. Confirm that ties are broken by most recent update and that deletion occurs at zero frequency.

2. Propose Core Data Structures

Use a hash map from item to node for O(1) access, and a doubly linked list of frequency buckets (each bucket contains a set of items with that frequency). Within each bucket, maintain a doubly linked list ordered by recency for tie-breaking.

3. Detail Update Operations

For increment: move item to next higher frequency bucket (create if needed), updating recency. For decrement: move to lower bucket, and if frequency becomes zero, remove item. Ensure O(1) amortized by adjusting bucket pointers.

4. Explain Top K Retrieval

Traverse frequency buckets from highest to lowest, collecting items from each bucket's recency list until K items are gathered. This yields O(k) time if buckets are traversed efficiently, skipping empty buckets.

5. Discuss Trade-offs and Optimizations

Compare with alternative designs like heaps or balanced trees, highlighting why this achieves O(1) updates and O(k) retrieval. Mention potential memory overhead and how to handle concurrent updates if needed.

Key Points to Mention

Hash map for O(1) item lookup and doubly linked list of frequency buckets for ordered frequencies.
Within each frequency bucket, a doubly linked list maintains recency order for tie-breaking.
Increment/decrement operations move items between buckets in O(1) amortized time by adjusting pointers.
Top K retrieval traverses buckets from highest frequency, collecting items until K reached, ensuring O(k) time.
Deletion at zero frequency removes item from hash map and bucket.
This design is analogous to an LFU cache with recency tie-breaking, and can be extended with time-decay for real-world trending.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.