Day 18: LRU Cache

Day 18 — LRU Cache

Coding problem

Solution outline (coding)

• Combine hash map (key → node) with a doubly linked list for LRU order (head = MRU, tail = LRU).
• get: move node to front; if missing, return -1. put: insert or update; evict tail if over capacity.
• All operations must update both structures consistently.

Time complexity: O(1) average per get and put with a proper DLL + map.

Space complexity: O(capacity) — at most capacity key-value pairs.

from collections import OrderedDict


class LRUCache:
  def __init__(self, capacity: int):
    self.cap = capacity
    self.od = OrderedDict()

  def get(self, key: int) -> int:
    if key not in self.od:
      return -1
    self.od.move_to_end(key)
    return self.od[key]

  def put(self, key: int, value: int) -> None:
    if key in self.od:
      self.od.move_to_end(key)
    self.od[key] = value
    if len(self.od) > self.cap:
      self.od.popitem(last=False)


# Input:  capacity 2, put(1,1), put(2,2), get(1), put(3,3) evicts key 2
# Output: get(2) -> -1

SQL interview practice

1. Interview question

Companies / track: Anthropic, Meta

Research + product scale: combines rigorous definitions (common at research labs) with Meta-style event logs, cohorts, and high-volume joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Anthropic, Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
cache_logs(key, ts, op, hit). BigQuery: compute hit rate per key and moving hit rate per hour; design a query that surfaces keys with sudden degradation in hit rate compared to 24h baseline.

Tables implied by the prompt:

• cache_logs(key, ts, op, hit)

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

WITH hourly AS (
  SELECT key, TIMESTAMP_TRUNC(ts, HOUR) AS hr,
    AVG(IF(hit, 1.0, 0.0)) AS hit_rate
  FROM cache_logs
  GROUP BY key, hr
),
baseline AS (
  SELECT key, AVG(hit_rate) AS baseline_24h
  FROM hourly
  WHERE hr >= TIMESTAMP_SUB(TIMESTAMP_TRUNC(CURRENT_TIMESTAMP(), HOUR), INTERVAL 24 HOUR)
  GROUP BY key
)
SELECT h.key, h.hr, h.hit_rate, b.baseline_24h,
  h.hit_rate - b.baseline_24h AS delta
FROM hourly AS h
JOIN baseline AS b USING (key)
WHERE h.hr >= TIMESTAMP_SUB(TIMESTAMP_TRUNC(CURRENT_TIMESTAMP(), HOUR), INTERVAL 1 HOUR)
  AND h.hit_rate < b.baseline_24h * 0.7;