Last active 5 days ago

Interview prep notes

linkjobai revised this gist 5 days ago. Go to revision

1 file changed, 40 insertions

timemap.md(file created)

@@ -0,0 +1,40 @@
1 + # Time-Based Key-Value Store (LeetCode 981): Binary Search on Timestamps
2 +
3 + The problem: implement `set(key, value, timestamp)` and `get(key, timestamp)`, where `get` returns the value set at the largest timestamp less than or equal to the one requested.
4 +
5 + ## Key observation
6 +
7 + Timestamps for each key arrive in increasing order. So every key's history is already a **sorted list**, and `get` is a binary search.
8 +
9 + ```python
10 + import bisect
11 + from collections import defaultdict
12 +
13 + class TimeMap:
14 + def __init__(self):
15 + self.times = defaultdict(list)
16 + self.values = defaultdict(list)
17 +
18 + def set(self, key, value, ts):
19 + self.times[key].append(ts)
20 + self.values[key].append(value)
21 +
22 + def get(self, key, ts):
23 + i = bisect.bisect_right(self.times[key], ts)
24 + return self.values[key][i - 1] if i else ""
25 + ```
26 +
27 + `set` is O(1); `get` is O(log n) for a key with n versions.
28 +
29 + ## Explaining `bisect_right`
30 +
31 + `bisect_right` returns the first position *greater* than `ts`, so the element just before it is the latest timestamp that is at most `ts`. If the position is 0, nothing qualifies and you return the empty string. Walking through this off-by-one out loud is what the interviewer wants to hear.
32 +
33 + ## Follow-ups
34 +
35 + - **Timestamps not in order:** use a balanced BST or a sorted container (like `SortedList`), at O(log n) per insert.
36 + - **Memory limits:** drop old versions beyond a retention window.
37 + - **Real systems:** this is how multi-version stores work. Bigtable and HBase keep timestamped cells, and databases use MVCC so readers see a consistent snapshot.
38 +
39 + ---
40 + *Disclosure: I'm on the team behind [Linkjob AI](https://www.linkjob.ai/), an AI tool for job interviews.*
Newer Older