Start learning free

LESSON 347 OF 574 · BINARY SEARCH

Time Based Key-Value Store in Swift: O(log n) get by 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 12
    Ctrl + Enter to check

    SWIFT · BINARY SEARCH

    Time Based Key Value Store in Swift, explained

    Problem overview

    A TimeMap remembers every value a key has ever had, together with the time it was set. set(key, value, timestamp) stores a value. get(key, timestamp) returns the value that was set for that key with the largest timestamp that is still less than or equal to the one asked about. If the key has no value at or before that time, or was never set, get returns the empty string.

    The timestamps of the set calls strictly increase: each set has a larger timestamp than every set before it. The statement wants set in O(1) and get in O(log n), where n is the number of values set for that key.

    Take set("foo", "bar", 1). Then get("foo", 1) is "bar", and so is get("foo", 3), because nothing else was set in between. After set("foo", "bar2", 4), both get("foo", 4) and get("foo", 5) return "bar2". The value set exactly at the asked time counts. A call such as get("foo", 0) returns an empty string: nothing existed yet.

    Approach: sorted lists and a binary search

    Each key keeps a list of (timestamp, value) pairs. A get could scan the list from the end until it finds a timestamp that is not after the asked one. That is correct, but it costs O(n) per call when the answer is near the start.

    The list has a property worth using: it is sorted by timestamp. Because the set timestamps only go up, every new pair belongs at the end, so appending keeps the list sorted with no sorting and set takes O(1). A sorted list can be searched by halving, and that makes get take O(log n).

    This is a binary search for the last position whose timestamp is at most the asked one. At each step look at the middle pair:

    • if its timestamp is at most the asked one, it is a valid answer, and so far the best. Every position before it is older, so only a later position could beat it. Save its value and search the right half;
    • otherwise it was set too late, and so was everything after it. Search the left half.

    When the range is empty, the saved value is the answer. If no middle pair ever qualified, the saved value is still the empty string, which is the right answer. For a store with 100,000 values for one key, a search takes about 17 passes through the loop.

    Step by step

    1. Declare store as a var of type [String: [(timestamp: Int, value: String)]], set to [:]. The tuple has named parts, so a pair reads as .timestamp and .value.
    2. In set, append (timestamp: timestamp, value: value) to store[key, default: []]. The default gives a new key an empty array, so the first value needs no special case.
    3. In get, return "" if store[key] is nil: a key that was never set has no value at any time.
    4. Store the key's array in entries with store[key]!. The check above makes the ! safe.
    5. Declare result as a var set to "". It holds the best value found so far.
    6. Set the search bounds: left is 0 and right is entries.count - 1, both inclusive.
    7. Loop while left <= right. Use <= so that a range with one position left is still checked.
    8. Compute middle as (left + right) / 2. Integer division rounds down, so it is a valid position.
    9. If entries[middle].timestamp <= timestamp, save entries[middle].value in result.
    10. Still inside, set left = middle + 1 to look for a later qualifying value.
    11. Otherwise set right = middle - 1, since the middle pair and everything after it is too new.
    12. Return result.

    The solution in Swift

    class TimeMap {
    var store: [String: [(timestamp: Int, value: String)]] = [:]

    func set(_ key: String, _ value: String, _ timestamp: Int) {
        store[key, default: []].append((timestamp: timestamp, value: value))
    }

    func get(_ key: String, _ timestamp: Int) -> String {
        if store[key] == nil {
            return ""
        }
        let entries = store[key]!
        var result = ""
        var left = 0, right = entries.count - 1
        while left <= right {
            let middle = (left + right) / 2
            if entries[middle].timestamp <= timestamp {
                result = entries[middle].value
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return result
    }
}

    The Swift details worth a closer look:

    • Dictionary lookups return optionals. store[key] has the type [(timestamp: Int, value: String)]?. Comparing it with nil works even though the tuples aren't Equatable. The ! in store[key]! would crash on a missing key, and the check just above rules that out.
    • default: in set. store[key, default: []].append(...) changes the array inside the dictionary directly. For a missing key it starts from an empty array and stores the result.
    • A copy of the array. let entries = store[key]! gives a constant view of the array. Swift arrays are value types, and the copy is cheap because the storage is shared until something changes it. Nothing does here.
    • Several variables in one var. var left = 0, right = entries.count - 1 declares both at once. For an empty array, right is -1 and the loop doesn't run.
    • The middle. (left + right) / 2 is safe from overflow here, since positions are at most 100,000 and Int is 64 bits.
    • The method named set and get. They are ordinary method names in Swift. They are only special inside a property declaration, so a class can have methods with these names.

    Complexity

    Time. set appends to an array and updates a dictionary: O(1) on average. get does one dictionary lookup and then a binary search that halves the range each pass, so it takes O(log n) for the n values of that key.

    Space. O(N) for all the N pairs ever set, which is the data the class has to remember. get uses a few extra integers.

    Edge cases and common mistakes

    • A key that was never set. With "love" set at times 10 and 20, get("hate", 25) returns an empty string.
    • A time before the first value. get("love", 5) returns an empty string, as no pair qualified. Times 10 and 15 return "high", and times 20 and 25 return "low".
    • A time exactly equal to a set time. Use <=, not <. A value set at the asked time counts.
    • The loop condition left < right. It skips the last remaining position. With one pair, set("foo", "bar", 1), the call get("foo", 1) would return an empty string, and with two pairs a value at the last position can be missed.
    • Returning at the first match. Several values can be at or before the asked time, and the lesson wants the latest. Stopping at the first qualifying middle can return an older value, so the search keeps going right.
    • Keys are independent. After set("a", "x", 1), set("b", "y", 2) and set("a", "z", 3), get("a", 2) is "x", get("b", 1) is an empty string, and get("b", 2) is "y".
    • Scanning the list. A loop over all the pairs is correct but O(n) per call.

    Testing

    • set("foo", "bar", 1), then get("foo", 1) and get("foo", 3) give bar and bar. After set("foo", "bar2", 4), get("foo", 4) and get("foo", 5) give bar2 and bar2.
    • With set("love", "high", 10) and set("love", "low", 20), the calls get("love", 5), get("love", 10), get("love", 15), get("love", 20), get("love", 25) give an empty string, high, high, low, low.
    • With 100,000 values v1 to v100000 set at times 10, 20, ..., 1,000,000, get("k", 5) is an empty string, get("k", 10) is v1, get("k", 555) is v55 and get("k", 5000000) is v100000.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free