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

SeniorPrefer not to say

Jul 2026

Summary

Uber system design round for a software engineering role. One meaty question about a versioned key-value store that took up the whole session. The design constraints were trickier than they looked on the surface.

Questions Asked (1)

Design a time-versioned key-value store where writes do not accept a caller-supplied timestamp. It should support set(key, value), getLatest(key), and getAtOrBefore(key, wallTime). Walk through your data structures, how you guarantee monotonically increasing timestamps despite clock skew, and the time and space complexity of each operation.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

The no-external-timestamp constraint is what makes this annoying.

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 per-key append-only log with a monotonic timestamp source (e.g., a hybrid logical clock) to avoid clock skew issues. Explain how getLatest and getAtOrBefore leverage binary search on the timestamp index, and analyze time/space complexity for each operation.

Pro tip: Emphasize that using a monotonic clock (like a hybrid logical clock) ensures timestamps are strictly increasing even with clock skew, and discuss trade-offs between in-memory vs. persistent storage for scalability.

1. Clarify Requirements and Constraints

Ask about expected read/write patterns, data size, latency requirements, and whether timestamps need to be globally unique or just per-key monotonic.

2. Design Data Structures

Propose storing each key's versions in an append-only log (e.g., array or balanced BST) sorted by timestamp, with an index for binary search.

3. Ensure Monotonic Timestamps

Use a hybrid logical clock (HLC) or a monotonic counter combined with wall time to generate strictly increasing timestamps despite clock skew.

4. Implement Operations

For set, append a new version with a generated timestamp; for getLatest, return the last version; for getAtOrBefore, binary search for the largest timestamp ≤ wallTime.

5. Analyze Complexity and Trade-offs

Discuss time complexity (O(1) for set and getLatest, O(log n) for getAtOrBefore) and space complexity (O(n) per key), and trade-offs like memory vs. disk storage.

Key Points to Mention

Use of hybrid logical clocks (HLC) to combine physical and logical time for monotonicity.
Append-only log per key with binary search for efficient range queries.
Time complexity: set O(1), getLatest O(1), getAtOrBefore O(log n).
Space complexity: O(n) per key, where n is number of versions.
Handling clock skew by never relying solely on wall clock; use logical counters.
Trade-offs between in-memory and persistent storage for scalability and durability.

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