Time Based Key-Value Store

Mediumbinary-searchhash-tabledesign
Category: Binary Search
Companies that ask this question:
AmazonGoogleFacebook
LeetCode →NeetCode →

Approach

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 time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

  • TimeMap() Initializes the object
  • void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp
  • String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

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"]

Explanation:
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store "bar" at time 1
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar" (no value at 3, return value at 1)
timeMap.set("foo", "bar2", 4); // store "bar2" at time 4
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2" (no value at 5, return value at 4)

Intuition

For each key, we store a list of (timestamp, value) pairs. Since set calls have increasing timestamps (per problem constraint), this list is sorted by timestamp.

For get(key, timestamp), we need to find the largest timestamp ≤ target timestamp. This is a binary search problem!

Pattern Recognition

This is Binary Search + HashMap with:

  • Hash map for key → list of (timestamp, value)
  • Binary search to find largest timestamp ≤ target
  • Design problem requiring efficient data structure

Approach

  1. Data Structure:

    • HashMap<String, List<Pair<Integer, String>>>
    • Each key maps to list of (timestamp, value) pairs

  2. set(key, value, timestamp):

    • Add (timestamp, value) to list for this key
    • O(1) append operation

  3. get(key, timestamp):

    • If key doesn't exist: return ""
    • Binary search on timestamps to find largest t ≤ timestamp
    • Return corresponding value
    • O(log n) where n = number of values for this key

Binary Search Logic:

  • Find rightmost position where timestamps[i] <= target
  • This gives us the most recent value before or at target time

Edge Cases

  • Key doesn't exist
  • Timestamp before any stored value
  • Timestamp matches exactly
  • Timestamp after all values
  • Multiple values for same key

Complexity Analysis

  • set: O(1)

    • Append to list

  • get: O(log n) where n = number of timestamps for the key

    • Binary search on sorted timestamps

  • Space: O(m * n) where m = number of unique keys, n = average values per key

Solution

java
1class TimeMap {
2    private Map<String, List<Pair>> map;
3
4    private static class Pair {
5        int timestamp;
6        String value;
7
8        Pair(int timestamp, String value) {
9            this.timestamp = timestamp;
10            this.value = value;
11        }
12    }
13
14    public TimeMap() {
15        map = new HashMap<>();
16    }
17
18    public void set(String key, String value, int timestamp) {
19        map.putIfAbsent(key, new ArrayList<>());
20        map.get(key).add(new Pair(timestamp, value));
21    }
22
23    public String get(String key, int timestamp) {
24        if (!map.containsKey(key)) {
25            return "";
26        }
27
28        List<Pair> list = map.get(key);
29
30        // Binary search for largest timestamp <= target
31        int left = 0;
32        int right = list.size() - 1;
33        String result = "";
34
35        while (left <= right) {
36            int mid = left + (right - left) / 2;
37            if (list.get(mid).timestamp <= timestamp) {
38                result = list.get(mid).value;
39                left = mid + 1;  // Try to find larger timestamp
40            } else {
41                right = mid - 1;
42            }
43        }
44
45        return result;
46    }
47}
48
Loading visualizer...