Start learning free

LESSON 349 OF 576 · BINARY SEARCH

Time Based Key-Value Store in Rust: 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

    RUST · BINARY SEARCH

    Time Based Key Value Store in Rust, 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, and get(key, timestamp) returns the value with the largest timestamp that is still <= timestamp. If the key has no value at or before that time, or was never set, get returns the empty string.

    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 1 and 3. After set("foo", "bar2", 4), both get("foo", 4) and get("foo", 5) return "bar2". A value set exactly at the asked time counts.

    The constraints say that the timestamps of the set calls strictly increase, and the statement asks for O(1) time in set and O(log n) in get, where n is the number of values set for that key.

    Approach: one sorted list per key

    The straightforward design keeps, for each key, a list of (timestamp, value) pairs, and get scans the list for the latest pair that is not after the asked time. That costs O(n) per call, which is too slow when one key has tens of thousands of values.

    The constraint on timestamps is what makes a faster design possible. Because every new set has a larger timestamp than every earlier one, appending the new pair to the end of its key's vector keeps that vector sorted by time, with no sorting needed. So set is just an append.

    A sorted vector can be binary searched. Here the search does not look for an exact match but for the last pair whose timestamp is <= timestamp. Look at the pair in the middle. If its timestamp is not after the asked time, it is a candidate answer, and everything before it is older, so only a later pair could beat it: remember it and search the right half. If its timestamp is after the asked time, so is everything after it: search the left half. When the range is empty, the last remembered candidate is the answer, or the empty string if there was none.

    Take a key with the pairs (2, "v0"), (4, "v1"), (6, "v2"), (8, "v3") and (10, "v4"), and ask for time 7:

    left=0 right=4 middle=2 time=6
left=3 right=4 middle=3 time=8
result="v2"

    The first middle, time 6, is at or before 7, so "v2" is remembered and the search moves right. The next middle, time 8, is after 7, so the search moves left, the range empties and the answer is "v2".

    Step by step

    1. Declare the field store as a HashMap<String, Vec<(i32, String)>>: each key maps to its vector of (timestamp, value) tuples, read with .0 and .1.
    2. In new, return a TimeMap with an empty map.
    3. In set, push the pair (timestamp, value) onto the key's vector. entry(key).or_insert(Vec::new()) gives the vector, creating an empty one for a new key, so the first value of a key needs no special case.
    4. In get, return an empty String when the store doesn't contain the key.
    5. Borrow the key's vector as entries with &self.store[&key]. The borrow copies nothing.
    6. Start result as an empty String. If no value is old enough, it stays empty, and that is the answer.
    7. Set the search bounds left = 0 and right = entries.len() as i32 - 1, both inclusive, and both i32 because right can reach -1.
    8. Loop while left <= right. With <=, a range of one position is still checked.
    9. Take the middle of the two bounds.
    10. If the middle's timestamp is <= timestamp, store a clone of its value in result.
    11. Move left to middle + 1, to look for a later pair that still qualifies.
    12. Otherwise move right to middle - 1, because that pair and every one after it was set too late.
    13. Return result after the loop, without a semicolon.

    The solution in Rust

    struct TimeMap {
    store: HashMap<String, Vec<(i32, String)>>,
}

impl TimeMap {
    fn new() -> TimeMap {
        TimeMap { store: HashMap::new() }
    }

    fn set(&mut self, key: String, value: String, timestamp: i32) {
        self.store.entry(key).or_insert(Vec::new()).push((timestamp, value));
    }

    fn get(&self, key: String, timestamp: i32) -> String {
        if !self.store.contains_key(&key) {
            return String::new();
        }
        let entries = &self.store[&key];
        let mut result = String::new();
        let mut left = 0i32;
        let mut right = entries.len() as i32 - 1;
        while left <= right {
            let middle = (left + right) / 2;
            if entries[middle as usize].0 <= timestamp {
                result = entries[middle as usize].1.clone();
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        result
    }
}

    In a file of your own, add use std::collections::HashMap; at the top. Using the store for the second example:

    love 5 ""
love 10 "high"
love 15 "high"
love 20 "low"
love 25 "low"
hate ""

    Those results come from set("love", "high", 10) and set("love", "low", 20), followed by get calls at times 5, 10, 15, 20 and 25 for "love" and at time 25 for "hate".

    The Rust details worth a closer look:

    • entry(key).or_insert(Vec::new()). It returns a mutable reference to the key's vector, inserting an empty one first if the key is new, so push can be chained onto it. set takes key: String by value, and entry moves it into the map.
    • &self in get. Reading does not change the store, so get borrows it immutably. self.store[&key] would panic for a missing key, which is why the contains_key check comes first.
    • Why i32 bounds. A usize cannot go below zero. When the target is older than every pair, right becomes middle - 1 with middle at 0, which is -1, and the loop ends. With a usize, that subtraction would panic in a debug build and wrap to a huge number in an optimized one. The vector is indexed with middle as usize.
    • clone(). The vector keeps owning its strings, so result gets a copy of the text. Moving it out of a borrowed vector is not allowed.
    • The empty string. String::new() makes one without allocating. An empty string is also the answer for a missing key and for a time before the first value.
    • The middle. (left + right) / 2 is safe here: with at most 100,000 calls, the sum is far from the i32 limit.

    Complexity

    Time. set is one hash lookup and one append: O(1) on average. get is one hash lookup plus a binary search that halves the range on every pass, so it makes about log2(n) passes: O(log n), where n is the number of values set for that key. The key's own length is at most 20 characters.

    Space. O(N) for the N values ever set, since the store keeps all of them. get uses a few integers and the returned string.

    Edge cases and common mistakes

    • A time before the first value. With the pairs at times 2, 4, 6, 8 and 10, get(k, 1) returns "", because every pair is later than time 1.
    • A time exactly equal to a stored time. get(k, 2) returns "v0" and get(k, 10) returns "v4". Using < instead of <= would miss them.
    • A time after the last value. get(k, 99) returns "v4", the latest value.
    • A key that was never set. It returns "", as for "hate" above. Indexing the map without the check panics.
    • Keys are independent. 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".
    • Using lo < hi as the loop test. A one-element range would be skipped. A store with a single value would then never find it.
    • Stopping at the first match. The search must go on to the right after a match, because a later pair may also be at or before the asked time.
    • Scanning from the start. It is correct but O(n) per get. With 100,000 values under one key, a binary search needs about 17 passes.

    Testing

    • set("foo", "bar", 1), then get("foo", 1) and get("foo", 3): "bar" and "bar".
    • Then set("foo", "bar2", 4), get("foo", 4) and get("foo", 5): "bar2" and "bar2".
    • With 100,000 values "v1" to "v100000" set at times 1 to 100,000, get(k, 77777) returns "v77777".
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free