Start learning free

LESSON 346 OF 573 · BINARY SEARCH

Time Based Key-Value Store in Kotlin: 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 13
    Ctrl + Enter to check

    KOTLIN · BINARY SEARCH

    Time Based Key Value Store in Kotlin, explained

    Problem overview

    You write a class TimeMap that remembers every value a key has ever had. set(key, value, timestamp) stores a string value for a string key at a given time and keeps the earlier values. get(key, timestamp) returns the value whose timestamp is the largest one that is still at most timestamp. If the key was never set, or all its values are newer than the question, it returns the empty string.

    Say "love" is set to "high" at time 10 and to "low" at time 20. Then get("love", 5) is empty, because nothing was set yet. Times 10 and 15 give high, and times 20 and 25 give low. A value set exactly at the asked time counts. A key never set, such as "hate", gives the empty string.

    Approach

    The simplest design keeps, for each key, a list of (timestamp, value) pairs, and get walks through the whole list to find the best match. That costs O(n) per call, where n is how many values the key has.

    The constraints give a lot: the timestamps of the set calls strictly increase. So each new pair belongs at the end of its key's list, and every list is automatically sorted by time with no sorting. A sorted list can be binary searched. The question "the latest timestamp at or before t" is a binary search that, instead of looking for an exact match, remembers the best candidate seen so far:

    • if the middle entry's timestamp is at most t, it is a valid answer, and anything better lies to its right, so remember its value and search the right half;
    • otherwise the middle entry and everything after it are too new, so search the left half.

    When the range is empty, the remembered value is the answer, or the empty string if no entry was old enough. set takes O(1) and get takes O(log n).

    Step by step

    1. One map of lists. The field store is a HashMap<String, MutableList<Pair<Int, String>>>: each key maps to its list of pairs. In a Pair, .first is the timestamp and .second the value.
    2. Create a list on first use. In set, if the key is not in store, store an empty mutableListOf() for it.
    3. Append. Add Pair(timestamp, value) to store[key]!!. The !! says the lookup is not null, which the if just made sure of. The new pair has the largest timestamp so far, so the end is its place.
    4. Unknown key. In get, if the key is not in store, return "".
    5. Set up the search. Name the key's list entries (the same list, not a copy), start result as "", and start left at 0 and right at entries.size - 1. Both ends are inclusive.
    6. Loop while left <= right. With < instead, a range of one entry would be skipped.
    7. Take the middle. (left + right) / 2; integer division rounds down, so it is a valid position.
    8. Old enough: if entries[middle].first <= timestamp, save entries[middle].second in result and move left to middle + 1.
    9. Too new: otherwise move right to middle - 1.
    10. Return result. Each saved match sits to the right of the one before it, so result ends as the value with the largest timestamp not after the question.

    The solution in Kotlin

    class TimeMap {
    val store = HashMap<String, MutableList<Pair<Int, String>>>()

    fun set(key: String, value: String, timestamp: Int) {
        if (!store.containsKey(key)) {
            store[key] = mutableListOf()
        }
        store[key]!!.add(Pair(timestamp, value))
    }

    fun get(key: String, timestamp: Int): String {
        if (!store.containsKey(key)) {
            return ""
        }
        val entries = store[key]!!
        var result = ""
        var left = 0
        var right = entries.size - 1
        while (left <= right) {
            val middle = (left + right) / 2
            if (entries[middle].first <= timestamp) {
                result = entries[middle].second
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return result
    }
}

    Kotlin details worth knowing:

    • store[key] is nullable. Indexing a map gives null for a missing key, so its type is MutableList<Pair<Int, String>>?. The !! operator converts it to the non-null type and would throw if it were null. The code only uses it right after checking the key.
    • The names set and get are fine. They are soft keywords, meaningful only in property accessors, so the class can have fun set(...) and fun get(...) as ordinary methods called as map.set(...) and map.get(...).
    • Assigning with brackets. store[key] = mutableListOf() calls the map's set; Kotlin infers the list's element type from store's declared type.
    • Midpoint and overflow. (left + right) / 2 could overflow an Int only for lists with more than a billion entries, far above the limit of 100,000 calls here.

    Seeing it run

    The first part of this code repeats the example above; the second stores five values at times 10, 20, 30, 40 and 50 and asks between and around them.

    fun main() {
    val map = TimeMap()
    map.set("love", "high", 10)
    map.set("love", "low", 20)
    for (t in intArrayOf(5, 10, 15, 20, 25)) {
        println("get(\"love\", $t) = \"${map.get("love", t)}\"")
    }
    println("get(\"hate\", 25) = \"${map.get("hate", 25)}\"")

    val k = TimeMap()
    for ((i, v) in listOf("a", "b", "c", "d", "e").withIndex()) {
        k.set("k", v, (i + 1) * 10)
    }
    println(k.get("k", 35))
    println(k.get("k", 50))
    println("\"" + k.get("k", 9) + "\"")
}

    It prints:

    get("love", 5) = ""
get("love", 10) = "high"
get("love", 15) = "high"
get("love", 20) = "low"
get("love", 25) = "low"
get("hate", 25) = ""
c
e
""

    At time 35 the values stored at 10, 20 and 30 are old enough, and the latest of them is c. At time 50 the last entry matches exactly, so the answer is e. At time 9 no entry is old enough, so result keeps its starting value, the empty string.

    Complexity

    • set: O(1) on average: one hash lookup and a list append.
    • get: O(log n), where n is the number of values stored for that key. Every pass halves the range, so a key with 100,000 values needs at most 17 passes. Other keys do not slow it down, because each key has its own list.
    • Space: O(total number of set calls).

    Edge cases and common mistakes

    • Exact match. A value set at exactly the asked time counts, so the comparison is <=, not <.
    • Stopping at the first match. A normal binary search returns when it finds the target. Here a match is only a candidate, and the search must go right to look for a later one.
    • Nothing old enough. If every entry is newer, the search only ever goes left and result stays empty.
    • Key never set. Check for it first; otherwise store[key]!! throws a NullPointerException.
    • Scanning the list. A loop from the end of the list is correct but takes O(n) per get.
    • Relying on sorted order. The list is sorted only because the timestamps of the set calls strictly increase. If they could arrive out of order, the append would break it.
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free