Design a Versioned Key-Value Store
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a data structure for storing values by key over time.
The structure should support these operations:
- `put(key, value, timestamp)`: Store the string `value` for the string `key` at the given integer `timestamp`.
- `get(key, timestamp)`: Return the value associated with `key` at the greatest timestamp less than or equal to `timestamp`.
If there is no stored value for `key` at or before the requested time, return an empty string.
Assumptions:
- `key` and `value` are non-empty strings.
- `timestamp` is a positive integer.
- Calls to `put` are given in strictly increasing timestamp order.
Example:
- `put("foo", "bar", 1)`
- `get("foo", 1)` returns `"bar"`
- `get("foo", 3)` returns `"bar"`
- `put("foo", "baz", 4)`
- `get("foo", 4)` returns `"baz"`
- `get("foo", 5)` returns `"baz"`
Quick Answer: This question evaluates understanding of time-versioned data structures, temporal indexing, and efficient lookup strategies for storing and retrieving values by key across timestamps.
Implement solution(operations). Operations are ["put", key, value, timestamp] and ["get", key, timestamp]. For get, return the value at the greatest timestamp <= the query timestamp, or the empty string if none exists. Return all get results in order.
Constraints
- put timestamps are strictly increasing
- keys and values are strings
Examples
Input: ([['put', 'foo', 'bar', 1], ['get', 'foo', 1], ['get', 'foo', 3], ['put', 'foo', 'baz', 4], ['get', 'foo', 4], ['get', 'foo', 5], ['get', 'x', 5]],)
Expected Output: ['bar', 'bar', 'baz', 'baz', '']
Input: ([['put', 'a', 'x', 2], ['put', 'a', 'y', 5], ['get', 'a', 4], ['get', 'a', 5]],)
Expected Output: ['x', 'y']
Hints
- Store sorted (timestamp, value) lists per key and binary-search them.