Coding · Design a structure
Time Based Key-Value Store
- Appears on company lists
- Medium
- Senior and above
- 2 sources
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
Design a store that keeps every value ever written for a key together with the time of the write. set(key, value, timestamp) records a value, and get(key, timestamp) returns the value with the largest timestamp not after the one asked for, or an empty string if there is none. Timestamps for one key only increase, and there can be 200,000 calls, so a read must not scan the whole history. Example: after set("a","x",10) and set("a","y",20), get("a",15) is "x", get("a",5) is "", and get("a",25) is "y".
Restated in our own words, not a quote from Netflix or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
First I confirm the ordering promise: do timestamps for a key always increase, or can writes arrive late? That decides whether plain appending is enough. Can two writes share a timestamp for the same key? What should get return for an unknown key, or for a time before the first write? Do values ever need deleting or expiring? How many calls are there, and are reads more common than writes?
Assumptions: timestamps strictly increase per key, the store lives in memory, nothing is deleted, an unknown key or a time that is too early returns an empty string, and reads are at least as common as writes. A single thread is enough, and I would raise locking as a follow-up.
Brute force
Say the obvious answer and why it is too slow.
The simple design keeps, for each key, a list of (timestamp, value) pairs and answers a read by scanning that list for the latest pair whose timestamp does not exceed the query, walking from the back until one fits. A write is O(1) and a read is O(m), where m is the number of values stored under the key. With 200,000 calls on one hot key, split evenly between writes and reads, a read can walk about 100,000 entries, so the total approaches ten billion comparisons, which is far too slow. Another idea is to store one entry per possible timestamp, which wastes memory and is unusable if times are in the billions. The list is already sorted by timestamp, and that is the hint that binary search applies.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(m) per get
- Time
- set O(1), get O(log m)
- Space
- O(total writes)
This is a hash map plus binary search. The map finds the key's history in O(1) on average. Because timestamps for a key only increase, appending keeps the history sorted for free, so no sorting and no balanced tree is needed. A read then asks: in a sorted list of timestamps, which is the last one not greater than t? That is the classic predecessor search, a binary search for the rightmost position that satisfies a monotone condition.
The condition is timestamp[i] <= t. It is true for a prefix of the list and false after it, which is why binary search is valid. I keep an answer variable. When the middle element satisfies the condition, I record its value and search to the right for something later. Otherwise I search to the left. When the range is empty, the recorded value is the answer, and if nothing was recorded the answer is the empty string.
Correctness: the loop keeps two facts. Everything left of low satisfies the condition, everything right of high does not, and the recorded value belongs to the rightmost satisfying index seen so far. When the pointers cross, the recorded value is therefore the last satisfying entry. If two writes ever shared a timestamp, the later one would win, because the search always moves right on a match.
Out loud: a map from key to an append-only sorted list, and each read is a binary search for the last entry at or before the time asked. Writes are O(1) amortised and reads are O(log m).
Walk it through
A dry run on the example, step by step.
| step | call | list for a | probes (index) | returns |
|---|---|---|---|---|
| 1 | set(a,"x",10) | 10:x | - | null |
| 2 | set(a,"y",20) | 10:x,20:y | - | null |
| 3 | set(a,"z",30) | 10:x,20:y,30:z | - | null |
| 4 | get(a,5) | same | 1 late, 0 late | empty string |
| 5 | get(a,25) | same | 1 ok, 2 late | y |
| 6 | get(a,30) | same | 1 ok, 2 ok | z |
| 7 | get(a,99) | same | 1 ok, 2 ok | z |
Follow the trace: three writes to key a at times 10, 20 and 30 build the sorted list. Read at 5: the first probe looks at index 1, time 20, which is too late, so go left; the probe at index 0, time 10, is also too late; the range empties with nothing recorded, so the result is an empty string. Read at 25: index 1 qualifies, so record y and go right; index 2, time 30, is too late; the answer is y. Read at 30: index 1 qualifies, then index 2 qualifies because the rule is not after, so the answer is z. Read at 99 qualifies at both probes and ends on z, the newest value. No read needed more than two probes.
The code
Runnable JavaScript, checked against test cases.
class TimeMap {
constructor() {
this.history = new Map();
}
set(key, value, timestamp) {
if (!this.history.has(key)) this.history.set(key, []);
this.history.get(key).push([timestamp, value]);
}
get(key, timestamp) {
const entries = this.history.get(key);
if (!entries) return "";
let low = 0;
let high = entries.length - 1;
let answer = "";
while (low <= high) {
const mid = (low + high) >> 1;
if (entries[mid][0] <= timestamp) {
answer = entries[mid][1];
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
}
function run(ops, args) {
let store = null;
return ops.map((op, i) => {
if (op === "TimeMap") {
store = new TimeMap();
return null;
}
if (op === "set") {
store.set(...args[i]);
return null;
}
return store.get(...args[i]);
});
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Unknown key: there is no history, so the read returns an empty string at once.
- Time before the first write: every probe fails, nothing is recorded, and the result is an empty string.
- Exact timestamp match: the condition uses less-than-or-equal, so the value written at that time is returned.
- Time after the last write: the search ends on the final entry, so the newest value is returned.
- Same timestamp on different keys: each key has its own list, so they never interfere.
- A stored empty string: it looks the same as not found; if that matters, return a distinct marker for absence.
Follow-ups to expect
Where the interviewer pushes next.
- What changes if writes can arrive out of timestamp order?
- How would you delete or expire old versions without scanning every key?
- How would you add a read that returns the earliest value at or after a time?
- How would you make this safe for many threads reading while one thread writes?
- What if the history of one key no longer fits in memory?
Where candidates slip
The mistakes this problem punishes.
- Scanning the list linearly and calling it a binary search because the list is sorted.
- Returning the entry at
lowafter the loop, which is one past the answer, or the entry athighwithout guarding the case where it is -1. - Using strict less-than so an exact timestamp match is missed.
- Returning
undefinedor null instead of an empty string when nothing qualifies. - Sorting the list again on every write, which turns a cheap append into O(m log m).
- Keeping one global list of writes instead of one list per key.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.