Time Based Key-Value Store

Problem in Plain English

Design a store that saves values for each key at strictly increasing timestamps and returns the latest value at or before a queried time. Unknown keys and times before any save return the empty string.

Problem Statement

Design a time-based key-value data structure that stores multiple values for the same key at different timestamps and retrieves the value at a queried time.

Implement the TimeMap class: TimeMap() initializes the store, set(key, value, timestamp) saves value for key at timestamp, and get(key, timestamp) returns the value with the largest saved time at or before timestamp, or "" when none exists. All set timestamps are strictly increasing.

Constraints

$1 \leq key.length, value.length \leq 100$ .
key and value consist of lowercase English letters and digits.
$1 \leq timestamp \leq 10^7$ .
All timestamps across set calls are strictly increasing; get queries may arrive in any order.
At most $2 \times 10^5$ total calls are made to set and get.

Examples

Example 1

Input: ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

Saving bar at time 1 answers queries at times 1 and 3; after saving bar2 at time 4, queries at times 4 and 5 answer bar2.

Example 2

Input: ["TimeMap", "get", "set", "get"] [[], ["missing", 5], ["a", "x", 2], ["a", 1]]
Output: [null, "", null, ""]

Unknown key missing returns "", and querying a at time 1 before its first save at time 2 also returns "".

Example 3

Input: ["TimeMap", "set", "set", "set", "get", "get", "get", "get"] [[], ["a", "old", 2], ["b", "other", 4], ["a", "new", 8], ["a", 6], ["b", 3], ["a", 8], ["a", 10]]
Output: [null, null, null, null, "old", "", "new", "new"]

The two keys have separate histories. Querying a at 6 chooses old at 2, because new at 8 is in the future; b at 3 has no eligible save. An exact query at 8 and a later query at 10 both choose new.

Intuition

A key keeps a history rather than one current value. Group saves by key and append each timestamp-value pair: globally increasing set times make every individual history sorted too. For foo in Example 1, a query at 3 uses bar from time 1, while a query at 5 uses bar2 from time 4. The answer is the last history entry whose timestamp is at most the query, not the nearest timestamp and not necessarily the newest entry.

Approaches

Linear Scan Get

Solution Details

Reveal Linear Scan Get: intuition, complexity, and code

Intuition

Append each saved pair to its key history and answer a query by walking from newest to oldest. The first timestamp at most the query is the desired version because every entry visited earlier was newer. This avoids searching other keys but may inspect every saved version of the requested key.

Step-by-Step Logic

Create an empty map, then append each set pair to its own key history. Example 1 creates foo -> [[1, "bar"]].
For get, find that key history; an unknown key returns the empty string. Walk the history backward, skipping entries later than the query.
Return the first pair at or before the query. Example 1 queries at 1 and 3 both return bar from time 1.
Keep older versions when a later set arrives. Appending bar2 at time 4 leaves foo -> [[1, "bar"], [4, "bar2"]].
Repeat the backward scan for every get independently. Queries at 4 and 5 both inspect index 1 first and return bar2; return the empty string if the scan exhausts the history.

Why It Works

Each history is sorted in strictly increasing timestamp order because set calls are globally increasing. A reverse walk therefore checks candidates from largest timestamp to smallest. Entries exceeding the query are ineligible; the first eligible entry has the largest timestamp among all remaining entries. If none qualifies, or the key does not exist, no prior value satisfies the query and the empty string is correct. Appending preserves all earlier versions needed for future historical queries.

Dry Run

Linear Scan Get: variable states at each step
Operation	History / index inspected	Comparison / transition	Output so far
TimeMap()	empty map	initialize	[null]
set(foo, bar, 1)	[[1, bar]]	append first pair	[null, null]
get(foo, 1)	i = 0, [1, bar]	1 <= 1; return bar	[null, null, "bar"]
get(foo, 3)	i = 0, [1, bar]	1 <= 3; return bar	[null, null, "bar", "bar"]
set(foo, bar2, 4)	[[1, bar], [4, bar2]]	append, preserve index 0	[null, null, "bar", "bar", null]
get(foo, 4)	i = 1, [4, bar2]	4 <= 4; return bar2	[null, null, "bar", "bar", null, "bar2"]
get(foo, 5)	i = 1, [4, bar2]	4 <= 5; return bar2	[null, null, "bar", "bar", null, "bar2", "bar2"]

Complexity Analysis

Time Complexity

O(m)

Space Complexity

O(N)

Let m be the number of saved versions for the queried key and N the total number of saved pairs. With expected constant-time hash lookup and bounded-length strings, set is amortized O(1), while get is O(m + 1) worst case (O(m) for a nonempty history) and O(1) for a missing key. A before-first query visits every pair; an after-last query visits only one. For S sets and G gets, total expected time is O(S + G + sum of histories scanned), at worst O(S + G(S + 1)); this is a sequence bound, not the cost of one get. Persistent storage is O(N), including at most N keys, while each operation uses O(1) auxiliary space. List growth occasionally costs O(m) but is amortized over appends. Strings are stored as references; counting owned character data adds its total length, still O(N) under the length cap.

Code

Solution.java

1import java.util.Map;2import java.util.List;3import java.util.HashMap;4import java.util.ArrayList;5
6class TimeMap {7    private Map<String, List<Integer>> times = new HashMap<>();8    private Map<String, List<String>> vals = new HashMap<>();9
10    public TimeMap() {11    }12
13    public void set(String key, String value, int timestamp) {14        times.putIfAbsent(key, new ArrayList<>());15        vals.putIfAbsent(key, new ArrayList<>());16        times.get(key).add(timestamp);17        vals.get(key).add(value);18    }19
20    public String get(String key, int timestamp) {21        if (!times.containsKey(key)) {22            return "";23        }24        List<Integer> list = times.get(key);25        List<String> values = vals.get(key);26        for (int i = list.size() - 1; i >= 0; i--) {27            if (list.get(i) <= timestamp) {28                return values.get(i);29            }30        }31        return "";32    }33}

Hints

Hint 1

Strictly increasing set times mean each key list is already sorted, so never sort inside get.

Hint 2

The query asks for the largest saved time at or below the target, which is a rightmost-valid-position search.

Hint 3

Keep a res variable, move left past every valid mid, and return res so gaps between saves resolve to the earlier value.

Edge Cases

Querying an unknown key returns "" without touching any list.
Querying before the first save for a key, such as time 1 after a first save at time 2, returns "".
Querying between two saves or far after the last save returns the earlier or final value respectively.

Common Mistakes and Interview Tips

Accepting the nearest timestamp even when it is larger than the query, which violates the at-or-before rule.
Sorting the history on every get instead of trusting the strictly increasing set order.
Returning the first valid entry from the left rather than continuing right for the largest valid time.
Overwriting a key with only its latest value loses historical answers such as foo at time 3 after the save at time 4.
Using strict timestamp comparison instead of at-or-before rejects exact matches.
Returning as soon as a binary-search midpoint is eligible misses a later eligible version; save the candidate and continue right.
Changing set order or inserting out-of-order timestamps breaks the sorted-history assumption; get query times themselves need not increase.
In Java, the parallel timestamp and value lists must receive one append each per set so their indices remain aligned.

Key Takeaway

When appends arrive in sorted order, group them by key in a hash map and binary search each group for bound queries.