Time-Based Key-Value Store

Interview Problem Advanced Medium Array Hash Map Binary Search

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement TimeMap.set(key, value, timestamp) and TimeMap.get(key, timestamp). Set timestamps for each key are strictly increasing. get returns the value with greatest timestamp <= query, or an empty string.

Starter code

class TimeMap:
    def __init__(self):
        pass

Test cases

version-history

{
  "operations": [
    "TimeMap",
    "set",
    "get",
    "get",
    "set",
    "get",
    "get"
  ],
  "arguments": [
    [],
    [
      "foo",
      "bar",
      1
    ],
    [
      "foo",
      1
    ],
    [
      "foo",
      3
    ],
    [
      "foo",
      "bar2",
      4
    ],
    [
      "foo",
      4
    ],
    [
      "foo",
      5
    ]
  ]
}

Expected: [null,null,"bar","bar",null,"bar2","bar2"]

Wizard outline

Step 1: Initialize TimeMap
Replace the empty starter with the first real state owned by TimeMap. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Wizard Stateful Timemap Exact case
Complete the readable core algorithm for one representative Interview case. Append-only per-key history preserves sorted order without an insertion sort.
Step 4: Harden the Wizard Stateful Timemap History boundary
Repair the reviewed boundary and pass the complete submission contract. Moving right after an eligible midpoint preserves it as the current answer while searching for a later eligible version.

Footguns and prerequisites

A query between versions must return the earlier version, not require an exact timestamp match.
dictionaries and sets
arrays strings two pointers sliding window

Reviewed references

LeetCode 981 — Time Based Key-Value Store

Practice prerequisites

Find the First True Boundary(opens in a new tab)
Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing time based key value store as a complete Interview Problem.

Recommended approach and implementation

Map each key to an append-only list of timestamp-value pairs. Binary-search for the rightmost timestamp no greater than the query.

Why it works: Strictly increasing set timestamps keep each history sorted. The binary search maintains all indices at or before right as possible predecessors and returns the greatest qualifying index, which is exactly the requested latest version.

class TimeMap:
    """
    Checkpoint 1: initialize the state owned by this Interview contract.
    Checkpoint 2: assemble the primary transition without hiding the boundary.
    """
    def __init__(self):
        self.history = {}
    def set(self, key, value, timestamp):
        self.history.setdefault(key, []).append((timestamp, value))
    def get(self, key, timestamp):
        entries = self.history.get(key, [])
        left, right = 0, len(entries) - 1
        answer = ''
        while left <= right:
            middle = (left + right) // 2
            if entries[middle][0] <= timestamp:
                answer = entries[middle][1]
                left = middle + 1
            else:
                right = middle - 1
        return answer