Lyft·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Lyft software engineer round that was basically a deep dive into a single system design problem. More involved than I expected for what felt like a coding screen at first.

Questions Asked (1)

Design a key-value store that supports set(key, value, timestamp) and get(key, timestamp), where get returns the value at the largest stored timestamp that doesn't exceed the query timestamp. Handle up to 100k keys and 1 million operations, and discuss data structure choices, memory growth, and persistence via serialization.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with a sorted map per key and binary search, which is the right instinct, but fumbled a bit explaining why sorted insertion is still O(log n) amortized versus a naive array.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a data structure like a hash map of sorted lists (or balanced BSTs) to store per-key timestamp-value pairs, enabling efficient set and get operations. Discuss trade-offs in memory and performance, and outline persistence strategies such as periodic snapshots or write-ahead logging.

Pro tip: Emphasize that timestamps are monotonically increasing per key, allowing append-only lists and binary search for O(log n) get; also mention that memory can be optimized by storing deltas or using compression if values are large.

1. Clarify requirements and constraints

Confirm expected operation mix, latency requirements, and whether timestamps are unique per key. Discuss scale: 100k keys, 1M ops, and potential memory limits.

2. Choose core data structures

Propose a hash map from key to a sorted structure (e.g., dynamic array or balanced BST) of (timestamp, value) pairs. Explain how set appends and get uses binary search.

3. Analyze performance and memory

Calculate time complexity: O(1) average for set (append), O(log n) for get. Discuss memory growth: each key stores all versions; consider pruning or compression if needed.

4. Address persistence and serialization

Outline options: periodic snapshots of the entire store, write-ahead logging for durability, or a combination. Discuss serialization formats (e.g., JSON, Protobuf) and trade-offs in speed and size.

5. Discuss trade-offs and optimizations

Compare alternatives like using a single sorted list per key vs. a global sorted list, or using a B-tree. Mention concurrency, sharding, and eviction policies if relevant.

Key Points to Mention

Hash map with per-key sorted list (or balanced BST) for efficient timestamp-based retrieval.
Binary search for get operation to find largest timestamp ≤ query timestamp.
Time complexity: O(1) average for set, O(log n) for get; space complexity O(total versions).
Memory growth concerns and possible mitigations: pruning old versions, compression, or TTL.
Persistence via snapshots and/or write-ahead logging; serialization format trade-offs.
Scalability considerations: sharding by key, concurrency control, and handling 1M operations.

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