The Time Based Key-Value Store is a classic design problem that combines hash maps with binary search. The key observation is that timestamps are inserted in strictly increasing order, allowing us to efficiently search for historical values.

Let’s break down the problem, build the intuition, and walk through an optimal solution.

Problem Overview

We’re asked to design a data structure that supports two operations:

  • set(key, value, timestamp) – Store a value for a key at a specific timestamp.
  • get(key, timestamp) – Retrieve the value associated with the largest timestamp that is less than or equal to the given timestamp.

If no such value exists, return an empty string.

Example

set("alice", "happy", 1)
get("alice", 1) → "happy"

get("alice", 2) → "happy"

set("alice", "sad", 3)

get("alice", 3) → "sad"

Notice that when we query timestamp 2, there isn’t an exact match, so we return the most recent value before it.

Key Observation

The problem guarantees that:

Every set() operation for a key is called with strictly increasing timestamps.

This means the timestamps for each key are already sorted.

Instead of sorting them later, we can simply append each new (timestamp, value) pair to a list.

For example:

{
    "alice": [
        (1, "happy"),
        (3, "sad"),
        (8, "excited")
    ]
}

Since the timestamps are already ordered, we can use binary search to answer queries efficiently.

Data Structure

We’ll use a dictionary where:

  • Key → Original key ("alice")
  • Value → List of (timestamp, value) pairs
self.store = {
    "alice": [
        (1, "happy"),
        (3, "sad"),
        (8, "excited")
    ]
}

This gives us:

  • O(1) lookup for the key
  • O(log n) lookup for the correct timestamp

Implementing 

set()

The set() operation is straightforward.

If the key doesn’t exist, initialize an empty list.

Then append the new (timestamp, value) pair.

def set(self, key, value, timestamp):
    if key not in self.store:
        self.store[key] = []

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

Since timestamps are strictly increasing, appending maintains sorted order automatically.

Time Complexity

O(1)

Implementing 

get()

This is where binary search comes in.

Suppose we have:

[(1, happy), (3, sad), (8, excited)]

Now consider:

get("alice", 5)

There is no timestamp 5.

The answer should be the value at timestamp 3.

So we’re really searching for:

The largest timestamp that is less than or equal to the given timestamp.

This is a classic binary search pattern.

Binary Search Walkthrough

Suppose we search for timestamp 5.

Index:       0          1          2
Timestamp:   1          3          8
Value:     happy      sad      excited

Step 1

left = 0
right = 2

mid = 1
timestamp = 3

Since

3 <= 5

this is a valid answer.

Store:

result = "sad"

But there might be a larger valid timestamp, so search the right half.

left = mid + 1

Step 2

left = 2
right = 2

mid = 2
timestamp = 8

Since

8 > 5

this timestamp is too large.

Search the left half.

right = mid - 1

The search ends, and the stored result is "sad".

Why Keep a resultVariable?

During binary search, every timestamp that satisfies:

timestamp <= target

is a potential answer.

Instead of returning immediately, we store it:

result = value

and continue searching to the right, looking for an even larger valid timestamp.

At the end, result contains the value associated with the closest timestamp less than or equal to the target.

Complete Solution

class TimeMap:

    def __init__(self):
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""

        values = self.store[key]

        left = 0
        right = len(values) - 1
        result = ""

        while left <= right:
            mid = (left + right) // 2

            mid_timestamp, value = values[mid]

            if timestamp >= mid_timestamp:
                result = value
                left = mid + 1
            else:
                right = mid - 1

        return result

Complexity Analysis

set()

Appending to the list takes constant time.

Time: O(1)

Space: O(1) (excluding stored data)

get()

Dictionary lookup is constant time.

Binary search over the timestamps takes logarithmic time.

Time: O(log n)

Space: O(1)

Final Thoughts

The elegant part of this problem is recognizing that the timestamps are already sorted because of the problem constraint. That means we don’t need any additional sorting or balanced trees.

The combination of:

  • a hash map for fast key lookup, and
  • binary search on the timestamp list

gives an optimal solution with:

  • set() → O(1)
  • get() → O(log n)

This pattern appears frequently in interview questions whenever data is inserted in sorted order and efficient historical lookups are required. Recognizing when binary search can be applied to append-only data structures is a valuable interview skill that extends well beyond this problem.