Time Based Key-Value Store

Medium

The problem

Build a TimeMap that remembers values for keys at different times. Set(key, value, timestamp) stores a value for a key at a time. Get(key, timestamp) returns the value that was stored with the biggest timestamp that is less than or equal to the given one, or "" if there is none.

Example 1
Input: t := Constructor() t.Set("love", "high", 10) t.Get("love", 10) t.Get("love", 15) t.Set("love", "low", 20) t.Get("love", 25) t.Get("love", 15) t.Get("love", 5) t.Get("hate", 10)
Output: "high", "high", "low", "high", "", "" (for the six Get calls in order)
At time 10 and 15 the latest value stored at or before is "high". Once "low" is stored at 20, time 25 gives "low", but time 15 still gives "high". Time 5 is before anything was stored, and the key "hate" was never stored, so both give "".

Limits

Up to 200,000 calls in total
For each key, Set is called with strictly increasing timestamps
1 ≤ timestamp ≤ 10,000,000
Keys and values are lowercase letters

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Timestamps for a key arrive in increasing order. What does "latest value at or before t" remind you of?

The idea

Map key → list of (timestamp, value). get() binary-searches for the last timestamp ≤ t.

Target: set O(1), get O(log n)

Go function shape

type TimeMap struct{}
func Constructor() TimeMap
func (t *TimeMap) Set(key string, value string, timestamp int)
func (t *TimeMap) Get(key string, timestamp int) string

Reference solution

Tested with go test. Try it yourself first, then compare.

// TimeMap keeps every (timestamp, value) for a key in insertion order. Timestamps only increase,
// so each list is already sorted and Get can binary-search it.
type TimeMap struct{ data map[string][]entry }
type entry struct {
	ts    int
	value string
}

func NewTimeMap() *TimeMap { return &TimeMap{data: map[string][]entry{}} }

func (t *TimeMap) Set(key, value string, ts int) {
	t.data[key] = append(t.data[key], entry{ts, value})
}

// Get returns the value with the largest timestamp <= ts, or "".
func (t *TimeMap) Get(key string, ts int) string {
	list := t.data[key]
	i := sort.Search(len(list), func(i int) bool { return list[i].ts > ts }) // first entry that is too new
	if i == 0 {
		return ""
	}
	return list[i-1].value
}

Read the lesson: Binary Search