Formatted question description: https://leetcode.ca/all/981.html

981. Time Based Key-Value Store

Level

Medium

Description

Create a timebased key-value store class TimeMap, that supports two operations.

  1. set(string key, string value, int timestamp)

    • Stores the key and value, along with the given timestamp.
  2. get(string key, int timestamp)

    • Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
    • If there are multiple such values, it returns the one with the largest timestamp_prev.
    • If there are no values, it returns the empty string ("").

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","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]

Note:

  1. All key/value strings are lowercase.
  2. All key/value strings have length in the range [1, 100]
  3. The timestamps for all TimeMap.set operations are strictly increasing.
  4. 1 <= timestamp <= 10^7
  5. TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

Solution

Create a class TimestampValue that stores a timestamp and the corresponding value. Create a map to store each key with the list of objects of type TimestampValue.

Each time set is called, obtain the list of the key, create a new TimestampValue object using the value and the timestamp, and add the new TimestampValue object into the list.

Each time get is called, obtain the list of the key, and then do binary search using timestamp. If the object with timestamp exists in the list, then obtain the object’s value and return. Otherwise, find the object that has the greatest timestamp that is less than timestamp, and return the object. If the object is not found, return "".

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

    /** Initialize your data structure here. */
    public TimeMap() {
        map = new HashMap<String, List<TimestampValue>>();
    }
    
    public void set(String key, String value, int timestamp) {
        List<TimestampValue> list = map.getOrDefault(key, new ArrayList<TimestampValue>());
        TimestampValue timestampValue = new TimestampValue(timestamp, value);
        list.add(timestampValue);
        map.put(key, list);
    }
    
    public String get(String key, int timestamp) {
        List<TimestampValue> list = map.getOrDefault(key, new ArrayList<TimestampValue>());
        int index = binarySearch(list, timestamp);
        if (index < 0)
            index = -index - 2;
        if (index < 0)
            return "";
        TimestampValue timestampValue = list.get(index);
        return timestampValue.value;
    }

    public int binarySearch(List<TimestampValue> list, int timestamp) {
        int low = 0, high = list.size() - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            TimestampValue timestampValue = list.get(mid);
            int midTimestamp = timestampValue.timestamp;
            if (midTimestamp == timestamp)
                return mid;
            else if (midTimestamp > timestamp)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -low - 1;
    }
}

class TimestampValue implements Comparable<TimestampValue> {
    int timestamp;
    String value;

    public TimestampValue() {
        
    }

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

    public int compareTo(TimestampValue timestampValue2) {
        return this.timestamp - timestampValue2.timestamp;
    }
}

/**
 * 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);
 */

All Problems

All Solutions