Time Based Key-Value Store medium

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps. Implement the TimeMap class:

• TimeMap(): Initializes the object.
• set(String key, String value, int timestamp): Stores the key key with the value value at the given time timestamp.
• get(String key, int timestamp): Returns a value such that it was stored at a timestamp equal to or smaller than timestamp, and among such values, it was stored at the latest timestamp. If there are multiple such values, it returns the value associated with the largest timestamp. If there is no such value, it returns "".

Example 1

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar","null","bar2","bar2"]
Explanation:
TimeMap kv;
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1
kv.get("foo", 1);  // output "bar"
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"
kv.set("foo", "bar2", 4);
kv.get("foo", 4); // output "bar2"
kv.get("foo", 5); //output "bar2"

Example 2

Input: inputs = ["TimeMap","set","get","set","get","get"], inputs = [[],["love","high",10],["love",5],["love","low",20],["love",5],["love",10]]
Output: [null,null,"","low","low","high"]

Steps

1. Data Structure: We'll use a HashMap to store keys. Each key will map to a list of Pair objects. Each Pair will contain a timestamp and its corresponding value.

2. set(key, value, timestamp): Add a new Pair(timestamp, value) to the list associated with the key.

3. get(key, timestamp):

   • Check if the key exists in the HashMap. If not, return "".
   • Perform a binary search on the list of Pair objects associated with the key to find the latest timestamp less than or equal to the given timestamp.
   • Return the value associated with the found timestamp. If no such timestamp is found, return "".

Explanation

The key to efficiency here is using binary search. A simple linear scan through the list of timestamps for each get operation would result in O(n) time complexity for each get, where n is the number of entries for a key. Binary search reduces this to O(log n).

Code

import java.util.*;

class TimeMap {
    Map<String, List<Pair>> map;

    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }
        List<Pair> list = map.get(key);
        int left = 0, right = list.size() - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid).timestamp <= timestamp) {
                index = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return index == -1 ? "" : list.get(index).value;
    }

    static class Pair {
        int timestamp;
        String value;

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

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

Complexity

• Time Complexity:

  • set: O(1) on average (amortized), O(n) in the worst case if there are many collisions in the HashMap.
  • get: O(log n), where n is the number of entries for a given key due to binary search.

• Space Complexity: O(m*n), where m is the number of unique keys, and n is the maximum number of entries for a single key. The space is dominated by the HashMap.