Time Based Key-Value Store

Q: Why is this a good infra interview question?

It is the core of any versioned configuration or metrics store: "what was this feature flag, replica count or DNS record at the time the incident started?" Point-in-time lookup by binary search over an append-only history is how many such systems answer that.

Q: What if timestamps could arrive out of order?

Appending would no longer keep the list sorted. You would insert in sorted position (O(k) for a Python list), or use a sorted structure such as Java's TreeMap with floorEntry(timestamp), which makes both operations O(log k).

Q: Why store timestamps and values in separate lists in Python?

bisect_right then works on plain integers. Bisecting a list of tuples also works but needs a sentinel value in the probe tuple to compare correctly.

mediumBinary search Must-do

Design a class TimeMap that stores several values for the same key, each tagged with a timestamp, and can answer "what was the value at time t?".

TimeMap() creates an empty store.
set(key, value, timestamp) records value for key at timestamp.
get(key, timestamp) returns the value that was set for key with the largest timestamp that is less than or equal to timestamp. If there is no such value (unknown key, or every stored timestamp is later), return "".

Across all set calls, timestamps arrive in strictly increasing order.

Examples

Example 1

Input: set("config", "v1", 10) set("config", "v2", 25) get("config", 5) get("config", 10) get("config", 30)

Output: "" "v1" "v2"

Explanation: At time 5 nothing had been set yet. At 10 the value was v1. At 30 the latest value, v2, applies.

Example 2

Input: set("replicas", "3", 4) get("replicas", 20) get("image", 20)

Output: "3" ""

Explanation: image was never set.

Hints

Approach

Keep the same per-key lists, but binary-search them in get.

For each key, store two parallel lists: timestamps and values. set appends to both; the timestamp list stays sorted because timestamps only increase.
In get, find i, the number of stored timestamps that are <= t. That is the upper bound of t: the first index whose timestamp is greater than t.
If i == 0, nothing qualifies: return "". Otherwise return values[i - 1].

get drops to O(log k). In Python, bisect_right computes the upper bound directly.

ComplexityTime set O(1), get O(log k)Space O(total entries)

Python

from bisect import bisect_right
 
 
class TimeMap:
    def __init__(self):
        self.times = {}   # key -> sorted list of timestamps
        self.values = {}  # key -> values, parallel to times
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times.setdefault(key, []).append(timestamp)
        self.values.setdefault(key, []).append(value)
 
    def get(self, key: str, timestamp: int) -> str:
        ts = self.times.get(key)
        if not ts:
            return ""
        i = bisect_right(ts, timestamp)  # count of timestamps <= timestamp
        return self.values[key][i - 1] if i else ""

Follow-up questions

Add delete(key, timestamp) that hides all values set at or after a given time.
Memory is limited: keep only the last n versions of each key.

Frequently asked questions

It is the core of any versioned configuration or metrics store: "what was this feature flag, replica count or DNS record at the time the incident started?" Point-in-time lookup by binary search over an append-only history is how many such systems answer that.

Appending would no longer keep the list sorted. You would insert in sorted position (O(k) for a Python list), or use a sorted structure such as Java's TreeMap with floorEntry(timestamp), which makes both operations O(log k).

bisect_right then works on plain integers. Bisecting a list of tuples also works but needs a sentinel value in the probe tuple to compare correctly.

Problem statement