DDIA Ch12
维护物化视图
Question: Top K 是实时算还是维护物化视图？
维护 per-window materialized view，查询只读最近完成的窗口或 bounded-staleness snapshot。
第 7 周 - 第 3 天 - 2026-09-09 WED - FULL - Top K HLD
YouTube Top K FULL: all-time and tumbling-window HLD
今日目标
把 Top K 从 SQL ORDER BY 进化到 view-event stream, window aggregates, and materialized Top K view.
| 08:50-09:00 | Set target 定义 Top K contract: exact, max K=1k, windows, and tolerated staleness. |
|---|---|
| 09:00-10:05 | Attempt then read 25-35 分钟闭卷设计 Top K，再读 requirements, API, all-time and tumbling-window HLD. |
| 10:05-10:45 | Decision note 写 all-time counter, hourly aggregate row, query bottleneck, and materialized view option. |
| 10:45-10:55 | Spoken close 英语复述 exact tumbling-window Top K, including why query latency forces precompute. |
| 14:30-16:15 | NeetCode Trees Exactly three contiguous Trees slots. Each slot is 30m solve + 5m pattern/invariant/bug/complexity evidence. |
| 20:30-21:15 | Recall / Q&A / repair 20:30-21:15 Top K English recall outline: state the contract, HLD, and first bottleneck without notes. |
Exact source links
Use original Hello Interview titles and current canonical anchors. Inline Bad/Good/Great headings without standalone live anchors link to their parent canonical section.
| Original title / direct link | Disposition | Use |
|---|---|---|
| Understanding the Problem | required reading | precise Top K over YouTube views |
| Functional Requirements | required reading | query top K for supported windows |
| Non-Functional Requirements | required reading | 1 minute delay, precise results, tens of ms reads, massive events/videos |
| The Set Up | required reading | incremental design route |
| Planning the Approach | required reading | all-time first, then windows, then bottlenecks |
| Defining the Core Entities | required reading | Video, View, Time Window |
| API or System Interface | required reading | GET /views/top-k?window=... |
| High-Level Design | required reading | view event stream, counters, top-K service |
| 1) Clients should be able to query the top K videos for all-time (up to a max of 1k results). | required reading | all-time counters and sorted index |
| 2) Clients should be able to query tumbling windows of 1 {hour, day, month} and all-time (up to a max of 1k results). | required reading | window rows, group/sum/query bottleneck |
DDIA decision cards
Only exact Ch11/Ch12/Ch13 sections that change today's design are assigned.
DDIA Ch12
窗口的类型
Question: 1h/1d/1m 的窗口到底是什么？
面试先选 tumbling；如果要 sliding，再讨论增量和过期 decrement 的成本。
算法模块
Contiguous live NeetCode Trees order. No reviews. Three slots per day.
| # | Problem / mode | Pattern | Invariant | Bug risk | Time | Space |
|---|---|---|---|---|---|---|
| 7 | Diameter of Binary Tree NEW - 30m solve + 5m evidence | 后序高度 + 全局答案 | 经过节点的路径长度为 leftHeight + rightHeight。 | 把节点数和边数混淆。 | O(n) | O(h) |
| 8 | Balanced Binary Tree NEW - 30m solve + 5m evidence | 后序剪枝 | 任一子树高度差大于 1 即不平衡。 | 发现 -1 后仍继续覆盖结果。 | O(n) | O(h) |
| 9 | Same Tree NEW - 30m solve + 5m evidence | 双树同步 DFS | 两个节点同时为空或值相同且左右子树相同。 | 一个空一个非空未先判。 | O(n) | O(h) |
今日验收
| Output | Top K first attempt, corrected HLD, window contract, and latency/bottleneck note. |
|---|---|
| Hard fail | Passive reading without a spoken answer; missing invariant/failure/recovery/metric; any day outside Week 7 touched. |
| Repair | Pick the weakest answer and redo it for 8 minutes with one new failure window. |
Detailed lecture notes, audio, recall scripts, PDFs, Staff Q&A, and mock packs are archived locally and are intentionally not published on this site.