LeetCode: Time Based Key-Value Store

Time Based Key-Value Store

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #binarysearch

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

1. set(string key, string value, int timestamp)
2. Stores the key and value, along with the given timestamp.
3. get(string key, int timestamp)
4. Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
5. If there are multiple such values, it returns the one with the largest timestamp_prev.
6. 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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/time-based-key-value-store
// Basic Ideas: Binary search
//
// Complexity: Time O(log(n)), Space O(n)
type MyNode struct {
    value string
    timestamp int
}

type TimeMap struct {
    m map[string][]MyNode
}

/** Initialize your data structure here. */
func Constructor() TimeMap {
    return TimeMap{make(map[string][]MyNode)}
}


func (this *TimeMap) Set(key string, value string, timestamp int)  {
    // timestamps are strictly increasing
    this.m[key] = append(this.m[key], MyNode{value, timestamp})
}


func (this *TimeMap) Get(key string, timestamp int) string {
    // assume key is valid
    l, _ := this.m[key]
    // corner case
    if l[0].timestamp > timestamp {
        return ""
    }
    // set high to len(l), instead of len(l)-1
    low, high := 0, len(l)
    // binary search
    for low < high {
        mid := (high-low)/2 + low
        if l[mid].timestamp == timestamp {
            return l[mid].value
        }
        if l[mid].timestamp < timestamp {
            low = mid+1
        } else {
            high = mid
        }
    }
    return l[low-1].value
}

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