Start learning free

LESSON 346 OF 573 · BINARY SEARCH

Time Based Key-Value Store in Go: O(log n) Get with Binary Search

Practice O(log n) Read the full explanation

A time-based key-value store keeps every value a key has ever had, each with the time it was set. You can then ask what a key's value was at any moment: the value that was set most recently at or before that moment.

Implement the class TimeMap:

  • TimeMap() creates an empty store.
  • set(key, value, timestamp) stores the string value for the string key at the time timestamp. The key's earlier values are kept.
  • get(key, timestamp) returns the value that was set for key with the largest timestamp that is still <= timestamp. If no value was set for key at or before timestamp, or key was never set at all, it returns the empty string "".

The input is a list of operations, applied in order to one new TimeMap. The output lists what the get calls return, in order; an empty string is shown as "". The starter code spells these names the way your language does.

 

Example 1:

Input:
    set("foo", "bar", 1)
    get("foo", 1)
    get("foo", 3)
    set("foo", "bar2", 4)
    get("foo", 4)
    get("foo", 5)
Output: bar bar bar2 bar2
Explanation:
At time 1, "foo" was set to "bar", so get("foo", 1) is "bar".
Nothing was set for "foo" between 1 and 3, so at time 3 the value is still "bar".
At time 4, "foo" was set to "bar2": from then on, get returns "bar2", at time 4 and at time 5.

Example 2:

Input:
    set("love", "high", 10)
    set("love", "low", 20)
    get("love", 5)
    get("love", 10)
    get("love", 15)
    get("love", 20)
    get("love", 25)
    get("hate", 25)
Output: "" high high low low ""
Explanation:
At time 5, "love" had no value yet, so the answer is the empty string.
At times 10 and 15 the latest value is "high"; at 20 and 25 it is "low".
"hate" was never set, so its answer is the empty string too.

Example 3:

Input:
    set("a", "x", 1)
    set("b", "y", 2)
    set("a", "z", 3)
    get("a", 2)
    get("b", 1)
    get("b", 2)
    get("a", 3)
Output: x "" y z
Explanation: Each key keeps its own values. At time 2, "a" still has "x": "z" comes only at time 3. "b" gets its first value at time 2, so at time 1 it has none.

 

Constraints:

  • 1 <= key.length, value.length <= 20
  • key and value consist of lowercase English letters and digits.
  • 1 <= timestamp <= 107
  • The timestamps of the set calls are strictly increasing: each set has a larger timestamp than every set before it.
  • At most 105 calls in total are made to set and get.

Note:

set should run in O(1) time and get in O(log n) time, where n is the number of values set for that key. Looking through all of a key's values in get would take O(n) time per call.

