250. Time-Based Key-Value Store

Why this mechanism works

Append-only sorted histories make each query an upper-bound search. Find the first timestamp greater than the query; the previous entry is the newest eligible value. Searching timestamps directly avoids constructing a temporary timestamp list on every get and naturally handles repeated timestamps by selecting the last eligible occurrence.

State and boundaries

Each history is ordered by timestamp and insertion order within ties. During search, [left,right) contains the first-greater boundary; indices below left are eligible and indices at or above right are too late.

Protocol

1. Append each set to its key history, enforcing nondecreasing time.
2. On get use an empty history for unknown keys.
3. Binary-search the first timestamp >query.
4. Move right=mid for a too-late entry, otherwise left=mid+1.
5. Return history[left-1]'s value if left>0, else ''.

Visualization

history times [1,4,4,9], query 4
first timestamp >4 is index 3
answer index 2: latest value stored at time 4
query 0 gives boundary 0 -> no eligible value

Python implementation

from structures import run_operations

class TimeMap:
    def __init__(self):
        self.histories = {}

    def set(self, key, value, timestamp):
        history = self.histories.setdefault(key, [])
        if history and timestamp < history[-1][0]:
            raise ValueError('timestamps must be nondecreasing per key')
        history.append((timestamp, value))

    def get(self, key, timestamp):
        history = self.histories.get(key, ())
        left, right = 0, len(history)
        while left < right:
            mid = (left + right) // 2
            if history[mid][0] > timestamp:
                right = mid
            else:
                left = mid + 1
        return history[left - 1][1] if left else ''

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 __init__: self.histories = {}
self=TimeMap{'histories':{}}

L8 set: history = self.histories.setdefault(key, [])
self=TimeMap{'histories':{...:...}}; key='x'; value='early'; timestamp=1; history=[]

L11 set: history.append((timestamp, value))
self=TimeMap{'histories':{...:...}}; key='x'; value='early'; timestamp=1; history=[(1, 'early')]

L8 set: history = self.histories.setdefault(key, [])
self=TimeMap{'histories':{...:...}}; key='x'; value='new'; timestamp=4; history=[(1, 'early')]

L11 set: history.append((timestamp, value))
self=TimeMap{'histories':{...:...}}; key='x'; value='new'; timestamp=4; history=[(1, 'early'), (4, 'new')]

L14 get: history = self.histories.get(key, ())
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=3; history=[(1, 'early'), (4, 'new')]

L15 get: left, right = 0, len(history)
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=3; history=[(1, 'early'), (4, 'new')]; left=0; right=2

L17 get: mid = (left + right) // 2
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=3; history=[(1, 'early'), (4, 'new')]; left=0; right=2; mid=1

... 9 intermediate state changes omitted ...

L17 get: mid = (left + right) // 2
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=0; history=[(1, 'early'), (4, 'new')]; left=0; right=2; mid=1

L19 get: right = mid
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=0; history=[(1, 'early'), (4, 'new')]; left=0; right=1; mid=1

L17 get: mid = (left + right) // 2
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=0; history=[(1, 'early'), (4, 'new')]; left=0; right=1; mid=0

L19 get: right = mid
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=0; history=[(1, 'early'), (4, 'new')]; left=0; right=0; mid=0

L5 __init__: self.histories = {}
self=TimeMap{'histories':{}}

L8 set: history = self.histories.setdefault(key, [])
self=TimeMap{'histories':{...:...}}; key='x'; value='a'; timestamp=4; history=[]

L11 set: history.append((timestamp, value))
self=TimeMap{'histories':{...:...}}; key='x'; value='a'; timestamp=4; history=[(4, 'a')]

L8 set: history = self.histories.setdefault(key, [])
self=TimeMap{'histories':{...:...}}; key='x'; value='b'; timestamp=4; history=[(4, 'a')]

L11 set: history.append((timestamp, value))
self=TimeMap{'histories':{...:...}}; key='x'; value='b'; timestamp=4; history=[(4, 'a'), (4, 'b')]

L14 get: history = self.histories.get(key, ())
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=4; history=[(4, 'a'), (4, 'b')]

L15 get: left, right = 0, len(history)
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=4; history=[(4, 'a'), (4, 'b')]; left=0; right=2

L17 get: mid = (left + right) // 2
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=4; history=[(4, 'a'), (4, 'b')]; left=0; right=2; mid=1

L21 get: left = mid + 1
self=TimeMap{'histories':{...:...}}; key='x'; timestamp=4; history=[(4, 'a'), (4, 'b')]; left=2; right=2; mid=1

Why the solution is correct

Sorted timestamps create an eligible-then-too-late predicate boundary. Each branch discards only indices whose relation to that boundary is known, preserving the half-open candidate interval and reducing its width. At convergence, left-1 is exactly the last eligible entry, including the latest insertion among equal timestamps.

Time and space

Expected amortized O(1) set and O(log(h+1)) get for a key with h versions, with O(total_versions) storage. Dictionary access assumes expected constant time.

Common mistakes

Returning the lower-bound entry can select a future value or the first tie. Building [time for time,value in history] inside get makes the query linear. Out-of-order sets violate the append-only search invariant.

Reasoning card

Transfer exercise

Support out-of-order timestamps. Compare sorted-list insertion, balanced search trees and batched sorting in terms of write/read costs.