← all entries
A-033● Day 332026.06.08mediumleetcode #981neetcode150

Time Based Key-Value Store

#hash-table#string#binary-search#design
↗ leetcode #981 · time-based-key-value-store
01

Problem

· problem
P.033

Time Based Key-Value Store

↗ leetcode #981

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp. Implement the TimeMap class: - TimeMap() Initializes the object of the data structure. - void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp. - String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

constraints
  • · 1 ≤ key.length, value.length ≤ 100
  • · All timestamps in set() are strictly increasing
  • · 1 ≤ timestamp ≤ 10^7
  • · At most 2 × 10^5 calls to set() and get()
// paraphrased summary — see source for full text
examples
example 1input → output
["TimeMap","set","get","get","set","get","get"]
[[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
[null, null, "bar", "bar", null, "bar2", "bar2"]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What should get() return if no set() call has been made for the given key?
  • ☐
    If get() is called with a timestamp between two set() calls, which value should be returned?
  • ☐
    Are timestamps guaranteed to be strictly increasing for each key?
  • ☐
    Can the same key have multiple values at different timestamps?
  • ☐
    Do we need to sort the timestamps after storing them?
  • ☐
    Is it necessary to handle the case where multiple values have the exact same timestamp?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize data structure
○
self.keyStore = {}  # key : list of [val, timestamp]
○
self.keyStore = []
○
self.keyStore = set()
step 2· Check and initialize key│ nested
○
if key not in self.keyStore:
○
if key in self.keyStore:
○
if self.keyStore.get(key):
step 3· Append value-timestamp pair│ nested
○
self.keyStore[key].append([value, timestamp])
○
self.keyStore[key] = [value, timestamp]
○
self.keyStore[key].append(value)
step 4· Initialize search and retrieve values
○
res, values = "", self.keyStore.get(key, [])
○
res, values = None, self.keyStore.get(key, [])
○
values = self.keyStore[key]
step 5· Set binary search bounds
○
l, r = 0, len(values) - 1
○
l, r = 0, len(values)
○
l, r = 1, len(values) - 1
step 6· Binary search: Find largest timestamp <= query│ nested
○
if values[m][1] <= timestamp:
○
if values[m][1] < timestamp:
○
if values[m][0] <= timestamp:
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class TimeMap:
2
    def __init__(self):
3
        """
4
        Initialize your data structure here.
5
        """
6
        self.keyStore = {}  # key : list of [val, timestamp]
7
8
    def set(self, key: str, value: str, timestamp: int) -> None:
9
        if key not in self.keyStore:
10
            self.keyStore[key] = []
11
        self.keyStore[key].append([value, timestamp])
12
13
    def get(self, key: str, timestamp: int) -> str:
14
        res, values = "", self.keyStore.get(key, [])
15
        l, r = 0, len(values) - 1
16
        while l <= r:
17
            m = (l + r) // 2
18
            if values[m][1] <= timestamp:
19
                res = values[m][0]
20
                l = m + 1
21
            else:
22
                r = m - 1
23
        return res
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
["TimeMap","set","get","get","set","get","get"]
[[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
→
[null, null, "bar", "bar", null, "bar2", "bar2"]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.