Katkat
Back

Design a temporal key-value store with historical reads

LyftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's grasp of data structures and algorithms needed to implement a temporal key-value store supporting timestamped set/get operations and efficient historical reads, including performance targets like O(log n) per operation.

Implement a key–value store supporting set(key, value, timestamp) and get(key, timestamp) -> the value at the greatest timestamp ≤ the given timestamp (or empty if none). Optimize for up to 1e5 keys and 1e6 operations; discuss data structures to achieve O(log n) per operation, how you would handle memory growth, and any serialization considerations for persistence.