🏗️ 系统设计 / System Design — Day 22

设计自动补全 / Typeahead — Design an Autocomplete / Typeahead System

🌍 真实场景 / Real-World Scenario

想象你在谷歌搜索框里输入 "how to"，瞬间出现 10 条建议。这背后是什么？

Imagine typing "how to" in Google's search box and instantly seeing 10 suggestions. What's behind it?

每次用户输入一个字符，系统必须在 <100ms 内返回最相关的补全结果。谷歌、YouTube、Amazon、GitHub 都有这个功能——它看似简单，工程上却很复杂。

Each keystroke must return the most relevant completions in <100ms. Google, YouTube, Amazon, GitHub all have this — it looks simple but is engineering-hard.

🏛️ 架构图 / Architecture

数据流 / Data Flow:

1. 用户输入 → 客户端 debounce 50ms（减少请求量）
2. API Gateway → 先查 Redis cache
3. Cache miss → Trie 查找 Top-K 前缀
4. ML 模型 rerank（考虑个性化、地理位置）
5. 日志写入 Kafka → Spark 定期更新 Trie 权重

⚙️ 核心数据结构 / Core Data Structure: Trie

             root
           /  |  \
          a   b   c
         /|    \
        p  r    e
       /    \
      p      o
     /|       \
    l  [end]   w
   /            \
  e               s
  [end,"apple,5"]  [end,"browse,3"]

每个节点存储：

• children: dict
• is_end: bool
• top_k: list[{word, freq}] ← 预计算 Top-10，避免遍历

Each node stores precomputed Top-10 completions → avoids traversal on query.

关键优化： 每个节点缓存 Top-K，查询 O(prefix_length)，无需 DFS。

Key optimization: cache Top-K at each node, query is O(prefix_length), no DFS needed.

⚖️ 核心权衡 / Key Tradeoffs

为什么不实时更新 Trie？

每次搜索都更新 Trie 需要全局锁，QPS 百万级时会变成瓶颈。批量更新（每10分钟）是工程实际选择。

Why not real-time Trie updates? Global locks at million QPS become a bottleneck. Batch updates every 10 min is the engineering reality.

🚫 别踩这个坑 / Common Mistakes

❌ 坑1: 忘记 debounce

每次 keypress 都发请求 → 用户输入 "apple" = 5 个请求。加 debounce 50~100ms，节省 80% 请求。

Not debouncing = 5 requests for "apple". Add debounce 50-100ms, saves 80% of requests.

❌ 坑2: Trie 存完整路径

只存 top-K 在每个节点，不要在查询时做完整 DFS。

Store top-K at each node, don't do full DFS at query time.

❌ 坑3: 忘记限速

恶意用户可以爆破搜索建议接口。Rate limit + IP 封锁必须有。

Malicious users can hammer the suggest endpoint. Rate limiting is non-negotiable.

❌ 坑4: 大写/Unicode 不一致

输入 "Apple" vs "apple" 应该返回一样结果。存储前统一 lowercase + normalize。

"Apple" and "apple" should return same results. Normalize to lowercase before storing.

📐 规模估算 / Scale Numbers

• DAU: 10M 用户
• 平均每次搜索 5 次 keypress → 50M 建议请求/天
• QPS: ~600 req/s（峰值 2000）
• Trie 大小: 英文词典 ~100K 词 → ~50MB（可放内存）
• Cache hit rate: 60%（热词覆盖大量请求）

📚 深入阅读 / References

1. System Design Primer — Autocomplete — 经典参考
2. Designing Instagram's Typeahead Search — 真实案例
3. Trie Data Structure — NeetCode — Trie 详解

🧒 ELI5 (像我5岁一样解释)

想象你有一本超大的电话簿，里面有所有可能的词。每次你写一个字母，电话簿就帮你翻到那一页，显示最热门的词。为了不让你等太久，电话簿提前把每一页最热门的10个词写在页眉上了！

Imagine a giant phonebook. Each letter you type, the book flips to that page and shows the top 10 popular words it already wrote at the top of the page — no searching needed!

💻 算法 / Algorithms — Day 23

#150 Evaluate Reverse Polish Notation (Medium) — Stack Pattern

🧩 Stack 模式 (3/7) — 基于 Day 21 (Valid Parentheses) 和 Day 24 (Min Stack) 的模版

