Start learning free

LESSON 346 OF 573 · BINARY SEARCH

Time Based Key-Value Store in Scala: Binary Search per Key

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 13
    Ctrl + Enter to check

    SCALA · BINARY SEARCH

    Time Based Key Value Store in Scala, explained

    Problem overview

    A time-based key-value store remembers every value a key has ever had, together with the time it was set, and can answer what a key's value was at any moment. The class TimeMap has two methods:

    • set(key: String, value: String, timestamp: Int): Unit stores value for key at timestamp. Earlier values of the key are kept.
    • get(key: String, timestamp: Int): String returns the value set for key with the largest timestamp that is still <= timestamp. If the key has no value at or before that time, or was never set, it returns the empty string "".

    The timestamps of the set calls are strictly increasing: every set has a larger timestamp than every set before it.

    Example: after set("foo", "bar", 1), both get("foo", 1) and get("foo", 3) return bar, since nothing changed between times 1 and 3. After set("foo", "bar2", 4), get("foo", 4) and get("foo", 5) return bar2. The value set exactly at the asked time counts.

    Approach

    The simple way and its cost

    Keep each key's values in a list and, in get, look through the whole list for the latest entry that is not after the asked time. That costs O(n) per call, where n is the number of values set for that key. The lesson asks for O(1) in set and O(log n) in get.

    Lists that sort themselves

    For each key the class keeps an ArrayBuffer of (timestamp, value) pairs. Because every new timestamp is larger than all earlier ones, a new pair always belongs at the end. The list therefore stays sorted by time, oldest first, without any sorting, and set is just an append.

    A sorted list can be binary searched. The twist is that the target time usually is not in the list, so the search is not "find this timestamp" but "find the last timestamp that is not after the target". The method:

    • look at the middle entry;
    • if its time is <= the asked time, its value is a valid answer, and anything better must be to its right: remember the value and move left to middle + 1;
    • otherwise the entry and everything after it are too new, so move right to middle - 1.

    Each pass halves the positions still to check. Because every match is further right than the one before, the remembered value at the end belongs to the largest timestamp that is not after the asked time. If no entry qualifies, the remembered value stays "", which is the right answer.

    A trace on one key with the values (1, "a"), (2, "b"), (4, "c"), (7, "d"), (9, "e"), asking for time 8:

    leftrightmiddletime at middlewhat happens
    04244 <= 8: result is c, search to the right
    34377 <= 8: result is d, search to the right
    44499 > 8: search to the left, the range is now empty

    The result is d. Asking for time 0 on the same list looks at times 4 and 1, both too new, and returns "".

    Step by step

    1. Declare store, a mutable.HashMap[String, mutable.ArrayBuffer[(Int, String)]]. It maps each key to its buffer of pairs. (Int, String) is a tuple type, read with ._1 and ._2.
    2. In set, create the key's buffer if store does not contain the key yet.
    3. Append the pair (timestamp, value) to store(key) with +=. The pair needs its own parentheses inside those of +=.
    4. In get, return "" at once if the key was never set.
    5. Name the buffer entries. It is the same buffer, not a copy.
    6. Declare result as a var holding "", the answer when no value is old enough.
    7. Declare left and right, the inclusive ends of the range still to check: 0 and entries.length - 1.
    8. Loop while left <= right. When the two are equal, one position is still left to check.
    9. Take middle as (left + right) / 2. Integer division rounds down, so it is a valid position.
    10. If entries(middle)._1 <= timestamp, store entries(middle)._2 in result...
    11. ...and move left to middle + 1.
    12. Otherwise move right to middle - 1.
    13. Return result.

    The solution in Scala

    class TimeMap {
    val store = mutable.HashMap[String, mutable.ArrayBuffer[(Int, String)]]()

    def set(key: String, value: String, timestamp: Int): Unit = {
        if (!store.contains(key)) {
            store(key) = mutable.ArrayBuffer[(Int, String)]()
        }
        store(key) += ((timestamp, value))
    }

    def get(key: String, timestamp: Int): String = {
        if (!store.contains(key)) {
            return ""
        }
        val entries = store(key)
        var result = ""
        var left = 0
        var right = entries.length - 1
        while (left <= right) {
            val middle = (left + right) / 2
            if (entries(middle)._1 <= timestamp) {
                result = entries(middle)._2
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return result
    }
}

    Using the class:

    val t = new TimeMap
t.set("love", "high", 10)
t.set("love", "low", 20)
val answers = List(t.get("love", 5), t.get("love", 10), t.get("love", 15), t.get("love", 20), t.get("love", 25), t.get("hate", 25))
println(answers.map(s => "\"" + s + "\""))

    List("", "high", "high", "low", "low", "")

    The first and last answers are empty strings: "love" has no value at time 5, and "hate" was never set.

    Scala details:

    • store(key) = ... and store(key) += .... The first stores a new buffer under the key. The second reads the buffer for the key and appends to it in place.
    • Double parentheses in += ((timestamp, value)). The outer ones belong to the call, the inner ones build the tuple. Writing += (timestamp, value) is a type mismatch, since the compiler sees two arguments.
    • Tuples. entries(middle)._1 is the first element of the pair and ._2 is the second.
    • (left + right) / 2 divides two Ints, so the fraction is dropped. With the limits in this lesson the sum cannot overflow an Int.
    • The lesson's code uses mutable without a prefix. In a file of your own, add import scala.collection.mutable.

    Complexity

    Time. set is O(1) on average: a hash lookup and an append. get is O(log n) for the n values of that key: the range halves on every pass, and a list of 100,000 values needs at most 17 passes.

    Space. O(N) for N values in total, since every set keeps its pair.

    Edge cases and common mistakes

    • Using < instead of <=. A value set exactly at the asked time must count. With a strict comparison, get("love", 10) returns "" instead of high.
    • A key that was never set. store(key) on a missing key throws NoSuchElementException, so the check at the top of get is needed. get("hate", 25) returns "".
    • A time before the key's first value. Every entry is too new, right keeps moving left, and result stays "". In example terms, get("love", 5) returns "".
    • Returning the middle at once. Stopping at the first entry with time <= timestamp would return an older value when a newer one is also valid. Keep searching to the right after a match.
    • Keys do not share lists. After set("a", "x", 1), set("b", "y", 2) and set("a", "z", 3), get("a", 2) returns x and get("b", 1) returns "".
    • Using while (left < right). The last position would never be checked.

    Testing

    • After set("foo", "bar", 1): get("foo", 1) and get("foo", 3) return bar.
    • After set("foo", "bar2", 4): get("foo", 4) and get("foo", 5) return bar2.
    • After set("a", "x", 1), set("b", "y", 2), set("a", "z", 3): get("a", 2), get("b", 1), get("b", 2) and get("a", 3) return x, "", y and z.
    • With the values from the trace above, asking for times 0 to 10 gives "", a, b, b, c, c, c, d, d, e, e.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free