#981 Time Based Key-Value Store
the problem
In plain words
Build TimeMap, a key-value store that remembers history. set(key, value, timestamp) records that key holds value from that moment on. get(key, timestamp) returns what key held at that time: the value from the latest set call whose timestamp is at most the one asked for. If key has no such version, return the empty string. The timestamps passed to set strictly increase.
in set("foo", "bar", 1), get("foo", 1), get("foo", 3), set("foo", "bar2", 4), get("foo", 4), get("foo", 5)
out null, "bar", "bar", null, "bar2", "bar2"
At time 3 the latest version at or before 3 is the one from time 1.
in set("price", "100", 5), get("price", 4), get("stock", 9)
out null, "", ""
Nothing was set for price before time 5, and stock was never set at all.
- 1 ≤ key.length, value.length ≤ 100 (lowercase letters and digits)
- 1 ≤ timestamp ≤ 10⁷
- The timestamps of set calls strictly increase
- At most 2·10⁵ calls in total
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBinary search (exact & bounds)Ordered map / set (floor & ceiling)
where this runsPostgreSQL's MVCC keeps several versions of a row, so each statement reads the data as it was at some earlier moment — conceptually a lookup by time, like get(key, t) (internally it compares transaction IDs against a snapshot).
Because set timestamps only grow, appending to a key's list keeps it sorted for free. Then "the value at time t" is the floor of t in that list — one binary search.
solutions
From brute force to optimal
Per key, keep the times and values in set order; get walks back from the newest until a time ≤ t.
- set: append the time and the value to the key's two lists.
- get: from the end, return the first value whose time ≤ t; if none, "".
v = versions of that key; asking about the distant past walks all of them.
One time and one value per set call.
// On LeetCode, name this class TimeMap.class TimeMapScan { private final Map<String, List<Integer>> times = new HashMap<>(); // key → its timestamps, in set order private final Map<String, List<String>> values = new HashMap<>(); // key → its values, same positions public void set(String key, String value, int timestamp) { times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp); values.computeIfAbsent(key, k -> new ArrayList<>()).add(value); } public String get(String key, int timestamp) { List<Integer> ts = times.get(key); if (ts == null) return ""; for (int i = ts.size() - 1; i >= 0; i--) { // newest first: O(n) in the worst case if (ts.get(i) <= timestamp) return values.get(key).get(i); } return ""; }}HashMap<String, TreeMap<Integer, String>>; get is floorEntry(t).
- set:
store.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value). - get:
floorEntry(timestamp)— null means "".
TreeMap is a red-black tree: put and floorEntry each walk one root-to-leaf path.
One tree entry (key, value and links) per set call.
// On LeetCode, name this class TimeMap.class TimeMapTree { private final Map<String, TreeMap<Integer, String>> store = new HashMap<>(); public void set(String key, String value, int timestamp) { store.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value); // O(log n) } public String get(String key, int timestamp) { TreeMap<Integer, String> history = store.get(key); if (history == null) return ""; Map.Entry<Integer, String> e = history.floorEntry(timestamp); // largest time ≤ timestamp: O(log n) return e == null ? "" : e.getValue(); }}Per key, two ArrayLists (times, values). Appending keeps times sorted; get binary-searches the last time ≤ t.
- set: computeIfAbsent the key's History; append the time and the value.
- get: lo = 0, hi = size − 1, found = −1. While lo ≤ hi: mid; if times[mid] ≤ t then found = mid, lo = mid + 1; else hi = mid − 1.
- Return found == −1 ? "" : values[found].
Appending to an ArrayList is amortized O(1); the search halves the range each step.
Two compact list slots per set call — no tree nodes.
class TimeMap { private static class History { final List<Integer> times = new ArrayList<>(); // increasing, because set() timestamps only grow final List<String> values = new ArrayList<>(); // values.get(i) was set at times.get(i) } private final Map<String, History> store = new HashMap<>(); public void set(String key, String value, int timestamp) { History h = store.computeIfAbsent(key, k -> new History()); h.times.add(timestamp); // appending keeps the list sorted h.values.add(value); } public String get(String key, int timestamp) { History h = store.get(key); if (h == null) return ""; int lo = 0, hi = h.times.size() - 1, found = -1; while (lo <= hi) { int mid = (lo + hi) >>> 1; if (h.times.get(mid) <= timestamp) { found = mid; // a candidate; a later one may fit too lo = mid + 1; } else { hi = mid - 1; // too new } } return found == -1 ? "" : h.values.get(found); }}Dry run
in the room
How to say it in the interview
talk track
- Ask: do set timestamps always increase? (Here, yes.) That is what makes set O(1).
- Name the query: the largest time ≤ t is a floor — TreeMap.floorEntry, or a binary search on a sorted list.
- Write the binary search with a
foundvariable, so you never have to reason about wherelostops. - Mention TreeMap as the answer if timestamps could arrive out of order.
traps
- Searching for the first time ≥ t (ceiling) instead of the last time ≤ t (floor).
- Returning
nullinstead of""for a missing key or a time before the first version. Collections.binarySearchreturns −(insertion point) − 1 when t isn't stored; the floor is then at insertion point − 1.- Sorting a key's list on every set — it is already sorted.
what they ask next
Follow-ups
Timestamps can arrive out of order?
Appending no longer keeps the list sorted. Use a TreeMap per key: put and floorEntry are both O(log v).
Drop versions older than time T to save memory?
With a TreeMap, headMap(T).clear(). With lists, keep a start index per key and move it forward (rebuild the list once in a while).
Snapshots of a whole array (LC 1146 Snapshot Array)?
Same idea per index: each index keeps (snapshot id, value) pairs in increasing snapshot order, and get is a floor search by snapshot id.
before you submit
Edge cases to test
- get for a key that was never set → "".
- get with t before the key's first version → "".
- t exactly equal to a stored time returns that version.
- Two keys with interleaved times never mix: each key has its own history.
practise next
Similar problems
- #35Search Insert PositionEasyin Binary Search
- #729My Calendar IMediumin BST
- #362Design Hit CounterMediumin QueuesLeetCode Premium