Day 82: Rate Limiter (coding + design)

Day 82 — Rate Limiter (coding + design)

Coding problem

Solution outline (coding)

• Clarify: fixed window vs sliding; per-user vs global; distributed vs single machine.
• Implement token bucket or leaky bucket with timestamps in a deque or counter map.
• Discuss atomicity if multi-threaded.

Time complexity: O(1) per check amortized for simple schemes.

Space complexity: O(users) or O(window) — depends on design.

class ReviewDay:
  """Practice / review: Rate Limiter (coding + design)."""

  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: Netflix

Netflix-style: cohort retention, engagement rollups, and subscription analytics—often with strict user grain and time-based windows.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Netflix**-scale surfaces (ads, product, or engagement — as the tables suggest).
api_requests(user_id, ts). BigQuery: implement token-bucket-style rate limiter report that flags users exceeding per-minute thresholds across regions.

Tables implied by the prompt:

• api_requests(user_id, 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 Design to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Rates: SAFE_DIVIDE or NULLIF; define numerator and denominator.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT user_id, DATE_TRUNC(ts, MINUTE) AS minute_bucket, COUNT(*) AS req_cnt
FROM api_requests
GROUP BY user_id, minute_bucket
HAVING req_cnt > @limit_per_minute;