上次 Min Stack 用栈存最小值，这次用栈做运算——同样的工具，不同的用途。

Last time (Min Stack) we used the stack to track minimums; this time we use it to evaluate — same tool, different job.

🔗 Links

• 🔗 LeetCode #150 🟡 Medium
• 📹 NeetCode Video

🌍 现实类比 / Real-World Analogy

逆波兰表达式（RPN）是计算器的内部语言。当你在科学计算器上按 3 4 + 2 *，计算器内部其实就是在用栈处理 RPN。Forth 语言、PostScript 都基于 RPN。

RPN is the internal language of calculators. When you press 3 4 + 2 on a scientific calculator, it's processing RPN with a stack internally. Forth, PostScript are all RPN-based.*

🧩 问题 / Problem

给你一个字符串数组，表示逆波兰表达式：

Given a string array representing a Reverse Polish Notation expression:

Input: ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

🗺️ 映射到模版 / Map to Template

这道题的变化： 不是找"下一个更大元素"，而是把数字当操作数，遇到运算符就出栈计算

stack = []
for token in tokens:
    if token is NUMBER:
        stack.append(int(token))     # push
    else:
        b = stack.pop()              # 注意顺序！b是后弹出的
        a = stack.pop()              # a是先弹出的（先入栈的）
        result = apply(a, op, b)
        stack.append(result)         # push result back
return stack[0]

关键陷阱 / Key Trap: 弹出顺序！a - b 中，a 是先入栈的（先到达），所以：

先 pop b（后到），再 pop a（先到），计算 a op b。

Pop order matters! For a - b: a was pushed first, so pop b first, then a.

🐍 Python 解法 / Solution

def evalRPN(tokens: list[str]) -> int:
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b)  # truncate toward zero (not //!)
    }
    
    for token in tokens:
        if token in ops:
            b = stack.pop()   # second operand (pushed last)
            a = stack.pop()   # first operand (pushed first)
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))
    
    return stack[0]

# Trace: ["2","1","+","3","*"]
# "2" → stack: [2]
# "1" → stack: [2, 1]
# "+" → pop 1,2 → 2+1=3 → stack: [3]
# "3" → stack: [3, 3]
# "*" → pop 3,3 → 3*3=9 → stack: [9]
# return 9 ✓

注意 / 的处理！

Python // 向负无穷截断：-7 // 2 = -4

题目要求向零截断：-7 / 2 = -3

所以用 int(a / b)，不用 a // b！

Python // truncates toward negative infinity, but the problem wants truncation toward zero. Use int(a/b) not a//b!

📊 复杂度 / Complexity

• 时间 Time: O(n) — 每个 token 处理一次
• 空间 Space: O(n) — 栈最大存 n/2 个数字

🔄 举一反三 / Pattern Block: Stack (3/7)

📚 References

1. LeetCode #150 — Evaluate Reverse Polish Notation
2. NeetCode — Stack Playlist
3. Wikipedia — Reverse Polish Notation

🧒 ELI5

想象你在排队买东西，每次看到数字就记下来（放进口袋）。看到加减乘除号，就从口袋里掏出最后两个数字算完再放回去。最后口袋里只剩一个数，就是答案！

🗣️ 软技能 / Soft Skills — Day 22

成长型思维 / Growth Mindset

题目：告诉我你收到了一次很难听的反馈。你是怎么应对的？

Tell me about a time you received tough feedback. How did you respond?

🎯 为什么这道题很重要 / Why This Matters

这道题考察的不是你有没有犯过错，而是你如何面对批评。

Senior/Staff 工程师的标志之一：能从批评中学习，而不是防御或逃避。

面试官在看：自我认知、情绪成熟度、持续改进的能力。

This question doesn't test whether you made mistakes — it tests how you handle criticism. A marker of Senior/Staff engineers: learning from feedback instead of defending or deflecting. Interviewers look for: self-awareness, emotional maturity, capacity to grow.

⭐ STAR 框架 / STAR Breakdown

S — Situation（背景）:

设置具体场景。是代码评审？设计评审？绩效评估？

避免模糊的 "有一次我的老板批评了我"。

Set a specific context. Code review? Design review? Performance review? Avoid vague "my manager criticized me once."