STEP 1 OF 14
    Ctrl + Enter to check

    GO · BINARY SEARCH

    Time Based Key Value Store in Go, explained

    Problem overview

    A time-based key-value store keeps every value a key has ever had, together with the time it was set. You can then ask what a key's value was at any moment: the value set most recently at or before that moment.

    The lesson asks for a TimeMap struct. Constructor creates an empty store. Set(key, value, timestamp) stores a string value for a key at a time, and keeps the key's earlier values. Get(key, timestamp) returns the value with the largest timestamp that is still <= timestamp, or the empty string "" if the key has no value that old or was never set.

    One guarantee makes the design simple: the timestamps of the Set calls are strictly increasing. Each Set has a larger timestamp than every Set before it.

    In the first example, Set("foo", "bar", 1) is followed by Get("foo", 1) and Get("foo", 3), which both return "bar": nothing changed between times 1 and 3. After Set("foo", "bar2", 4), both Get("foo", 4) and Get("foo", 5) return "bar2". Get("foo", 0) returns "", because nothing was set yet at time 0.

    Approach: one sorted list per key, then binary search

    The simplest Get looks through all of a key's values and keeps the latest one that isn't after the asked time. That costs O(n) per call, where n is the number of values set for that key.

    The statement's guarantee removes the need to look at all of them. For each key, the store keeps a list of (timestamp, value) pairs. Since each new pair has the largest timestamp so far, it belongs at the end of its list, so every list stays sorted by time without any sorting, and Set takes O(1). A sorted list can be binary searched, so Get takes O(log n).

    This is not the plain "find the value" binary search. The asked time usually falls between two timestamps, so there may be no exact match. The search looks for the last entry whose timestamp is not after the asked time. Whenever the entry in the middle qualifies, it is remembered as the best answer so far, and the search continues to the right, in case a later entry also qualifies. When the entry in the middle is too new, the search continues to the left.

    As an example, take five values for one key with timestamps 10, 20, 30, 40, 50, and ask for time 35. The first middle is position 2 (timestamp 30): it qualifies, so the search moves right to positions 3 to 4. The middle is position 3 (timestamp 40): too new, so the search moves left and the range is empty. The answer is the value at timestamp 30.

    Step by step

    1. Declare the entry struct with two fields: timestamp as an int and value as a string.
    2. Declare store in TimeMap as a map[string][]entry: for each key, its entries in the order they were set, which is also the order of their timestamps.
    3. Create the map in Constructor. The zero value of a map is nil, and storing into a nil map stops the program.
    4. In Set, append entry{timestamp, value} to this.store[key] and store the result back. For a new key, this.store[key] is a nil slice and append works on it.
    5. In Get, read the key's entries and whether the key exists in one line: entries, found := this.store[key].
    6. If the key isn't found, return "".
    7. Declare result as "". If no entry is old enough, it stays empty, which is the right answer.
    8. Set left and right to the first and the last position. Both ends are inclusive.
    9. Loop while left <= right. When they are equal, one position is still left to check.
    10. Compute middle as (left + right) / 2. Integer division rounds down, so it is a valid position.
    11. If the entry at middle is not after timestamp (<=, so a value set exactly at the asked time counts), save its value in result.
    12. Move left to middle + 1, to look for a later entry that still qualifies.
    13. Otherwise move right to middle - 1, because the entry and every one after it are too new.
    14. Return result after the loop.

    The solution in Go

    type entry struct {
    timestamp int
    value string
}

type TimeMap struct {
    store map[string][]entry
}

func Constructor() TimeMap {
    return TimeMap{store: map[string][]entry{}}
}

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

func (this *TimeMap) Get(key string, timestamp int) string {
    entries, found := this.store[key]
    if !found {
        return ""
    }
    result := ""
    left, right := 0, len(entries)-1
    for left <= right {
        middle := (left + right) / 2
        if entries[middle].timestamp <= timestamp {
            result = entries[middle].value
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return result
}

    The Go details worth a closer look:

    • Positional struct literal. entry{timestamp, value} fills the fields in the order the struct declares them. If the declaration order changed, the literal would break, or silently swap fields of the same type.
    • The comma-ok form. A map read with two variables returns the value and a bool telling whether the key existed. Without it, a missing key would give a nil slice, which looks like a key with no entries. Here both cases happen to give "", but the form makes the intent clear.
    • Appending to a map entry. this.store[key] yields a slice header copy, so the result of append must be assigned back to the map.
    • Safe midpoint. (left + right) / 2 could overflow for indexes near the limit of int, but Go's int is 64 bits here and a slice can't be that long, so it is safe.

    Complexity

    Time. Set is O(1) amortized: a map lookup and an append. Get is O(log n), where n is the number of values set for that key: every pass halves the positions still to check, so a key with 100,000 values needs at most 17 passes.

    Space: O(N) for all N values ever set, since nothing is thrown away.

    Edge cases and common mistakes

    • A key that was never set. Get("hate", 25) returns "".
    • A time before the first value. With Set("love", "high", 10), Get("love", 5) returns "": no entry qualifies, so result is never assigned.
    • An exact match. Get("love", 10) returns "high". Using < instead of <= would miss it.
    • A time between two timestamps. After Set("love", "low", 20), Get("love", 15) returns "high", the older value, and Get("love", 25) returns "low".
    • Several keys. Each key has its own list. After Set("a", "x", 1), Set("b", "y", 2) and Set("a", "z", 3), the calls Get("a", 2), Get("b", 1), Get("b", 2) and Get("a", 3) return "x", "", "y" and "z".
    • Stopping at the first match. Returning as soon as an entry qualifies gives an old value. The search must continue to the right.
    • Using left < right. The last position would never be checked.

    Testing

    With the first example's calls, the four Get results are "bar", "bar", "bar2", "bar2". With the second example, the six Get results are "", "high", "high", "low", "low", "". For a key with the values "v1" to "v5" set at times 10, 20, 30, 40, 50, Get("k", 35) returns "v3", after two passes of the loop: the first looks at the timestamp 30 and the second at 40.

    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free