Time Based Key Value Store

Asked byAmazonLyftMicrosoftGoogleOracletiktok

Problem

Design a time-based key-value store that can store multiple values for the same key at different timestamps, and retrieve the value associated with a key at (or just before) a given timestamp.

Examples

Example 1

Input:set("foo","bar",1); get("foo",1)

Output:"bar"

Example 2

Input:get("foo",3); set("foo","bar2",4); get("foo",4)

Output:"bar", "bar2"

At timestamp 3 the most recent set was at 1; after set at 4, get(4) returns the newer value.

Constraints

Timestamps for a given key are strictly increasing when set is called.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Binary Search pattern

Repeatedly halve the search space by comparing the middle element to a target, turning an O(n) scan into O(log n). It works on more than sorted arrays — any "answer space" that's monotonic (true…true…false…false) can be binary searched.

Look for this pattern when

The input is sorted, or partially sorted (like a rotated sorted array).
You're minimizing or maximizing a value where "is X feasible?" is easy to check and feasibility is monotonic.

Read the full Binary Search guide →

Video walkthroughs

Original problem on LeetCode ↗