Time Based Key-Value Store

Q: How do you solve Time Based Key-Value Store?

Store for each key a list of (value, timestamp) pairs sorted by timestamp. For get operations, perform a binary search on the timestamps to find the rightmost timestamp less than or equal to the query timestamp. Return the corresponding value or an empty string if none exists. This approach guarantees O(log n) time per get and O(1) amortized time per set.

Q: What is the time complexity of Time Based Key-Value Store?

O(log n) per get, O(1) amortized per set. Each get operation performs a binary search on the sorted list of timestamps for a key, which takes O(log n) time where n is the number of timestamps for that key. Each set appends to the list in O(1) amortized time.

Q: What pattern does Time Based Key-Value Store use?

The Pattern: Binary Search (Rightmost Element Search in Sorted Array) The Heuristic: When searching for the largest element less than or equal to a target in a sorted list, use binary search to find the rightmost position where the element satisfies the condition, enabling O(log n) retrieval.

Medium Modified Binary Search

Problem

Implement a time-based key-value store with set and get operations, where get returns the value associated with a key at the largest timestamp less than or equal to the given timestamp.

All timestamps for set operations are strictly increasing for each key.
1 ≤ key.length, value.length ≤ 100
1 ≤ timestamp ≤ 10⁷
At most 2 * 10⁵ calls will be made to set and get.

Example

Input: set("foo", "bar", 1), get("foo", 1), get("foo", 3), set("foo", "bar2", 4), get("foo", 4), get("foo", 5)

Output: [null, "bar", "bar", null, "bar2", "bar2"]

Initially, set("foo", "bar", 1) stores the value "bar" at timestamp 1. get("foo", 1) returns "bar" because the timestamp matches exactly. get("foo", 3) returns "bar" because the largest timestamp less than or equal to 3 is 1. Then set("foo", "bar2", 4) stores "bar2" at timestamp 4. get("foo", 4) returns "bar2" (exact match), and get("foo", 5) returns "bar2" because 4 is the largest timestamp <= 5.

Approach

Straightforward Solution

A naive approach would scan all stored timestamps for a key linearly to find the largest timestamp <= query timestamp, resulting in O(n) time per get call, which is inefficient for large inputs.

Core Observation

The problem requires retrieving the value associated with the largest timestamp less than or equal to a given timestamp. Since timestamps for each key are strictly increasing, the stored values form a sorted list by timestamp, enabling efficient binary search.

Path to Optimal

Preview

Recognizing that timestamps are strictly increasing for each key, the stored values can be maintained as a sorted list. This allows binary search to find the correct timestamp in O(log n) time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Store for each key a list of (value, timestamp) pairs sorted by timestamp. For get operations, perform a binary search on the timestamps to find the rightmost timestamp less than or equal to the query timestamp…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n) per get, O(1) amortized per set

Each get operation performs a binary search on the sorted list of timestamps for a key, which takes O(log n) time where n is the number of timestamps for that key. Each set appends to the list in O(1) amortized time.

Space

O(n)

All set operations store values and timestamps in lists, requiring O(n) space proportional to the number of set calls. No additional significant auxiliary space is used.

Pattern Spotlight

Binary Search (Rightmost Element Search in Sorted Array)

When searching for the largest element less than or equal to a target in a sorted list, use binary search to find the rightmost position where the element satisfies the condition, enabling O(log n) retrieval.

Solution

Python

1class TimeMap:
  def __init__(self):
      self.store = {}
4
  def set(self, key: str, value: str, timestamp: int) -> None:
      if key not in self.store:
          self.store[key] = []
      self.store[key].append([value, timestamp])
9
  def get(self, key: str, timestamp: int) -> str:
      res = ""
      values = self.store.get(key, [])
      
      l, r = 0, len(values) - 1
      while l <= r:
          m = (l + r) // 2
          if values[m][1] <= timestamp:
              res = values[m][0]
              l = m + 1
          else:
              r = m - 1
      
      return res

Step-by-Step Solution

Store Values and Timestamps in Sorted Lists per Key

3self.store = {}
6if key not in self.store:
7    self.store[key] = []
8self.store[key].append([value, timestamp])

Objective

To maintain a mapping from keys to lists of (value, timestamp) pairs sorted by timestamp.

Key Insight

Since timestamps are strictly increasing for each key, appending new (value, timestamp) pairs to the list preserves sorted order. This structure enables efficient binary search later without additional sorting overhead.

Interview Quick-Check

Core Logic

Appending values with strictly increasing timestamps ensures the list remains sorted, which is essential for binary search.

Common Pitfalls & Bugs

Failing to maintain sorted order would prevent binary search from working correctly.

Perform Binary Search to Retrieve Value at or Before Timestamp

To efficiently find the value associated with the largest timestamp less than or equal to the query timestamp using binary search.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 8 Critical

self.store[key].append([value, timestamp])

Append the new value-timestamp pair.

Appending works because timestamps are inserted in increasing order, so the per-key history stays sorted.

Line 17 Critical

if values[m][1] <= timestamp:

Check whether the midpoint timestamp is valid for the query.

A midpoint timestamp less than or equal to the query is a valid candidate answer.

Line 18 Critical

res = values[m][0]

Update the result with the midpoint value.

When the midpoint timestamp is valid, its value becomes the best answer seen so far.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why is binary search the appropriate method to find the value for a given timestamp in this problem?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Time Based Key-Value Store from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Time Based Key-Value Store drill

or drill a free problem

1	`class TimeMap:`
2	`def __init__(self):`
3	`self.store = {}`
4
5	`def set(self, key: str, value: str, timestamp: int) -> None:`
6	`if key not in self.store:`
7	`self.store[key] = []`
8	`self.store[key].append([value, timestamp])`
9
10	`def get(self, key: str, timestamp: int) -> str:`
11	`res = ""`
12	`values = self.store.get(key, [])`
13
14	`l, r = 0, len(values) - 1`
15	`while l <= r:`
16	`m = (l + r) // 2`
17	`if values[m][1] <= timestamp:`
18	`res = values[m][0]`
19	`l = m + 1`
20	`else:`
21	`r = m - 1`
22
23	`return res`

3	`self.store = {}`
6	`if key not in self.store:`
7	`self.store[key] = []`
8	`self.store[key].append([value, timestamp])`