T — Task（任务）:

你当时做的是什么项目/决策？

What were you working on or what decision had you made?

A — Action（行动）:

这是关键！要展示：

1. 你冷静地接受了反馈（没有立刻防御）
2. 你主动寻求理解（问了澄清问题）
3. 你具体做出了改变

This is the key! Show: 1) You received feedback calmly (no immediate defensiveness), 2) You sought to understand (asked clarifying questions), 3) You made concrete changes.

R — Result（结果）:

量化结果 + 长期影响（你从中学到了什么习惯？）

Quantify the result + long-term impact (what habit did you develop?)

❌ 差答案 vs ✅ 好答案 / Bad vs Good

❌ 差答案:

"有一次我老板说我沟通不好，我就多发了些邮件，后来他满意了。"

问题：太模糊、没有自我反思、没有展示成长。

Too vague, no self-reflection, no demonstrated growth.

✅ 好答案 (Sample):

"在做一个后端服务重构时，我的 Tech Lead 在代码评审中说我的 PR 很难 review——改动超过 2000 行，没有原子化。我当时第一反应是有点委屈，因为我觉得改动是连贯的。

但我没有立刻反驳，而是先问他：'你觉得最难理解的是哪部分？' 他指出我把接口变更和实现变更混在一起了。

我重新把 PR 拆成 4 个：接口定义 → 数据层 → 业务逻辑 → 集成测试。每个 PR 独立可测试。

结果 review 时间从 3 天缩短到 1 天，后来团队把'PR ≤ 400 行'写进了我们的开发规范。这个习惯我现在每个项目都在用。"

为什么好： 具体场景、初始情绪诚实、主动提问理解根因、行动可量化、有长期影响。

Why it works: specific scenario, honest about initial emotion, proactively sought root cause, quantifiable action, lasting impact.

💎 Senior/Staff 加分项 / Senior/Staff Tips

展示元认知 (metacognition):

"那次反馈让我意识到，我倾向于在「把东西做完」和「让别人容易理解」之间优先前者。这是一个我持续在调整的倾向。"

展示你帮助他人成长:

"后来我成为了团队的 code review mentorship 负责人，把这个经验传给了新人。"

避免假谦虚:

不要说 "我最大的缺点是工作太努力了"——面试官会翻白眼。

Don't say "my biggest weakness is working too hard" — interviewers will roll their eyes.

🗝️ 关键要点 / Key Takeaways

1. 诚实 > 完美 — 展示真实的成长比假装从不犯错更有说服力
2. 行动比情绪重要 — 你感受到委屈是正常的，关键是你做了什么
3. 量化长期影响 — 把个人成长转化为团队/系统改进
4. 成长型思维的核心： 失败是数据，不是定义

1. Honest > Perfect — real growth > pretending perfection. 2. Action > Emotion — feeling stung is normal, what matters is what you did. 3. Quantify long-term impact. 4. Growth mindset core: failure is data, not identity.

📚 References

1. Radical Candor — Kim Scott — 给予和接受反馈的经典框架
2. Mindset: The New Psychology of Success — Carol Dweck — 成长型思维原著
3. The STAR Method — Indeed — STAR 答题法详解

🧒 ELI5

就像在游戏里输了一局，好的玩家不会摔手柄，而是看录像找出哪里操作失误了，然后练习那个技能。面试官想看到的就是：你是那个会复盘的玩家。

Like losing a game: a good player doesn't rage-quit, they watch the replay to find the mistake and practice that skill. Interviewers want to see: are you the player who reviews the tape?

🎨 前端 / Frontend — Day 22

TypeScript Generics 深度解析 — 构建类型安全的 API Client

TypeScript Generics Deep Dive — Build a Type-Safe API Client

🌍 真实场景 / Real Scenario

你在做一个 dashboard，需要从多个 API 端点获取数据：/api/users、/api/orders、/api/products。

每个端点返回不同的数据类型，但 fetch 逻辑相同（error handling、token、timeout）。

不用 Generics 的话，你要写 3 个几乎相同的函数——有了 Generics，只写 1 个。

You're building a dashboard fetching from multiple API endpoints. Each returns different data shapes but the fetch logic is identical. Without Generics: 3 near-identical functions. With Generics: 1.

💡 从基础到实战 / From Basic to Production

