Frequently Asked — This problem has been reported multiple times in recent Amazon interviews. Prioritize this during revision.

Time Based Key-Value Store

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the value at a certain timestamp.

Implement the TimeMap class:

• TimeMap() — Initializes the data structure.
• set(key, value, timestamp) — Stores the key-value pair along with the given timestamp.
• get(key, timestamp) — Returns the value associated with key such that the timestamp of the stored value is the largest timestamp less than or equal to the given timestamp. If no such value exists, return "".

Example:

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

Output: [null, null, "bar", "bar", null, "bar2"]

Explanation:
- set("foo", "bar", 1) → store "bar" at timestamp 1
- get("foo", 1) → return "bar" (exact match)
- get("foo", 3) → return "bar" (timestamp 1 <= 3, and it's the latest)
- set("foo", "bar2", 4) → store "bar2" at timestamp 4
- get("foo", 4) → return "bar2" (exact match)

Constraints:

• 1 <= key.length, value.length <= 100
• 1 <= timestamp <= 10^7
• All timestamps for set are strictly increasing for each key.
• At most 2 * 10^5 calls to set and get.

Difficulty: Medium (LC 981)

---

Pattern Recognition

• What is the input structure? A stream of set/get operations with string keys and integer timestamps.
• What are we optimizing? Fast retrieval of the most recent value at or before a given timestamp.
• What pattern does this fit? HashMap + Binary Search. The HashMap gives O(1) key lookup. Since timestamps arrive in sorted order, binary search finds the floor timestamp in O(log n).
• Why does this pattern fit? The constraint says timestamps for each key are strictly increasing, so the values list per key is already sorted. Binary search is the natural choice for "find the largest element <= target" in a sorted array.

---

Approach

Brute Force — Linear Scan

Store all (timestamp, value) pairs per key. For get, scan backward through the list to find the latest timestamp <= target.

class TimeMap:
    store = {}

    set(key, value, timestamp):
        store[key].append((timestamp, value))

    get(key, timestamp):
        if key not in store: return ""
        for i in reverse(store[key]):
            if i.timestamp <= timestamp:
                return i.value
        return ""

Time: set is O(1), get is O(n) where n is the number of entries for that key. Space: O(total entries). Why insufficient: With up to 2 * 10^5 calls, get operations can degrade to O(n) each — too slow.

Optimal — HashMap + Binary Search

Key Insight: Since timestamps arrive in strictly increasing order, the list of (timestamp, value) pairs per key is already sorted. Use bisect_right to find the insertion point for the target timestamp, then the answer is at index insertion_point - 1.

Step-by-step:

1. Use a dictionary mapping each key to a list of (timestamp, value) tuples.
2. set: Append (timestamp, value) to the list for that key. O(1).
3. get: Use binary search on the timestamps list.
   • Find the rightmost timestamp <= target using bisect_right(timestamps, target).
   • If insertion point > 0, return the value at insertion_point - 1.
   • Otherwise, return "".

class TimeMap:
    store = defaultdict(list)

    set(key, value, timestamp):
        store[key].append((timestamp, value))

    get(key, timestamp):
        entries = store[key]
        idx = bisect_right(entries, (timestamp, chr(127)))  # search by timestamp
        if idx > 0: return entries[idx - 1].value
        return ""

Time: set is O(1), get is O(log n). Space: O(total entries).

---

Walkthrough

Operations:

set("foo", "bar", 1)
set("foo", "bar2", 4)
set("foo", "bar3", 7)
get("foo", 5)

State after all sets:

store = {"foo": [(1, "bar"), (4, "bar2"), (7, "bar3")]}

Processing get("foo", 5):

Timestamps list: [1, 4, 7] Target: 5

Step	Action	Result
1	Extract timestamps: [1, 4, 7]	—
2	bisect_right([1, 4, 7], 5)	Returns 2 (5 would be inserted at index 2)
3	idx = 2 > 0 → return entries[1]	Value at index 1 = "bar2"

Answer: "bar2" — timestamp 4 is the largest timestamp <= 5.

Processing get("foo", 0):

Step	Action	Result
1	bisect_right([1, 4, 7], 0)	Returns 0
2	idx = 0, not > 0	Return ""

Answer: "" — no timestamp <= 0 exists.

---

Implementation

TypeScript

class TimeMap {
    private store: Map<string, [number, string][]> = new Map();

    set(key: string, value: string, timestamp: number): void {
        if (!this.store.has(key)) this.store.set(key, []);
        this.store.get(key)!.push([timestamp, value]);
    }

    get(key: string, timestamp: number): string {
        const entries = this.store.get(key);
        if (!entries || entries.length === 0) return "";

        // Binary search for rightmost timestamp <= target
        let lo = 0, hi = entries.length - 1, result = "";
        while (lo <= hi) {
            const mid = (lo + hi) >> 1;
            if (entries[mid][0] <= timestamp) {
                result = entries[mid][1];
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return result;
    }
}

C++

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    void set(const string& key, const string& value, int timestamp) {
        store[key].emplace_back(timestamp, value);
    }

    string get(const string& key, int timestamp) {
        auto it = store.find(key);
        if (it == store.end() || it->second.empty()) return "";

        auto& entries = it->second;
        // upper_bound finds first entry with timestamp > target
        // decrement to get the rightmost entry with timestamp <= target
        auto ub = upper_bound(entries.begin(), entries.end(),
                              make_pair(timestamp, string(1, 127)));
        if (ub == entries.begin()) return "";
        return prev(ub)->second;
    }
};

Alternative — manual binary search (shows understanding):

TypeScript

class TimeMapManual {
    private store: Map<string, [number, string][]> = new Map();

    set(key: string, value: string, timestamp: number): void {
        if (!this.store.has(key)) this.store.set(key, []);
        this.store.get(key)!.push([timestamp, value]);
    }

    get(key: string, timestamp: number): string {
        const entries = this.store.get(key);
        if (!entries || entries.length === 0) return "";

        let lo = 0, hi = entries.length - 1;
        let result = "";

        while (lo <= hi) {
            const mid = (lo + hi) >> 1;
            if (entries[mid][0] <= timestamp) {
                result = entries[mid][1]; // Candidate answer
                lo = mid + 1;            // Search for a later timestamp
            } else {
                hi = mid - 1;
            }
        }

        return result;
    }
}

C++

class TimeMapManual {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    void set(const string& key, const string& value, int timestamp) {
        store[key].emplace_back(timestamp, value);
    }

    string get(const string& key, int timestamp) {
        auto it = store.find(key);
        if (it == store.end() || it->second.empty()) return "";

        auto& entries = it->second;
        int lo = 0, hi = (int)entries.size() - 1;
        string result;

        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (entries[mid].first <= timestamp) {
                result = entries[mid].second; // Candidate answer
                lo = mid + 1;                 // Search for a later timestamp
            } else {
                hi = mid - 1;
            }
        }

        return result;
    }
};

Watch out:

1. Using bisect_left instead of bisect_right. You want the rightmost entry with timestamp <= target. bisect_right gives you the insertion point after all equal elements, so idx - 1 is the correct floor. Using bisect_left would miss exact matches if there are duplicates (though the problem guarantees unique timestamps per key).
2. Not handling the case where the key does not exist. Return "" when the key is missing or when all timestamps are greater than the target.
3. The chr(127) trick in tuple comparison. When using bisect_right on (timestamp, value) tuples, you search for (timestamp, chr(127)) — a string guaranteed to be lexicographically larger than any value — to find the position after all entries with the exact target timestamp.

---

Complexity Analysis

	Time (set)	Time (get)	Space
Brute Force (Linear Scan)	O(1)	O(n)	O(total entries)
Optimal (HashMap + Binary Search)	O(1)	O(log n)	O(total entries)

Bottleneck: The space is unavoidable — you must store all entries. The get operation's O(log n) binary search is optimal given that you need to support arbitrary timestamp queries. You cannot do better without additional assumptions.

---

Edge Cases

1. get with a timestamp before any stored timestamp — Should return "". Your binary search must handle idx = 0.
2. get with an exact timestamp match — Should return that value. Verify your binary search returns the right element.
3. Single entry per key — get should return it for any timestamp >= it, "" for any timestamp < it.
4. Very large number of entries per key (10^5) — Binary search handles this in ~17 comparisons. Linear scan would time out.
5. Multiple keys — Ensure key isolation. Operations on "foo" should not affect "bar".
6. get on a non-existent key — Return "" without error. defaultdict(list) handles this naturally.

---

Related Problems

• LC 729 — My Calendar I — Sorted list + binary search for interval queries on a timeline.
• LC 352 — Data Stream as Disjoint Intervals — Maintaining sorted data with efficient queries.
• LC 1146 — Snapshot Array — Similar versioned data structure with binary search on snapshots.
• LC 362 — Design Hit Counter — Time-based data structure with range queries.

---

What is Expected at Each Level

Junior: Identify that a HashMap is needed. Implement the linear scan version. Recognize that binary search can improve get. May need guidance on bisect usage.

Mid-level: Immediately see HashMap + Binary Search. Write clean code using bisect_right. Handle all edge cases. Discuss why timestamps being sorted is critical to the solution.

Senior: Write the solution quickly and discuss extensions: What if timestamps are not sorted? (Use a balanced BST like SortedList.) What about concurrent access? (Read-write locks, CAS for append.) Discuss memory optimization for high-throughput systems (e.g., TTL eviction, compaction). Mention that this is essentially a simplified LSM-tree or MVCC pattern used in real databases.