Welcome to Subscribe On Youtube

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

############

class TimeMap {
    private Map<String, TreeMap<Integer, String>> ktv = new HashMap<>();

    public TimeMap() {
    }

    public void set(String key, String value, int timestamp) {
        ktv.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!ktv.containsKey(key)) {
            return "";
        }
        var tv = ktv.get(key);
        Integer t = tv.floorKey(timestamp);
        return t == null ? "" : tv.get(t);
    }
}

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

  • // OJ: https://leetcode.com/problems/time-based-key-value-store/
// Time:
//      TimeMap: O(1)
//      set: O(logT)
//      get: O(logT)
// Space: O(N)
class TimeMap {
    unordered_map<string, map<int, string, greater<>>> m;
public:
    TimeMap() {}
    void set(string key, string value, int timestamp) {
        m[key][timestamp] = value;
    }
    string get(string key, int timestamp) {
        if (m.count(key) == 0) return "";
        auto it = m[key].lower_bound(timestamp);
        return it == m[key].end() ? "" : it->second;
    }
};

  • class TimeMap:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.ktv = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.ktv[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.ktv:
            return ''
        tv = self.ktv[key]
        i = bisect_right(tv, (timestamp, chr(127)))
        return tv[i - 1][1] if i else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

############

class TimeMap(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.t_ = collections.defaultdict(list)
        self.v_ = collections.defaultdict(list)
        self.max_ = collections.defaultdict(int)
        

    def set(self, key, value, timestamp):
        """
        :type key: str
        :type value: str
        :type timestamp: int
        :rtype: None
        """
        self.t_[key].append(timestamp)
        self.v_[key].append(value)
        self.max_[key] = max(self.max_[key], timestamp)
        

    def get(self, key, timestamp):
        """
        :type key: str
        :type timestamp: int
        :rtype: str
        """
        if key not in self.t_:
            return ""
        if timestamp >= self.max_[key]:
            return self.v_[key][-1]
        v = bisect.bisect_right(self.t_[key], timestamp)
        if v:
            return self.v_[key][v - 1]
        return ""


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

  • type TimeMap struct {
	ktv map[string][]pair
}

func Constructor() TimeMap {
	return TimeMap{map[string][]pair{} }
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	this.ktv[key] = append(this.ktv[key], pair{timestamp, value})
}

func (this *TimeMap) Get(key string, timestamp int) string {
	pairs := this.ktv[key]
	i := sort.Search(len(pairs), func(i int) bool { return pairs[i].t > timestamp })
	if i > 0 {
		return pairs[i-1].v
	}
	return ""
}

type pair struct {
	t int
	v string
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Set(key,value,timestamp);
 * param_2 := obj.Get(key,timestamp);
 */

All Problems

All Solutions