Last active 5 days ago

Interview prep notes

Revision 10c240f86202639e2507f3c4018334d4353ee463

timemap.md Raw

Time-Based Key-Value Store (LeetCode 981): Binary Search on Timestamps

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.

Key observation

Timestamps for each key arrive in increasing order. So every key's history is already a sorted list, and get is a binary search.

import bisect
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)
        self.values = defaultdict(list)

    def set(self, key, value, ts):
        self.times[key].append(ts)
        self.values[key].append(value)

    def get(self, key, ts):
        i = bisect.bisect_right(self.times[key], ts)
        return self.values[key][i - 1] if i else ""

set is O(1); get is O(log n) for a key with n versions.

Explaining bisect_right

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.

Follow-ups

  • Timestamps not in order: use a balanced BST or a sorted container (like SortedList), at O(log n) per insert.
  • Memory limits: drop old versions beyond a retention window.
  • 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.

Disclosure: I'm on the team behind Linkjob AI, an AI tool for job interviews.