Framework Thinking - Neetcode 150 - Time Based Key-Value Store

Here is solutions for Time Based Key-Value Store.

1. Understand the problem

You need to design a data structure that supports:

  • set(key, value, timestamp): Store value under key at this timestamp.

  • get(key, timestamp): Return the value such that:

    • Its timestamp t is ≤ timestamp, and

    • Among those, t is the largest possible.

If no such timestamp exists, return “” (empty string).

2. Clarify constraints (Q&A style)

  1. Are timestamps inserted in strictly increasing order for the same key?
  • Yes. For any given key, calls to set will have non-decreasing timestamps.

=> This is very important; it lets us keep arrays sorted without extra work.

  1. Rough size constraints (how many operations)?
  • O(N^2) is too slow, O(N) is ok, O(logN) is better.
  1. What to return if key was never set at any time ≤ timestamp?
  • Return empty string “”.
  1. Are keys reused many times?
  • Yes, same key may be set many times with different timestamps.

3. Explore examples


set("foo", "bar", 1)
get("foo", 1)  -> "bar"   # exact match
get("foo", 3)  -> "bar"   # closest timestamp ≤ 3 is 1

set("foo", "bar2", 4)
get("foo", 4)  -> "bar2"
get("foo", 5)  -> "bar2"
get("foo", 0)  -> ""      # no timestamp ≤ 0

4. Brainstorm 2 - 3 ideas

4.1. Naive Solution - Set O(1), Get O(N)

  • set: O(1) (just append).

  • get: Worst case O(n) where n = number of versions for that key.

4.2. Optimized with binary search per key

  • set: add value (timestamp, val), O(1) (just append).

  • get: O(logn), query binary search by timestamp.

5. Implement solutions

5.1. Brute Force - Set O(1), Get O(N)

class TimeMap:

    def __init__(self):
        self.keyStore = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keyStore:
            self.keyStore[key] = {}
        if timestamp not in self.keyStore[key]:
            self.keyStore[key][timestamp] = []
        self.keyStore[key][timestamp].append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.keyStore:
            return ""
        seen = 0

        for time in self.keyStore[key]:
            if time <= timestamp:
                seen = max(seen, time)
        return "" if seen == 0 else self.keyStore[key][seen][-1]

  • Time: O(1) for set, O(N) for get.

  • Space: O(M * N).

5.2. Binary Search (Sorted Map) - Set O(logN), get O(logN)

from sortedcontainers import SortedDict

class TimeMap:
    def __init__(self):
        self.m = defaultdict(SortedDict)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m[key][timestamp] = value

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.m:
            return ""

        timestamps = self.m[key]
        idx = timestamps.bisect_right(timestamp) - 1

        if idx >= 0:
            closest_time = timestamps.iloc[idx]
            return timestamps[closest_time]
        return ""

  • Time: O(logN) for set, O(logN) for get.

  • Space: O(M * N).

5.3. Binary search in timestamp - Set O(1), Get O(logN)

from collections import defaultdict
import bisect

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

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)      # O(1)
        self.values[key].append(value)         # O(1)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.times:
            return ""
        i = bisect.bisect_right(self.times[key], timestamp) - 1  # O(log N)
        return self.values[key][i] if i >= 0 else ""

  • Time: O(1) for set, O(logN) for get.

  • Space: O(M * N).

6. Dry run examples

Operation times[“foo”] values[“foo”] Result
set("foo", "bar", 1) [1] ["bar"] -
get("foo", 1) [1] ["bar"] "bar"
get("foo", 3) [1] ["bar"] "bar"
set("foo", "bar2", 4) [1, 4] ["bar", "bar2"] -
get("foo", 4) [1, 4] ["bar", "bar2"] "bar2"
get("foo", 5) [1, 4] ["bar", "bar2"] "bar2"
get("foo", 0) [1, 4] ["bar", "bar2"] ""
get("foo", 2) [1, 4] ["bar", "bar2"] "bar"
November 27, 2025