Time Based Key Value Store

The problem

A store keeps every value a key was given, each with its timestamp. operations names the operations to run, in order, and values holds the arguments of each. "TimeMap" comes first, has no arguments and creates the empty store. "set" has a key, a value and a timestamp, and stores that value for the key. "get" has a key and a timestamp, and asks for the value set for the key at the latest time not after that timestamp, or "" if there is none. Return the list of results, one per operation: each "get" gives its answer, every other operation gives null. Timestamps of "set" operations only increase.

What to write

function solve(operations: string[], values: (string | number)[][]): (string | null)[]

Input
operations = ["TimeMap","set","get","get","set","get","get"]
values = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]

Output
[null,null,"bar","bar",null,"bar2","bar2"]

Input
operations = ["TimeMap","get","set","get"]
values = [[],["x",1],["x","y",2],["x",1]]

Output
[null,"",null,""]

Constraints

Set timestamps strictly increase.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The timestamps of the "set" operations only increase. So if you write down each key's values in the order they arrive, they are already in order of time. Nothing ever has to be sorted or squeezed in between two older values.

2. Hint 2: Ask a smaller question

   Suppose one key was set at times 10, 20, 30 and 40, and a "get" asks for its value at time 25. Which of the four values is the answer? What about time 40, and time 5? Say in words which one you look for each time.

3. Hint 3: Name the pattern

   Each key's values are in order of time, and a "get" asks where one time falls in that order. To find a place in sorted data you do not need to look at every entry: check the middle one and drop the half that cannot matter. That is binary search on a sorted range. Read the lesson on binary search on a sorted range.

4. Hint 4: State the invariant

   Call a timestamp with its value a pair. Count the key's pairs set at or before the asked time. Keep two marks: every pair before the first mark counts, and every pair from the second mark on is too late. Each round settles the middle pair between the marks and all the pairs on one side of it.

5. Hint 5: Sketch the pseudocode

   Each key has a list of (time, value) pairs. set: add the pair at the end. get: low = 0, high = the list's length. While low < high: mid = middle; time at mid <= asked time: low = mid + 1, else high = mid. Result: "" if low is 0, else the value at low - 1.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Keep each key’s timestamped values in append order. Use upper-bound binary search to find the last timestamp at most the query.

The slow way

Keep every value of a key in a list, each paired with its timestamp. For a get, walk that list from the newest pair back and return the first one set at or before the asked time, the timestamp of the get. It is correct, but one get can walk over every pair of a key that was set many times.

The insight

The timestamps of the sets only increase, so a list filled in the order of arrival is already sorted by time. In such a list the pairs set at or before the asked time all come first, and the later ones follow. The answer is the last pair of the first group, and halving the list finds where that group ends.

Step by step

1. Keep a list of timestamp and value pairs for each key. A key can be set many times, and a get may ask about any moment. So every value has to stay, together with the time it was set.
2. Handle the operations in order and give one result for each. The answer is a list with one entry per operation, in the same order. Only a get produces a value. Creating the store and setting a value give null.
3. A set adds its timestamp and value to the end of the key's list. The timestamps of the sets only increase, so a pair added at the end is the newest one. Every list stays sorted by time without any sorting. A key gets its list the first time it is set.
4. A get counts the key's pairs set at or before the asked time. Those pairs come first in the sorted list, so their number says where the answer is. The search looks at the middle of the pairs not decided yet. A key that was never set has an empty list.
5. The middle pair counts, so every pair before it counts too. The list is sorted by time, so every pair before the middle one was set even earlier. All of them count without being looked at, and the search goes on after the middle pair.
6. The middle pair is too late, so every pair after it is too. Too late means set after the asked time. Every pair after the middle one was set later still, so none of them counts either. The search goes on among the pairs before the middle one.
7. The last pair counted holds the answer; with none counted it is "". The counted pairs are exactly the ones set at or before the asked time, and the last of them is the latest. With nothing counted, the key had no value yet at that time.

The same numbered steps are the comments in each solution.

