Leetcode - Time Based Key-Value Store

https://leetcode.com/problems/time-based-key-value-store/

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"   

1. Create two hashes. One is storing key -> [value1, value2, value3...], another is storing key -> [timestamp1, timestamp2, timestamp3...]

2. When getting the value by key, firstly find the [value1, value2, value3] and then run a binary search in [timestamp1, timestamp2, timestamp3] to find the index

type TimeMap struct {
    hash map[string][]string
    timestamp map[string][]int
}


/** Initialize your data structure here. */
func Constructor() TimeMap {
    return TimeMap{
        hash: map[string][]string{},
        timestamp: map[string][]int{},
    }
}


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


func (this *TimeMap) Get(key string, timestamp int) string {
    if len(this.hash[key]) == 0 {
        return ""
    }
    index := find(this.timestamp[key], timestamp)
    if index < 0 {
        return ""
    }
    return this.hash[key][index]
}

func find(arr []int, timestamp int) int {
    l := 0
    r := len(arr)-1
    var mid int
    for l <= r {
        mid = (l + r) / 2
        if arr[mid] == timestamp {
            return mid
        }
        if arr[mid] > timestamp {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    
    return r
}


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

• 相关文章
• 全局相关文章