Day 60: Key-Value Store with TTL (custom)

Day 60 — Key-Value Store with TTL (custom)

Coding problem

Solution outline (coding)

• Define operations: get, set, TTL behavior, and clock source (simulated vs real).
• Pick structure: hash map + lazy expiry, or heap of expiry times, or periodic sweep.
• Discuss memory vs accuracy trade-off for eviction.

Time complexity: O(1) average target for get/set; eviction may add O(log n) or amortized cleanup.

Space complexity: O(n) — live keys.

class ReviewDay:
  """Practice / review: Key-Value Store with TTL (custom)."""

  def practice_plan(self):
    return [
      "Pick 2–3 problems from this phase; re-solve timed without notes.",
      "For each: pattern name, time/space complexity, one alternative approach.",
    ]


# Input:  (your choice of problems from this week or phase)
# Output: a short list of gaps to drill before the next session

SQL interview practice

1. Interview question

Companies / track: Anthropic

Frontier AI lab: interviews often stress clean grain, experiment or eval metrics, and reproducible joins over logging and offline tables—similar rigor to research engineering.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Anthropic**-scale surfaces (ads, product, or engagement — as the tables suggest).
ttl_kv(store, key, value, ts, ttl_seconds). BigQuery: determine which keys are live at reference time and compute cardinality/distribution by store.

Tables implied by the prompt:

• ttl_kv(store, key, value, ts, ttl_seconds)

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 Design to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT store, COUNT(DISTINCT key) AS live_keys
FROM ttl_kv
WHERE TIMESTAMP_ADD(ts, INTERVAL ttl_seconds SECOND) > CURRENT_TIMESTAMP()
GROUP BY store;