⚡Flashcard Drill➔
NeetCode #287LC-981MediumBinary SearchNC 150NC 250
← Back to All Problems

#287 · #981 · Time Based Key-Value Store(基于时间的键值存储)

📌 Problem Statement & Constraints

Design a time-based key-value store supporting set(key, value, timestamp) and get(key, timestamp), which returns the value with the largest timestamp less than or equal to the given one, or an empty string. Timestamps for the same key are strictly increasing across set calls. Constraints: at most 2 * 10^5 calls.

💡 Core Algorithmic Approaches

  1. For each key, keep two parallel lists: the timestamps in increasing order and the corresponding values.
  2. Because set calls arrive in increasing timestamp order per key, the lists are already sorted -- no explicit sort is needed.
  3. get is then a bisect_right on the timestamp list: the index just before the insertion point holds the answer.
  4. This gives O(log n) per get and O(1) per set.

💻 Benchmark Python3 Implementation

class TimeMap:
    def __init__(self):
        from collections import defaultdict
        self.times = defaultdict(list)     # key -> increasing timestamps
        self.vals = defaultdict(list)      # key -> values aligned with times

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)  # timestamps arrive increasing
        self.vals[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        from bisect import bisect_right
        arr = self.times.get(key)
        if not arr:
            return ""
        i = bisect_right(arr, timestamp)   # first index with time > timestamp
        return self.vals[key][i - 1] if i > 0 else ""

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per set (amortised append) and O(log n) per get.
💾 Space Complexity
O(total number of stored pairs).

⚠️ Interview Pitfalls & Follow-ups

  • Sorting the timestamps on every set: they already arrive in increasing order per key, so sorting is wasted work.
  • Using bisect_left: that finds the first index with time >= timestamp; you want the largest time <= timestamp, hence bisect_right minus one.
  • Forgetting the i == 0 guard: it means no stored timestamp is at or before the query, so the answer is the empty string.
  • Storing (timestamp, value) tuples in one list and using a sentinel for bisection: workable but error-prone; parallel lists are simpler.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems