Design a versioned key-value store
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Design and implement a versioned key-value store that supports set(key, value, timestamp) and get(key, timestamp) to retrieve the most recent value at or before timestamp. Discuss data structures, time/space complexity, and how to handle out-of-order timestamps, large timestamp ranges, and memory limits. Extend the API to support delete, range queries by time, and background compaction.
Quick Answer: This question evaluates proficiency in designing time-versioned key-value stores, focusing on appropriate data structures, temporal query semantics, API design, and time/space complexity analysis within the Coding & Algorithms domain.