❌ 没有 Generics 的痛苦:

// Must duplicate for every type — painful!
async function fetchUsers(): Promise<User[]> {
  const res = await fetch('/api/users');
  return res.json();
}
async function fetchOrders(): Promise<Order[]> {
  const res = await fetch('/api/orders');
  return res.json();  // copy-paste hell
}

✅ 用 Generic 函数:

// T = Type variable, filled in at call site
async function fetchData<T>(url: string): Promise<T> {
  const res = await fetch(url);
  if (!res.ok) throw new Error(`HTTP ${res.status}`);
  return res.json() as T;
}

// Usage — TypeScript infers the return type!
const users = await fetchData<User[]>('/api/users');   // users: User[]
const order = await fetchData<Order>('/api/orders/1'); // order: Order

🏗️ 进阶：类型安全的 API Client / Production API Client

// Define the shape of all your API endpoints
interface ApiRoutes {
  '/api/users': User[];
  '/api/orders': Order[];
  '/api/products': Product[];
}

// Generic client with endpoint type inference
class ApiClient {
  private baseUrl: string;
  private token: string;

  constructor(baseUrl: string, token: string) {
    this.baseUrl = baseUrl;
    this.token = token;
  }

  // K extends keyof ApiRoutes — K must be a valid route key
  // ApiRoutes[K] — the return type is determined by the route
  async get<K extends keyof ApiRoutes>(
    endpoint: K
  ): Promise<ApiRoutes[K]> {
    const res = await fetch(`${this.baseUrl}${endpoint}`, {
      headers: { Authorization: `Bearer ${this.token}` },
    });
    if (!res.ok) throw new Error(`Failed: ${endpoint}`);
    return res.json();
  }
}

const client = new ApiClient('https://api.example.com', 'my-token');

// TypeScript KNOWS the return type from the endpoint string!
const users = await client.get('/api/users');   // User[] — no type annotation needed!
const orders = await client.get('/api/orders'); // Order[] — inferred!
// client.get('/api/invalid'); // ❌ TypeScript ERROR! Not in ApiRoutes

魔法在哪？ TypeScript 用 K extends keyof ApiRoutes 把字符串和类型绑定在一起，让 IDE 自动补全 URL 路径，同时推断返回类型。

The magic: K extends keyof ApiRoutes binds string literals to types, giving IDE autocomplete on URLs AND inferring return types.

🤔 猜猜这段代码的类型 / What's the type?

function firstOrDefault<T>(arr: T[], defaultValue: T): T {
  return arr.length > 0 ? arr[0] : defaultValue;
}

const result = firstOrDefault([1, 2, 3], 0);

A) result: number

B) result: number | undefined

C) result: unknown

D) result: T (literal T)

<details><summary>显示答案 / Show Answer</summary>

A) result: number ✅

TypeScript 从参数推断 T = number（因为 arr 是 number[]，defaultValue 是 0），所以返回类型是 number。不需要显式写 firstOrDefault<number>(...)——TypeScript 自动推断！

TypeScript infers T = number from the arguments (number[] and 0), so return type is number. No need to write firstOrDefault<number>(...) explicitly — inference handles it!

</details>

⚖️ 常见模式对比 / Common Generic Patterns

// ✅ Constrained Generic — T must have .length
function longest<T extends { length: number }>(a: T, b: T): T {
  return a.length >= b.length ? a : b;
}
longest("hello", "hi");       // ✅ strings have .length
longest([1, 2], [1]);         // ✅ arrays have .length
longest(10, 20);              // ❌ numbers don't have .length

// ✅ Generic with default
function createPair<T = string>(a: T, b: T): [T, T] {
  return [a, b];
}
createPair("x", "y");    // T inferred as string
createPair(1, 2);        // T inferred as number
createPair();            // Uses default: T = string (TS error without args though)

// ✅ Utility type using Generics (built into TypeScript)
type Partial<T> = { [K in keyof T]?: T[K] };  // Make all fields optional
type Required<T> = { [K in keyof T]-?: T[K] }; // Make all fields required
type Pick<T, K extends keyof T> = { [P in K]: T[P] }; // Pick subset of keys

🎯 何时用 / 何时不用 / When to Use vs Avoid

✅ 用 Generics 当:

