Coding Interview PatternsTime Based Key-Value Store
MediumModified Binary Search

Time Based Key-Value Store

Explanation & Solution

Practice Problem

Description

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 a function that processes a list of operations:

  • set(key, value, timestamp) — Stores the key with the value at the given timestamp.
  • get(key, timestamp) — Returns a value such that set was called previously with timestamp_prev <= timestamp. If there are multiple such values, return the value with the largest timestamp_prev. If there are no values, return "".
Input:ops = ["set", "get", "get", "set", "get", "get"], args = [["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
0
set
1
get
2
get
3
set
4
get
5
get
Output:[null, "bar", "bar", null, "bar2", "bar2"]
0
null
1
bar
2
bar
3
null
4
bar2
5
bar2

Constraints

  • 1 <= key.length, value.length <= 100
  • key and value consist of lowercase English letters and digits
  • 1 <= timestamp <= 10^7
  • All timestamps of set are strictly increasing for the same key
  • At most 2 * 10^5 calls to set and get

Approach

Modified Binary Search pattern

1. Data Structure

  • Use a Map where each key maps to a sorted array of [timestamp, value] pairs.
  • Since set timestamps are strictly increasing per key, the array stays sorted.

2. Set Operation

  • Append [timestamp, value] to the key's array. O(1).

3. Get Operation — Binary Search

  • For the given key and timestamp, binary search the array for the largest timestamp <= target.
  • Set lo = 0, hi = length - 1, track ans.
  • If entries[mid][0] <= timestamp, this is a valid candidate → save it, search higher.
  • Otherwise search lower.

4. Return Results

  • Return the results array with null for set operations and the found value (or "") for get operations.

🧠 Key Insight

  • The binary search finds the rightmost entry with timestamp <= target, which is the classic "upper bound" binary search pattern.
Time
O(log n) per `get`, O(1) per `set`.
Space
O(n) for storing all entries.

Solution Code

Previous
Search Insert Position
Next
Random Pick with Weight