Day 59: Time Based Key-Value Store

Day 59 — Time Based Key-Value Store

Coding problem

Solution outline (coding)

• Map key -> list of (timestamp, value) sorted by time.
• set appends; get binary searches last timestamp ≤ t.

Time complexity: O(log T) per query if T entries per key.

Space complexity: O(total events).

import bisect
from collections import defaultdict


class TimeMap:
  def __init__(self):
    self.store = defaultdict(list)

  def set(self, key: str, value: str, timestamp: int) -> None:
    self.store[key].append((timestamp, value))

  def get(self, key: str, timestamp: int) -> str:
    arr = self.store.get(key, [])
    i = bisect.bisect_right(arr, (timestamp, chr(127))) - 1
    return '' if i < 0 else arr[i][1]


# Input:  set foo bar 1, get foo 3 -> "bar" if latest <=3
# Output: string value or ""

SQL interview practice

1. Interview question

Companies / track: OpenAI, Anthropic

Frontier AI labs: SQL mirrors ML infra and evaluation—experiment tables, logging joins, and metric definitions with reproducible grain and clear ownership of keys.

What you are asked to write (SQL prompt):

Frame this as metrics work for **OpenAI, Anthropic**-scale surfaces (ads, product, or engagement — as the tables suggest).
time_kv(store, key, value, ts). BigQuery: implement efficient lookup of latest value before given ts per key using partitioning and window functions.

Tables implied by the prompt:

• time_kv(store, key, value, ts)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map Bin. Search / Design to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Filter time first: predicate on DATE(ts) / partition column before heavy joins; state the window in plain English.
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT store, key, ARRAY_AGG(STRUCT(ts, value) ORDER BY ts DESC LIMIT 1)[OFFSET(0)].value AS latest_before
FROM time_kv
WHERE ts <= @as_of_ts
GROUP BY store, key;