Time Based Key-Value Store

NeetCode: Time Based Key-Value Store · LeetCode: 981. Time Based Key-Value Store · Difficulty: Medium

Design a store where set(key, value, timestamp) records a value and get(key, timestamp) returns the value set with the largest timestamp <= timestamp, or an empty string if none. Timestamps for set are strictly increasing per key.

Example

Text

set("foo", "bar", 1)
get("foo", 1) -> "bar"
get("foo", 3) -> "bar"
set("foo", "bar2", 4)
get("foo", 4) -> "bar2"
get("foo", 5) -> "bar2"

Brute force: scan the history

Store a list of (timestamp, value) entries per key in a HashMap and scan the list for the entry with the largest timestamp <= timestamp. The Entry class is a small holder for the pair. Because timestamps arrive in increasing order, the last entry that passes the test is the answer. HashMap order is never printed, so the output is deterministic.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TimeMap {
    private static class Entry {
        final int timestamp;
        final String value;

        Entry(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }
    }

    private final Map<String, List<Entry>> data = new HashMap<>();

    public TimeMap() {
    }

    public void set(String key, String value, int timestamp) {
        data.computeIfAbsent(key, k -> new ArrayList<>()).add(new Entry(timestamp, value));
    }

    public String get(String key, int timestamp) {
        String answer = "";
        List<Entry> history = data.get(key);
        if (history != null) {
            for (Entry e : history) {
                if (e.timestamp <= timestamp) {
                    answer = e.value;
                }
            }
        }
        return answer;
    }
}

public class Main {
    static String show(String s) {
        return "\"" + s + "\"";
    }

    public static void main(String[] args) {
        TimeMap m = new TimeMap();
        m.set("foo", "bar", 1);
        System.out.println(show(m.get("foo", 1)));
        System.out.println(show(m.get("foo", 3)));
        m.set("foo", "bar2", 4);
        System.out.println(show(m.get("foo", 4)));
        System.out.println(show(m.get("foo", 5)));
        System.out.println(show(m.get("foo", 0)));
        System.out.println(show(m.get("missing", 5)));
    }
}

Output

"bar"
"bar"
"bar2"
"bar2"
""
""

Time: set is O(1), get is O(k) for k entries under the key. Space: O(total entries).

Optimal: binary search the history

Timestamps for a key arrive in increasing order, so each key's history is already sorted. The binary search finds the first index whose timestamp is greater than the query. The entry before it is the answer. If that index is 0, no entry is old enough and the result is the empty string. HashMap.get returns null for an unknown key, so get checks for that first.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TimeMap {
    private static class Entry {
        final int timestamp;
        final String value;

        Entry(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }
    }

    private final Map<String, List<Entry>> data = new HashMap<>();

    public TimeMap() {
    }

    public void set(String key, String value, int timestamp) {
        data.computeIfAbsent(key, k -> new ArrayList<>()).add(new Entry(timestamp, value));
    }

    public String get(String key, int timestamp) {
        List<Entry> history = data.get(key);
        if (history == null) {
            return "";
        }
        // First index whose timestamp is greater than the query.
        int lo = 0;
        int hi = history.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (history.get(mid).timestamp <= timestamp) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo == 0 ? "" : history.get(lo - 1).value;
    }
}

public class Main {
    static String show(String s) {
        return "\"" + s + "\"";
    }

    public static void main(String[] args) {
        TimeMap m = new TimeMap();
        m.set("foo", "bar", 1);
        System.out.println(show(m.get("foo", 1)));
        System.out.println(show(m.get("foo", 3)));
        m.set("foo", "bar2", 4);
        System.out.println(show(m.get("foo", 4)));
        System.out.println(show(m.get("foo", 5)));
        System.out.println(show(m.get("foo", 0)));
        System.out.println(show(m.get("missing", 5)));
    }
}

Output

"bar"
"bar"
"bar2"
"bar2"
""
""

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

Appending on set keeps every history sorted, so get never needs to re-sort.