Time Based Key-Value Store

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 of the data structure.
• 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 "".

For example:

TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

import java.util.HashMap;
import java.util.TreeMap;

class TimeMap {

    private HashMap<String, TreeMap<Integer, String>> map;

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

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

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }

        TreeMap<Integer, String> timeMap = map.get(key);
        Integer floorKey = timeMap.floorKey(timestamp);

        if (floorKey == null) {
            return "";
        } else {
            return timeMap.get(floorKey);
        }
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

Naive Solution

A naive solution would be to store the key-value pairs with their timestamps in a list or array. When get is called, iterate through the list to find the largest timestamp that is less than or equal to the given timestamp. This would have a time complexity of O(n) for the get operation, where n is the number of entries for a given key.

Optimal Solution

The optimal solution uses a HashMap to store the keys, and a TreeMap to store the timestamps and values for each key. The TreeMap automatically sorts the timestamps, which allows for efficient retrieval of the value associated with the largest timestamp that is less than or equal to the given timestamp.

Big(O) Run-time Analysis

• set(String key, String value, int timestamp): O(log n), where n is the number of entries for a given key. This is because the put operation in a TreeMap takes O(log n) time.
• get(String key, int timestamp): O(log n), where n is the number of entries for a given key. This is because the floorKey operation in a TreeMap takes O(log n) time.

Big(O) Space Usage Analysis

• The space complexity is O(m), where m is the total number of key-value pairs stored in the TimeMap.
  • The HashMap stores the keys, and each key maps to a TreeMap.
  • Each TreeMap stores the timestamps and values for a specific key.

Edge Cases

1. Key does not exist: If the key does not exist in the TimeMap, the get method should return an empty string "".
2. Timestamp is smaller than all existing timestamps for a key: If the timestamp is smaller than all existing timestamps for a key, the get method should return an empty string "".
3. Multiple values exist for a key at different timestamps: The get method should return the value associated with the largest timestamp that is less than or equal to the given timestamp.
4. Large number of set and get operations: The TimeMap should be able to handle a large number of set and get operations efficiently.
5. Empty key or value: The key and value can be empty strings.

Here's how the provided code handles these edge cases:

1. Key does not exist: The code checks if the key exists in the HashMap using map.containsKey(key). If the key does not exist, it returns "".
2. Timestamp is smaller than all existing timestamps for a key: The code uses timeMap.floorKey(timestamp) to find the largest timestamp that is less than or equal to the given timestamp. If no such timestamp exists (i.e., floorKey returns null), it returns "".
3. Multiple values exist for a key at different timestamps: The floorKey method of the TreeMap ensures that the largest timestamp that is less than or equal to the given timestamp is returned. The corresponding value is then returned.
4. Large number of set and get operations: The use of HashMap and TreeMap ensures that the set and get operations are efficient, with a time complexity of O(log n) for each operation.
5. Empty key or value: The code handles empty keys and values correctly, as the HashMap and TreeMap can store empty strings as keys and values.