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
- For each key, keep two parallel lists: the timestamps in increasing order and the corresponding values.
- Because
setcalls arrive in increasing timestamp order per key, the lists are already sorted -- no explicit sort is needed. getis then abisect_righton the timestamp list: the index just before the insertion point holds the answer.- This gives O(log n) per
getand O(1) perset.
💻 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 withtime >= timestamp; you want the largest time<= timestamp, hencebisect_rightminus one. - Forgetting the
i == 0guard: 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.