function solve(operations, values) {
  // 1. Keep a list of timestamp and value pairs for each key
  const store = new Map();
  // 2. Handle the operations in order and give one result for each
  return operations.map((op, i) => {
    // "TimeMap" only creates the store, so it has no result.
    if (op === "TimeMap") return null;
    const key = String(values[i][0]);
    if (op === "set") {
      // 3. A set adds its timestamp and value to the end of the key's list
      if (!store.has(key)) store.set(key, []);
      store.get(key).push([Number(values[i][2]), String(values[i][1])]);
      return null;
    }
    // 4. A get counts the key's pairs set at or before the asked time
    const a = store.get(key) || [],
      t = Number(values[i][1]);
    let l = 0,
      r = a.length;
    while (l < r) {
      const m = (l + r) >>> 1;
      if (a[m][0] <= t) {
        // 5. The middle pair counts, so every pair before it counts too
        l = m + 1;
      } else {
        // 6. The middle pair is too late, so every pair after it is too
        r = m;
      }
    }
    // 7. The last pair counted holds the answer; with none counted it is ""
    return l ? a[l - 1][1] : "";
  });
}

function solve(
  operations: string[],
  values: (string | number)[][],
): (string | null)[] {
  // 1. Keep a list of timestamp and value pairs for each key
  const store = new Map<string, [number, string][]>();
  // 2. Handle the operations in order and give one result for each
  return operations.map((op, i) => {
    // "TimeMap" only creates the store, so it has no result.
    if (op === "TimeMap") return null;
    const key = String(values[i][0]);
    if (op === "set") {
      // 3. A set adds its timestamp and value to the end of the key's list
      if (!store.has(key)) store.set(key, []);
      store.get(key)!.push([Number(values[i][2]), String(values[i][1])]);
      return null;
    }
    // 4. A get counts the key's pairs set at or before the asked time
    const a = store.get(key) || [],
      t = Number(values[i][1]);
    let l = 0,
      r = a.length;
    while (l < r) {
      const m = (l + r) >>> 1;
      if (a[m][0] <= t) {
        // 5. The middle pair counts, so every pair before it counts too
        l = m + 1;
      } else {
        // 6. The middle pair is too late, so every pair after it is too
        r = m;
      }
    }
    // 7. The last pair counted holds the answer; with none counted it is ""
    return l ? a[l - 1][1] : "";
  });
}

def solve(operations, values):
    # 1. Keep a list of timestamp and value pairs for each key
    store = {}
    # 2. Handle the operations in order and give one result for each
    out = []
    for op, args in zip(operations, values):
        result = None
        if op == "set":
            # 3. A set adds its timestamp and value to the end of the key's list
            key, value, timestamp = args
            store.setdefault(key, []).append((timestamp, value))
        elif op == "get":
            # 4. A get counts the key's pairs set at or before the asked time
            key, timestamp = args
            entries = store.get(key, [])
            left, right = 0, len(entries)
            while left < right:
                mid = (left + right) // 2
                if entries[mid][0] <= timestamp:
                    # 5. The middle pair counts, so every pair before it counts too
                    left = mid + 1
                else:
                    # 6. The middle pair is too late, so every pair after it is too
                    right = mid
            # 7. The last pair counted holds the answer; with none counted it is ""
            result = entries[left - 1][1] if left else ""
        # "TimeMap" and "set" leave the result as None.
        out.append(result)
    return out

Example 1, traced

Input
operations = ["TimeMap","set","get","get","set","get","get"]
values = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]

Output
[null,null,"bar","bar",null,"bar2","bar2"]

Why it works

The list is sorted by time, so the pairs that count are at the front and the pairs that are too late are at the back. Each round the middle pair settles itself and every pair on one side of it, so no pair lands in the wrong group. When no pair is left undecided the count is exact, and the last pair counted is the latest one.

Time and space

Time O(1) set; O(log n) get, extra space O(total sets). A set adds one pair at the end of a list, about one step whatever its length: O(1). A get halves the pairs still undecided every round, so a key with n pairs needs about log n rounds: O(log n). Each set stores one pair: O(total sets) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Compare timestamps with "at or before", not "before": a pair set at exactly the asked time must count. With "before", get foo at 1 in example 1 returns "" instead of "bar".
• A get may find nothing to count. Give a key that was never set an empty list, and return "" for a count of zero. If either is missing, example 2 stops with an error at its first get.
• The count is one more than the position of the last pair counted. Reading the pair at the count goes one too far: in example 1, get foo at 1 reads past the end of its one-pair list, an error.

Pattern

Binary search on a sorted range. Builds on Group Anagrams and Binary Search.

Keep going