• 多个函数/类逻辑相同，只是类型不同
• 你想保留类型信息（不想用 any）
• 构建可复用的库/工具函数

❌ 不要过度使用:

• 简单函数强行加 Generic → 代码变复杂但没收益
• 类型约束太复杂 → 用 overloads 更清晰
• 只用一次的类型 → 直接写具体类型

📚 References

1. TypeScript Handbook — Generics — 官方文档
2. Matt Pocock — TypeScript Generics — 最好的 TS 教程之一
3. TypeScript Deep Dive — Generics — 深度讲解

🧒 ELI5

泛型就像饭店里的通用容器。不管是装汤还是装沙拉，容器的形状是一样的，只是里面的东西不同。function eat<T>(food: T) 就是这个通用容器——你告诉它装什么，它就知道里面是什么。

Generics are like a restaurant's all-purpose container. Whether it holds soup or salad, same container shape, different contents. function eat<T>(food: T) is that container — you tell it what's inside, and it knows.

🤖 AI — Day 26

AI Agents：ReAct、工具调用与规划

AI Agents: ReAct, Tool Use, and Planning

🧠 什么是 AI Agent？/ What Is an AI Agent?

关键区别：Agent 可以使用工具（搜索、代码执行、数据库查询）并自主规划多步骤任务。

Key difference: Agents can use tools (search, code execution, DB queries) and autonomously plan multi-step tasks.

🔄 ReAct 框架 / The ReAct Framework

ReAct = Reasoning + Acting

来源：2022 年论文 "ReAct: Synergizing Reasoning and Acting in Language Models"

循环 / The Loop:

为什么有效？ 思考（CoT）让模型推理，行动让它获取外部信息，观察让它根据现实反馈修正计划。

Why it works: Thinking (CoT) enables reasoning; Actions gather real-world data; Observations allow course correction.

🛠️ 工具调用 / Tool Use

现代 LLM（GPT-4, Claude, Gemini）支持 function calling：模型决定何时调用哪个工具。

# Define tools the agent can use
tools = [
    {
        "name": "web_search",
        "description": "Search the web for current information",
        "parameters": {
            "type": "object",
            "properties": {
                "query": {"type": "string", "description": "Search query"}
            }
        }
    },
    {
        "name": "run_python",
        "description": "Execute Python code and return output",
        "parameters": {
            "type": "object",
            "properties": {
                "code": {"type": "string", "description": "Python code to run"}
            }
        }
    }
]

# pip install openai
import openai

client = openai.OpenAI()

response = client.chat.completions.create(
    model="gpt-4o",
    messages=[{"role": "user", "content": "What's 1234 * 5678?"}],
    tools=tools,
    tool_choice="auto"  # Model decides whether to use a tool
)

# Model returns: use run_python with code="print(1234 * 5678)"
# You execute the tool, send result back, model gives final answer
print(response.choices[0].message.tool_calls)

关键点： 模型建议调用工具，你的代码实际执行它——安全边界在这里！

Key: the model suggests tool calls, your code actually executes them — the safety boundary is here!

📐 规划模式 / Planning Patterns

🌍 2026 年趋势 / 2026 Trends

• Google 开源了官方 terminal agent（April 2026），内置 ReAct 循环
• LangGraph、LlamaIndex 提供预构建的 ReAct agent 模块，快速落地
• 生产就绪挑战： 幂等性（工具重复调用结果一致）+ durable checkpoints（保存 agent 状态）
• 个人 AI Agent 预测： 自动改签机票、重排日程、下订单——复杂规划的实际落地

Sources: IBM ReAct Agent, Goldman Sachs 2026 AI Predictions, ByteByteGo AI Trends

⚠️ Agent 的挑战 / Challenges

😱 失控问题： Agent 可能无限循环或采取意外行动 → 需要 max_iterations 限制

💸 成本问题： 每次 Thought-Action-Observation 都消耗 tokens，多步任务很贵

🔒 安全问题： Prompt injection 攻击（恶意网页内容欺骗 agent）是真实威胁

🐌 速度问题： 串行规划很慢；多 Agent 并行是方向

📚 References

1. ReAct Paper (arXiv) — 原始论文
2. LangGraph — Agent Frameworks — 实用框架
3. IBM — What is a ReAct Agent? — 概念讲解

🧒 ELI5