AlgoMaster Logo

Time Based Key-Value Store

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We need to build a data structure that associates keys with values, but each key can hold multiple values stored at different points in time. A get does not return the latest value. It returns the value that was current at a specific timestamp, meaning the value set at the largest timestamp that does not exceed the query timestamp.

This behaves like version control for a key-value store. Each set call creates a new version, and each get call asks what the value was at a given point in time. When no exact match exists, the answer is the most recent version before that time.

The timestamps for set calls arrive strictly increasing. The timestamps stored for each key are therefore already sorted, which makes binary search possible instead of scanning every entry.

Key Constraints:

  • 1 <= timestamp <= 10^7 and timestamps are strictly increasing. The timestamps stored per key are guaranteed sorted, so we never sort anything ourselves.
  • At most 2 * 10^5 calls to set and get. If every set targets one key and every get scans that key's full history, the total cost approaches 10^5 * 10^5 = 10^10 operations, too slow for the time limit. The get path needs to be sublinear.
  • key.length, value.length <= 100. String comparisons and copies are bounded by a small constant, so the running time depends on the lookup strategy rather than on string handling.

Approach 1: Hash Map with Linear Scan

Intuition

Store each key's history as a list of (timestamp, value) pairs inside a hash map. For set, append to the list. For get, scan backward through the list and return the first entry whose timestamp does not exceed the query timestamp.

Because timestamps arrive in strictly increasing order, each list is already sorted ascending. Scanning from the end reaches the largest timestamps first, so the first entry that satisfies timestamp <= query is also the largest such timestamp. That makes it the correct answer, and we can stop immediately.

Algorithm

  1. Initialize a hash map where each key maps to a list of (timestamp, value) pairs.
  2. For set(key, value, timestamp): append (timestamp, value) to the list for key.
  3. For get(key, timestamp): look up the list for key. Iterate backward through the list. Return the value of the first entry whose timestamp is less than or equal to timestamp. If no such entry exists, return "".

Example Walkthrough

1Initial: store is empty
1/6

Code

The linear scan ignores the sorted order of the timestamps. The next approach exploits that order with binary search, cutting get from O(n) to O(log n).

Approach 2: Hash Map with Binary Search (Optimal)

Intuition

The list of timestamps for each key is sorted ascending, so binary search replaces the backward scan. Instead of walking through thousands of entries, the search narrows to the right index in O(log n) time.

The query is a "floor" search: find the largest timestamp less than or equal to the target. We maintain a range [left, right] and check the middle element. If timestamps[mid] <= target, that timestamp is a valid candidate, but a larger valid one may sit to its right, so we record mid and move left = mid + 1. If timestamps[mid] > target, the middle timestamp is too new, so we move right = mid - 1. When left passes right, the last recorded candidate is the answer.

Algorithm

  1. Initialize a hash map where each key maps to a list of (timestamp, value) pairs.
  2. For set(key, value, timestamp): append (timestamp, value) to the list for key.
  3. For get(key, timestamp):
    • Look up the list for key. If the key doesn't exist, return "".
    • Binary search the timestamps for the largest one less than or equal to timestamp.
    • Set left = 0, right = list.size() - 1, result = -1.
    • While left <= right: compute mid = (left + right) / 2. If timestamps[mid] <= timestamp, set result = mid and move left = mid + 1. Otherwise, move right = mid - 1.
    • If result != -1, return the value at index result. Otherwise, return "".

Example Walkthrough

1Initial: no timestamps stored for key "foo"
1/7

Code