981. Time Based Key-Value Store #

Problem #

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.

Problem Summary #

Create a time-based key-value store class TimeMap, which supports the following two operations:

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

• Store the key key, the value value, and the given timestamp timestamp.

2. get(string key, int timestamp)

• Return the value stored by a previous call to set(key, value, timestamp_prev), where timestamp_prev <= timestamp.
• If there are multiple such values, return the one corresponding to the largest  timestamp_prev.
• If there is no value, return the empty string（""）。

Tips:

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

Solution Approach #

• The requirement is to design a timestamp-based kv store. The set() operation contains a timestamp. During the get() operation, find the value corresponding to the key whose timestamp is less than or equal to timestamp; if there are multiple solutions, output the value corresponding to the largest timestamp that satisfies the condition.
• This problem can be solved with binary search. Use a map to store the kv data: the key corresponds to the key, and the value corresponds to a struct that contains value and timestamp. When executing the get() operation, first take out the struct array corresponding to key, and then perform binary search in this array based on timestamp. Since the problem asks to find the largest timestamp less than or equal to timestamp, there will be many solutions that satisfy the condition. Transform it: first find the minimum solution > timestamp, then subtract one from the index, which gives the largest solution satisfying the problem statement.
• In addition, the problem mentions that “the timestamp in TimeMap.set operations is strictly increasing.” Therefore, when storing the value structs in the map, no sorting is needed; they are naturally ordered.

Code #

package leetcode

import "sort"

type data struct {
	time  int
	value string
}

// TimeMap is a timebased key-value store
// TimeMap define
type TimeMap map[string][]data

// Constructor981 define
func Constructor981() TimeMap {
	return make(map[string][]data, 1024)
}

// Set define
func (t TimeMap) Set(key string, value string, timestamp int) {
	if _, ok := t[key]; !ok {
		t[key] = make([]data, 1, 1024)
	}
	t[key] = append(t[key], data{
		time:  timestamp,
		value: value,
	})
}

// Get define
func (t TimeMap) Get(key string, timestamp int) string {
	d := t[key]
	i := sort.Search(len(d), func(i int) bool {
		return timestamp < d[i].time
	})
	i--
	return t[key][i].value
}

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