Design a Key-Value Store with Versioning
Last updated: October 30, 2025
Quick Overview
Implement a key-value store that supports versioned reads. Each write creates a new version, and reads can query the value at any historical timestamp. Support get, put, and get_at_timestamp operations.
Intuit
October 30, 202513
7
2,581 solved
Implement a key-value store that supports versioned reads. Each write creates a new version, and reads can query the value at any historical timestamp. Support get, put, and get_at_timestamp operations.
Appears in Craft Demos and senior-level phone screens. Directly relevant to Intuit's financial systems where audit trails require querying historical state of any record.
What the Interviewer Expects
- Implement efficient versioned storage with O(log n) historical reads via binary search
- Handle edge cases like querying timestamps before the first write
- Design a clean API that separates current and historical access patterns
- Consider memory management for long-lived keys with many versions
- Write comprehensive tests covering version boundaries
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you add a compact/gc operation to reclaim old versions?
- How would you implement range queries across versions?
- What changes would you make to support transactions across multiple keys?
- How would you distribute this across multiple machines?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
This problem requires us to implement a key-value store that supports versioning, allowing us to read values at specific historical timestamps. The key challenge is efficiently managing the versions o...
Approach
- Data Structure: Use a dictionary to map keys to lists of tuples, where each tuple contains a timestamp and the corresponding value. This allows us to keep track of all versions for each key.
...
Submit Your Answer
