Build a key-value store that remembers every version of a value, stamped with the time it was written. Unlike a normal Map, where setting a key throws away whatever was there before, this store keeps the full history per key. A read isn't "what is the value now?" — it's "what was the value as of time t?" This is the classic time-based key-value store (sometimes called a TimeMap): writes are timestamped, and a read returns the value of the most recent write at or before the time you ask about.
class MapWithHistory {
// Record that `key` had `value` as of `timestamp`.
// For a given key, timestamps arrive strictly increasing.
set(key: string, value: unknown, timestamp: number): void;
// Return the value of the write with the LARGEST timestamp <= `timestamp`.
// Returns undefined when no such write exists: the key was never written,
// or every write for it happened strictly after `timestamp`.
get(key: string, timestamp: number): unknown;
}// A read snaps back to the most recent earlier write.
const store = new MapWithHistory();
store.set('a', 'first', 10);
store.set('a', 'second', 20);
store.get('a', 10); // → 'first' (exact hit on the first write)
store.get('a', 15); // → 'first' (t=15 is between writes; floor is t=10)
store.get('a', 20); // → 'second' (exact hit on the second write)
store.get('a', 99); // → 'second' (after the last write; latest value wins)
store.get('a', 5); // → undefined (before any write for 'a' existed)// Each key keeps its own independent history.
const store = new MapWithHistory();
store.set('x', 'x@1', 1);
store.set('y', 'y@2', 2);
store.set('x', 'x@3', 3);
store.get('x', 2); // → 'x@1' (y's write at t=2 does not leak into x)
store.get('y', 2); // → 'y@2'
store.get('z', 1); // → undefined (unknown key)t, find the write whose timestamp is the largest value that is still <= t. An exact match is just the case where that largest value equals t.undefined. That happens two ways: the key was never written, or its earliest write is strictly later than t.set for a given key uses a larger timestamp than the previous set for that key. You may rely on this — but keeping each key's writes sorted by time is the safe assumption either way.0, '', false, or null must come back as itself. Don't let "falsy value" get confused with "no write found," which is the one case that returns undefined.get should not scan a key's writes one by one. Because each key's list is sorted by time, you can binary search for the floor in O(log n) instead of O(n).You'll store every write per key as a time-sorted list, and answer a read by binary-searching that list for the latest write at or before the queried time.
Think of a price tag that gets re-stickered over time. On Monday a shirt is $40, on Wednesday it's marked down to $30, on Friday it's $25. Now someone asks "what was the price on Thursday?" There's no sticker dated Thursday — so you read the most recent sticker before Thursday, which is Wednesday's $30. That's exactly this store. Each set(key, value, timestamp) adds a dated sticker; each get(key, timestamp) reads the latest sticker dated at or before the time you ask about. If you ask about a time before the very first sticker, there's nothing to read, and the answer is undefined.
Hold three things in your head: the key you're reading, that key's list of writes sorted by time, and the query time you want the value as of. Each key owns a separate list — writes under 'a' never touch the list under 'b'. Because the problem guarantees timestamps for a key arrive strictly increasing, each list is already sorted by time the moment you append to it. That sortedness is the whole game: a sorted list is exactly what binary search needs. The read reduces to one precise question — "what is the largest timestamp in this list that is still less than or equal to the query?" That index is called the floor. Find the floor, return its value; if there's no floor (the query is before every write), return undefined.
The instinct is right — store each key's writes, then look one up by walking the list. The first version usually walks it linearly, scanning from the newest write backward until it finds one that isn't in the future:
class MapWithHistory {
constructor() {
this.store = new Map();
}
set(key, value, timestamp) {
if (!this.store.has(key)) this.store.set(key, []);
this.store.get(key).push({ time: timestamp, value });
}
get(key, timestamp) {
const writes = this.store.get(key) ?? [];
// Walk newest-to-oldest; return the first write that isn't in the future.
for (let i = writes.length - 1; i >= 0; i--) {
if (writes[i].time <= timestamp) return writes[i].value;
}
return undefined;
}
}This is actually correct. It returns the right value in every case: it scans from the end, so the first write it finds with time <= timestamp is the one with the largest qualifying timestamp — the floor. The bug isn't correctness, it's speed. Every get is O(n) in the number of writes for that key. A key written to a few times is fine; a key with tens of thousands of writes that you query repeatedly turns each read into a full backward walk. The list is sorted, and we're ignoring that — we're doing a linear scan over data that's begging for binary search.
class MapWithHistory {
constructor() {
// One entry per key: key -> array of { time, value }, kept sorted by time.
// A Map (not a plain object) keeps arbitrary string keys away from
// inherited names like "toString" and preserves insertion order cleanly.
this.store = new Map();
}
set(key, value, timestamp) {
if (!this.store.has(key)) {
this.store.set(key, []);
}
// Timestamps for a key arrive strictly increasing, so the new write
// belongs at the end and the array stays sorted by time for free.
this.store.get(key).push({ time: timestamp, value });
}
get(key, timestamp) {
const writes = this.store.get(key);
if (writes === undefined) return undefined; // unknown key
// Binary search for the FLOOR: the largest index whose time <= timestamp.
// `lo..hi` is the candidate window; `best` is the answer found so far.
let lo = 0;
let hi = writes.length - 1;
let best = -1;
while (lo <= hi) {
const mid = (lo + hi) >> 1; // floor((lo + hi) / 2), avoids overflow drift
if (writes[mid].time <= timestamp) {
best = mid; // this write qualifies; look right for a later one
lo = mid + 1;
} else {
hi = mid - 1; // this write is in the future; discard it and the right
}
}
return best === -1 ? undefined : writes[best].value;
}
}
module.exports = { MapWithHistory };The structural shift is in get. Instead of walking the list, we binary-search it for the floor. The pattern is a floor binary search, which differs from a plain "find exact value" search in one detail: when the midpoint qualifies (time[mid] <= timestamp), we don't stop — we record it as the best answer so far and keep searching right, because a later write might also qualify and would be a better (larger-timestamp) floor. When the midpoint is in the future, we discard it and everything to its right. The window shrinks by half each step, so a key with n writes answers a read in O(log n) instead of O(n).
Two smaller choices matter. The store is a Map, not a plain {}: a Map handles any string key without colliding with inherited names like toString or constructor, and an unknown key cleanly reports undefined via this.store.get(key). And get distinguishes "key never written" (the Map has no entry → return undefined) from "found a floor" — it never confuses a stored falsy value like 0 or '' with the not-found case, because not-found is signalled by best === -1, not by the value itself.
Trace get('a', 25) against a key written five times — values at times [10, 20, 30, 40, 50]. The floor of 25 is the write at time 20, since 20 is the largest stored time that is still <= 25.
We start with lo = 0, hi = 4, best = -1.
writes: index 0 1 2 3 4
time 10 20 30 40 50
lo=0, hi=4 → mid=2, time[2]=30 30 > 25 → future, hi = mid-1 = 1
lo=0, hi=1 → mid=0, time[0]=10 10 <= 25 → best=0, lo = mid+1 = 1
lo=1, hi=1 → mid=1, time[1]=20 20 <= 25 → best=1, lo = mid+1 = 2
lo=2, hi=1 → lo > hi, loop ends
best = 1 → return writes[1].value // 'y'
The first probe lands on time 30, which is in the future, so the entire right half (indices 2–4) is thrown away in one step. The second probe finds time 10 qualifies and records it, but keeps looking right in case something larger also qualifies. The third probe finds time 20 — larger than 10 and still <= 25 — and records it as the new best. The window then collapses (lo passes hi) and we return writes[1].value. Three probes over five writes; over a thousand writes it would be about ten.
The shape of the floor search is worth isolating on its own, because the "record best, then keep going right" move is what separates it from a textbook exact-match search.
for loop from the end of the list returns the right answer, but it's O(n) per read — and the list is sorted, so you're leaving the O(log n) binary search on the table. On a key with 50,000 writes queried thousands of times, that's the difference between instant and sluggish. Binary search the sorted list; don't walk it.get('a', 25) when writes exist at 20 and 30 must return the 20 write. A search that returns "not found" unless time[mid] === query is wrong here. You want the floor: keep the best qualifying index seen and return it even when no exact match exists.time[mid] <= query, the floor is at mid or later — so set best = mid and move lo = mid + 1 to search right. A common slip is to treat a qualifying midpoint like an exact hit and stop, which returns an earlier write than the true floor. Record and keep going right.0, '', false, or null looks identical to a miss. Decide not-found by index: start best = -1, and only best === -1 means "no floor exists." A real write of 0 then comes back as 0, not undefined.{} for the store. const store = {} already responds to store['toString'] and store['constructor'] with inherited functions, so a key literally named "toString" collides with a method instead of holding a fresh list. A Map has no such inherited keys — every key, including "toString", behaves like any other. (If you must use an object, create it with Object.create(null).)getLatest(key) — the value of the most recent write regardless of time is just the last element of the key's list, writes[writes.length - 1]?.value, in O(1). No search needed, because the list is sorted and the newest write is always at the end.set must place each write at its sorted position. Binary-search for the insert index and splice it in (O(n) per write because of the shift), or keep appending and sort lazily on the first read. The get floor search is unchanged — it only needs the list sorted, not how it got sorted.>= the query) flips the <= to >= and records on the other branch; a range query (every write in [t1, t2]) binary-searches for both endpoints and returns the slice between them. Once you can find a floor in a sorted list, these are small variations on the same loop.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Build a key-value store that remembers every version of a value, stamped with the time it was written. Unlike a normal Map, where setting a key throws away whatever was there before, this store keeps the full history per key. A read isn't "what is the value now?" — it's "what was the value as of time t?" This is the classic time-based key-value store (sometimes called a TimeMap): writes are timestamped, and a read returns the value of the most recent write at or before the time you ask about.
class MapWithHistory {
// Record that `key` had `value` as of `timestamp`.
// For a given key, timestamps arrive strictly increasing.
set(key: string, value: unknown, timestamp: number): void;
// Return the value of the write with the LARGEST timestamp <= `timestamp`.
// Returns undefined when no such write exists: the key was never written,
// or every write for it happened strictly after `timestamp`.
get(key: string, timestamp: number): unknown;
}// A read snaps back to the most recent earlier write.
const store = new MapWithHistory();
store.set('a', 'first', 10);
store.set('a', 'second', 20);
store.get('a', 10); // → 'first' (exact hit on the first write)
store.get('a', 15); // → 'first' (t=15 is between writes; floor is t=10)
store.get('a', 20); // → 'second' (exact hit on the second write)
store.get('a', 99); // → 'second' (after the last write; latest value wins)
store.get('a', 5); // → undefined (before any write for 'a' existed)// Each key keeps its own independent history.
const store = new MapWithHistory();
store.set('x', 'x@1', 1);
store.set('y', 'y@2', 2);
store.set('x', 'x@3', 3);
store.get('x', 2); // → 'x@1' (y's write at t=2 does not leak into x)
store.get('y', 2); // → 'y@2'
store.get('z', 1); // → undefined (unknown key)t, find the write whose timestamp is the largest value that is still <= t. An exact match is just the case where that largest value equals t.undefined. That happens two ways: the key was never written, or its earliest write is strictly later than t.set for a given key uses a larger timestamp than the previous set for that key. You may rely on this — but keeping each key's writes sorted by time is the safe assumption either way.0, '', false, or null must come back as itself. Don't let "falsy value" get confused with "no write found," which is the one case that returns undefined.get should not scan a key's writes one by one. Because each key's list is sorted by time, you can binary search for the floor in O(log n) instead of O(n).You'll store every write per key as a time-sorted list, and answer a read by binary-searching that list for the latest write at or before the queried time.
Think of a price tag that gets re-stickered over time. On Monday a shirt is $40, on Wednesday it's marked down to $30, on Friday it's $25. Now someone asks "what was the price on Thursday?" There's no sticker dated Thursday — so you read the most recent sticker before Thursday, which is Wednesday's $30. That's exactly this store. Each set(key, value, timestamp) adds a dated sticker; each get(key, timestamp) reads the latest sticker dated at or before the time you ask about. If you ask about a time before the very first sticker, there's nothing to read, and the answer is undefined.
Hold three things in your head: the key you're reading, that key's list of writes sorted by time, and the query time you want the value as of. Each key owns a separate list — writes under 'a' never touch the list under 'b'. Because the problem guarantees timestamps for a key arrive strictly increasing, each list is already sorted by time the moment you append to it. That sortedness is the whole game: a sorted list is exactly what binary search needs. The read reduces to one precise question — "what is the largest timestamp in this list that is still less than or equal to the query?" That index is called the floor. Find the floor, return its value; if there's no floor (the query is before every write), return undefined.
The instinct is right — store each key's writes, then look one up by walking the list. The first version usually walks it linearly, scanning from the newest write backward until it finds one that isn't in the future:
class MapWithHistory {
constructor() {
this.store = new Map();
}
set(key, value, timestamp) {
if (!this.store.has(key)) this.store.set(key, []);
this.store.get(key).push({ time: timestamp, value });
}
get(key, timestamp) {
const writes = this.store.get(key) ?? [];
// Walk newest-to-oldest; return the first write that isn't in the future.
for (let i = writes.length - 1; i >= 0; i--) {
if (writes[i].time <= timestamp) return writes[i].value;
}
return undefined;
}
}This is actually correct. It returns the right value in every case: it scans from the end, so the first write it finds with time <= timestamp is the one with the largest qualifying timestamp — the floor. The bug isn't correctness, it's speed. Every get is O(n) in the number of writes for that key. A key written to a few times is fine; a key with tens of thousands of writes that you query repeatedly turns each read into a full backward walk. The list is sorted, and we're ignoring that — we're doing a linear scan over data that's begging for binary search.
class MapWithHistory {
constructor() {
// One entry per key: key -> array of { time, value }, kept sorted by time.
// A Map (not a plain object) keeps arbitrary string keys away from
// inherited names like "toString" and preserves insertion order cleanly.
this.store = new Map();
}
set(key, value, timestamp) {
if (!this.store.has(key)) {
this.store.set(key, []);
}
// Timestamps for a key arrive strictly increasing, so the new write
// belongs at the end and the array stays sorted by time for free.
this.store.get(key).push({ time: timestamp, value });
}
get(key, timestamp) {
const writes = this.store.get(key);
if (writes === undefined) return undefined; // unknown key
// Binary search for the FLOOR: the largest index whose time <= timestamp.
// `lo..hi` is the candidate window; `best` is the answer found so far.
let lo = 0;
let hi = writes.length - 1;
let best = -1;
while (lo <= hi) {
const mid = (lo + hi) >> 1; // floor((lo + hi) / 2), avoids overflow drift
if (writes[mid].time <= timestamp) {
best = mid; // this write qualifies; look right for a later one
lo = mid + 1;
} else {
hi = mid - 1; // this write is in the future; discard it and the right
}
}
return best === -1 ? undefined : writes[best].value;
}
}
module.exports = { MapWithHistory };The structural shift is in get. Instead of walking the list, we binary-search it for the floor. The pattern is a floor binary search, which differs from a plain "find exact value" search in one detail: when the midpoint qualifies (time[mid] <= timestamp), we don't stop — we record it as the best answer so far and keep searching right, because a later write might also qualify and would be a better (larger-timestamp) floor. When the midpoint is in the future, we discard it and everything to its right. The window shrinks by half each step, so a key with n writes answers a read in O(log n) instead of O(n).
Two smaller choices matter. The store is a Map, not a plain {}: a Map handles any string key without colliding with inherited names like toString or constructor, and an unknown key cleanly reports undefined via this.store.get(key). And get distinguishes "key never written" (the Map has no entry → return undefined) from "found a floor" — it never confuses a stored falsy value like 0 or '' with the not-found case, because not-found is signalled by best === -1, not by the value itself.
Trace get('a', 25) against a key written five times — values at times [10, 20, 30, 40, 50]. The floor of 25 is the write at time 20, since 20 is the largest stored time that is still <= 25.
We start with lo = 0, hi = 4, best = -1.
writes: index 0 1 2 3 4
time 10 20 30 40 50
lo=0, hi=4 → mid=2, time[2]=30 30 > 25 → future, hi = mid-1 = 1
lo=0, hi=1 → mid=0, time[0]=10 10 <= 25 → best=0, lo = mid+1 = 1
lo=1, hi=1 → mid=1, time[1]=20 20 <= 25 → best=1, lo = mid+1 = 2
lo=2, hi=1 → lo > hi, loop ends
best = 1 → return writes[1].value // 'y'
The first probe lands on time 30, which is in the future, so the entire right half (indices 2–4) is thrown away in one step. The second probe finds time 10 qualifies and records it, but keeps looking right in case something larger also qualifies. The third probe finds time 20 — larger than 10 and still <= 25 — and records it as the new best. The window then collapses (lo passes hi) and we return writes[1].value. Three probes over five writes; over a thousand writes it would be about ten.
The shape of the floor search is worth isolating on its own, because the "record best, then keep going right" move is what separates it from a textbook exact-match search.
for loop from the end of the list returns the right answer, but it's O(n) per read — and the list is sorted, so you're leaving the O(log n) binary search on the table. On a key with 50,000 writes queried thousands of times, that's the difference between instant and sluggish. Binary search the sorted list; don't walk it.get('a', 25) when writes exist at 20 and 30 must return the 20 write. A search that returns "not found" unless time[mid] === query is wrong here. You want the floor: keep the best qualifying index seen and return it even when no exact match exists.time[mid] <= query, the floor is at mid or later — so set best = mid and move lo = mid + 1 to search right. A common slip is to treat a qualifying midpoint like an exact hit and stop, which returns an earlier write than the true floor. Record and keep going right.0, '', false, or null looks identical to a miss. Decide not-found by index: start best = -1, and only best === -1 means "no floor exists." A real write of 0 then comes back as 0, not undefined.{} for the store. const store = {} already responds to store['toString'] and store['constructor'] with inherited functions, so a key literally named "toString" collides with a method instead of holding a fresh list. A Map has no such inherited keys — every key, including "toString", behaves like any other. (If you must use an object, create it with Object.create(null).)getLatest(key) — the value of the most recent write regardless of time is just the last element of the key's list, writes[writes.length - 1]?.value, in O(1). No search needed, because the list is sorted and the newest write is always at the end.set must place each write at its sorted position. Binary-search for the insert index and splice it in (O(n) per write because of the shift), or keep appending and sort lazily on the first read. The get floor search is unchanged — it only needs the list sorted, not how it got sorted.>= the query) flips the <= to >= and records on the other branch; a range query (every write in [t1, t2]) binary-searches for both endpoints and returns the slice between them. Once you can find a floor in a sorted list, these are small variations on the same loop.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.