Amazon VO Coding 高频题清单

这本 mdBook 是基于一亩三分地和 Reddit 的公开可见内容整理的 Amazon VO coding 高频题单。

目标不是做“纯 LeetCode 抄录”，而是把社区里反复出现的 Amazon VO coding 题型，整理成一个可以直接复习的版本：

• 保留社区原始描述
• 尽量还原真实面试题意
• 给出标准解法与面试讲法
• 补上练习路径和资料索引

建议按这个顺序使用：

1. 先看 VO Coding 高频题总表，知道什么最常见。
2. 再看 题目还原与解法，按题型刷一轮。
3. 最后看 资料与文档清单，补模式、模板和 mock。

如果你只有 3 天：

1. 先刷 Cache / BFS-DFS / Tree / Sliding Window
2. 然后刷 Random O(1) / Binary Search / Topological Sort
3. 最后过一遍 原始题源索引，熟悉社区里真实的问法

这本书里的“还原题目”分两类：

• 高可信：社区原描述已经能明确定位题意
• 中可信：社区只给了模糊描述，我按常见 Amazon 追问方式做了保守还原

使用说明与还原方法

我怎么定义“高频”

这本书不按 LeetCode 公司标签直接照搬，而是按下面三类证据综合判断：

• 一亩三分地公开可见面经里反复出现
• 一亩三分地总结帖直接把题列成高频清单
• Reddit 讨论里有人明确说 Amazon 实际问到过

我怎么处理“原帖隐藏”问题

一亩三分地很多正文被隐藏，但公开页面通常还能看到：

• 标题
• meta description
• 搜索引擎 snippet
• 页面中未完全隐藏的总结段落

所以每道题我都会分开写：

• 社区原始描述
• 还原题目
• 解法

其中：

• “社区原始描述”尽量保持原意，不扩大
• “还原题目”是我根据公开线索和 Amazon 常见出题方式整理的复盘版
• 如果无法完全确认，我会标成“中可信还原”

使用建议

做 Amazon VO coding，不要只背题号，要同时准备三件事：

• 5 分钟内说清楚 brute force 到 optimal 的路线
• 能手写核心数据结构
• 能扛住 follow-up：复杂度、边界、tradeoff、如何扩展

从 Reddit 的公开讨论看，Amazon loop 很常见的问题不是题太偏，而是：

• BQ 占时长，coding 被压缩
• interviewer 会临时加 follow-up
• 同一道题会从“能做出来”继续追到“能不能更快/更省空间/支持重复值/支持并发”

所以这本书里每道题都默认补一个 follow-up 方向。

VO Coding 高频题总表

下面这张表是按公开题源信号强弱整理的第一版。

一句话结论

如果你只剩很短时间，先把下面 8 个做熟：

1. LRU Cache
2. LFU Cache
3. Word Ladder
4. Word Search
5. Word Break I / II
6. LCA + Diameter + Path Sum
7. Insert Delete GetRandom O(1)
8. Search in Sorted Array of Unknown Size

题目还原与解法

1. Cache 家族

1.1 LRU / LFU / Custom Cache

优先级：S

社区原始描述：

• 一亩三分地有帖直接写到“实现一个 cache”
• 另一帖公开描述里写到 “missed cache 和 LRU cache simulation”
• 还有 Reddit 用户明确说 Amazon 问过 LRU Cache，另一个回复说自己被问到 LFU Cache

还原题目：

• 设计一个缓存系统，支持 get(key) 和 put(key, value)，超出容量时按最近最少使用淘汰
• follow-up 常见会改成：
  • LFU
  • 支持 miss count
  • 让你解释为什么能做到 O(1)
  • 问如果要支持并发或 TTL 怎么改

核心解法：

• LRU: HashMap + Doubly Linked List
• LFU: key -> node，freq -> doubly linked list，再维护 min_freq
• 面试时先讲：
  • 为什么单链表不够
  • 为什么需要 O(1) 删除任意节点
  • eviction 时怎么保证正确更新

易错点：

• 更新已有 key 时忘记移动节点
• 容量为 0
• LFU 在频率升级后没有正确更新 min_freq
• 删除尾节点后没同步从 map 去掉

建议练习：

• LeetCode 146 LRU Cache
• LeetCode 460 LFU Cache
• 自己口述一个 TTL cache 的扩展版本

2. Graph / BFS / DFS 家族

2.1 Word Ladder

优先级：S

社区原始描述：

• 一亩三分地总结帖直接写：bfs dfs考的很多，word ladder，word search基本成了必考

还原题目：

• 给 beginWord、endWord 和字典，每次只能改一个字符，问最短转换长度
• follow-up：
  • 输出路径而不只是长度
  • 优化时间复杂度

核心解法：

• 标准 BFS
• 进阶直接讲 bidirectional BFS
• 若 interviewer 追优化，讲：
  • wildcard pattern 预处理
  • 双向 BFS 降搜索空间

易错点：

• endWord 不在字典里
• 访问标记时机不对导致重复入队
• 复杂度说不清楚

建议练习：

• LeetCode 127 Word Ladder
• LeetCode 126 Word Ladder II

2.2 Word Search

优先级：S

社区原始描述：

• 同一篇总结帖把 word search 和 word ladder 放在一起，直接说成“基本成了必考”

还原题目：

• 在二维网格中找一个单词，字符可上下左右移动，同一个格子不能重复使用
• follow-up：
  • 多个单词版本
  • 如何剪枝

核心解法：

• DFS + Backtracking
• 多单词时讲 Trie + DFS

易错点：

• 访问标记恢复
• 边界判断顺序
• 多单词版本没有做前缀剪枝

建议练习：

• LeetCode 79 Word Search
• LeetCode 212 Word Search II

2.3 Course Schedule

优先级：A

社区原始描述：

• 一亩三分地总结帖直接列出了 210 course schedule

还原题目：

• 给依赖关系，判断能否完成所有课程，或输出一种可行顺序

核心解法：

• Topological Sort
• BFS(Kahn) 和 DFS cycle detection 都要会讲

易错点：

• 边方向说反
• 只会判断可行，不会输出顺序

建议练习：

• LeetCode 207
• LeetCode 210

3. DP / Backtracking 家族

3.1 Word Break I / II

优先级：S

社区原始描述：

• 总结帖直接列了 139 140 word break
• 另一个 VO 准备帖里明确出现：wordbreak II。follow up 问能不能更快

还原题目：

• Word Break I: 判断字符串能否被字典拆分
• Word Break II: 输出所有合法拆分
• follow-up：
  • 如何减少重复搜索
  • 如何更快

核心解法：

• Word Break I: DP
• Word Break II: DFS + memo
• 如果 interviewer 继续问优化，可以讲 Trie + memo

易错点：

• Word Break II 没做 memo 导致指数爆炸
• 字符串切片过多，解释不清性能瓶颈

建议练习：

• LeetCode 139
• LeetCode 140
• LeetCode 472 Concatenated Words

3.2 0-1 Knapsack / Edit Distance

优先级：B

社区原始描述：

• 总结帖列出 0-1 knapsack
• 同帖列出 72 edit distance

还原题目：

• 这类题在 Amazon VO 里更像“验证你是否掌握标准 DP 推导”的保底题

核心解法：

• 背包：状态定义、二维到一维压缩
• 编辑距离：dp[i][j] 表示前缀最小编辑次数

建议练习：

• LeetCode 72
• 经典 0-1 背包模板

4. Tree 家族

4.1 LCA / Diameter / Path Sum / Boundary / Vertical Order

优先级：S

社区原始描述：

• 总结帖列出：
  • 236 lca of tree
  • 545 boundary of tree
  • 314 binary vertical traversal
  • 437 path sum
  • 543 diameter of tree
• 另一帖还有一句：bottom view of a binary tree，题目一贴出来我就觉得和 vertical 那道题差不多

还原题目：

• Amazon 很喜欢把二叉树基础题包装成 traversal 变体
• 常见问法：
  • 最近公共祖先
  • 树的直径
  • 路径和计数
  • 边界遍历
  • vertical order / bottom view

核心解法：

• LCA: 递归返回左右子树命中情况
• Diameter: 后序遍历，同时维护最大值
• Path Sum III: 前缀和 + hashmap
• Vertical Order / Bottom View: BFS 配合列坐标
• Boundary: 分左边界、叶子、右边界

易错点：

• 把 Path Sum I 和 Path Sum III 混了
• vertical order 不清楚同列同层的输出顺序
• bottom view 和 vertical traversal 混用

建议练习：

• LeetCode 236
• LeetCode 543
• LeetCode 437
• LeetCode 314
• LeetCode 545

5. 随机结构 / O(1) 设计

5.1 Insert Delete GetRandom O(1)

优先级：A

社区原始描述：

• 一亩三分地帖子直接写到：类似 380 + - random O(1)，follow up 如果有dup怎么办

还原题目：

• 设计一个数据结构，支持：
  • insert
  • remove
  • getRandom
• 所有操作尽量 O(1)
• follow-up：如果允许重复值怎么办

核心解法：

• 标准版：array + value_to_index
• 重复值版：array + value_to_indices(set)

易错点：

• 删除时忘记交换最后一个元素
• 交换后没更新被换元素的下标
• 重复值版没同步更新 index set

建议练习：

• LeetCode 380
• LeetCode 381

6. Binary Search / Unknown Size

6.1 Search in Sorted Array of Unknown Length

优先级：A

社区原始描述：

• 一亩三分地 Amazon VO 帖里明确写到：search element in one sorted array which has infinate length

还原题目：

• 给一个有序数组，但你不知道长度，查目标值位置
• follow-up：如果数组其实是有限的，只是你拿不到长度，怎么办

核心解法：

• 先指数扩张右边界：1, 2, 4, 8...
• 再在 [left, right] 上做二分

易错点：

• 边界扩张时越界处理说不清
• 把“未知长度”误解成“真的无限”

建议练习：

• LeetCode 702 Search in a Sorted Array of Unknown Size

7. Sliding Window / String

7.1 找所有排列出现位置

优先级：A

社区原始描述：

• 一亩三分地帖子给出的描述非常接近原题：给两个string，在string1中找到所有符合string2的排列组合的subsequence，返回相应的index

还原题目：

• 在长串中找所有子串起点，使该子串是短串的一个排列
• 本质是 find all anagrams / permutation in string

核心解法：

• 固定窗口长度
• 维护频次数组或 hashmap
• 窗口右移时增一个、减一个

易错点：

• subsequence 和 substring 在原帖里可能被混说，但题意明显是固定长度窗口匹配
• 字典比较复杂度不会讲

建议练习：

• LeetCode 438 Find All Anagrams in a String
• LeetCode 567 Permutation in String

8. Heap / Selection

8.1 Kth Largest Element

优先级：A

社区原始描述：

• 一亩三分地总结帖直接列出 215 kth largest element in array

还原题目：

• 给数组和 k，返回第 k 大元素

核心解法：

• min-heap 大小 k
• 或 quickselect

易错点：

• 第 k 大和排序下标混淆
• 只会堆，不会解释 quickselect 的平均复杂度

建议练习：

• LeetCode 215

9. Greedy

9.1 Gas Station

优先级：B

社区原始描述：

• 一亩三分地总结帖直接列出 134 gas station

还原题目：

• 判断从哪个站点出发可以环绕一圈

核心解法：

• 总油量不足直接失败
• 线性扫描维护当前油量，跌破 0 就重置起点

10. 小型设计编码题

10.1 Calendar / Meeting Schedule

优先级：B

社区原始描述：

• 一亩三分地 VO 帖里明确写到：设计一个日历系统，要求支持“创建事件”“查看某个时间是否 busy”“查看某日的所有事件”

还原题目：

• 这类题介于 coding 和 LLD 之间
• 面试官想看：
  • 数据结构选择
  • 时间区间冲突判断
  • API 设计
  • 复杂度解释

核心解法：

• 单用户版可先用：
  • date -> sorted intervals
  • TreeMap / ordered list
• 如果 interviewer 继续问，讲：
  • 重叠校验
  • recurring events
  • 多时区
  • 并发写入

最后怎么刷

推荐顺序：

1. LRU / LFU
2. Word Ladder / Word Search
3. Word Break / Concatenated Words
4. LCA / Diameter / Path Sum / Vertical Order
5. Random O(1) / Unknown Size Binary Search
6. Course Schedule / Kth Largest / Gas Station

如果你要 mock Amazon VO，建议每题都强制自己回答这 4 句：

1. 暴力解是什么
2. 为什么不够好
3. 最优结构为什么是这个
4. 如果 interviewer 要我继续优化，我准备怎么扩展

资料与文档清单

这本书内置的复习主线

1. 高频题总表
2. 题目还原与解法
3. 原始题源索引

你应该额外准备的文档

必备模板

• LRU / LFU 模板
• BFS / DFS / Backtracking 模板
• Topological Sort 模板
• Sliding Window 模板
• Tree DFS + prefix sum 模板
• Heap / Quickselect 模板
• Binary Search on answer / boundary 模板

Amazon VO 特别要准备的“讲法文档”

• 如何从 brute force 讲到 optimal
• 如何分析时间复杂度和空间复杂度
• 如何应对 follow-up：
  • 支持重复值
  • 支持并发
  • 支持 TTL
  • 支持大数据量
  • 如何从单机扩到分布式

建议 mock 清单

• 45 分钟 mock：15 分钟 BQ + 25 分钟 coding + 5 分钟 follow-up
• 20 分钟压缩 mock：只做“澄清 + 方案 + 编码 + testcase”
• 每次 mock 至少覆盖一题 cache 和一题 graph/tree

外部资料索引

一亩三分地

• LC 淘帖合集：https://www.1point3acres.com/bbs/collection/240817
• Amazon onsite 总结帖：https://www.1point3acres.com/bbs/thread-531445-1-1.html
• Amazon VO 过经与准备帖：https://www.1point3acres.com/bbs/thread-493883-1-1.html

Reddit

• 频率榜是否有用的讨论，里面有人明确反馈 Amazon 问到 LRU、LFU：https://www.reddit.com/r/leetcode/comments/1ivwbp1/do_the_percompany_frequency_rankings_matter_for/
• Amazon SDE2 loop 体验讨论，能看出 coding 时间常被压缩、follow-up 很多：https://www.reddit.com/r/leetcode/comments/1mtr7t3/amazon_sde2_loop_rant_frustrating_experience/

3 天压缩版计划

Day 1

• LRU
• LFU
• Word Ladder
• Word Search

Day 2

• Word Break I / II
• LCA
• Path Sum III
• Vertical Order

Day 3

• Random O(1)
• Unknown Size Binary Search
• Course Schedule
• Kth Largest
• 快速过所有 source links

原始题源索引

下面只收录这本书实际用到的公开可见题源。

一亩三分地

1. Amazon onsite 面经总结

• 链接：https://www.1point3acres.com/bbs/thread-531445-1-1.html
• 可见关键信号：
  • bfs dfs考的很多，word ladder，word search基本成了必考
  • Coding: 1. 140 wordbreak ... 13. 127 word ladder ... 15. 380 + - random O(1) ... 19. 215 kth largest element in array
• 用途：
  • 作为整本书的“高频题总表”主证据

2. Amazon VO 过经 + 准备帖

• 链接：https://www.1point3acres.com/bbs/thread-493883-1-1.html
• 可见关键信号：
  • wordbreak II。follow up 问能不能更快
  • bottom view of a binary tree
  • 类似380 + - random O(1)...如果有dup怎么办
  • 设计一个日历系统
  • 给两个string...返回相应的index
• 用途：
  • 还原 follow-up 风格
  • 还原 sliding window / calendar / random O(1) 题意

3. Amazon VO 面经

• 链接：https://www.1point3acres.com/bbs/thread-889394-1-1.html
• 可见关键信号：
  • 一共4轮，3轮coding，1轮SD
  • 第一轮...实现一个计算器
  • 第二轮...实现一个cache
• 用途：
  • 证明 Amazon VO coding 里会出现偏实现型题目

4. Amazon video 面经

• 链接：https://www.1point3acres.com/bbs/thread-156066-1-1.html
• 可见关键信号：
  • missed cache 和 LRU cache simulation
• 用途：
  • 强化 cache 家族频率判断

5. Amazon VO 面经

• 链接：https://www.1point3acres.com/bbs/thread-750586-1-1.html
• 可见关键信号：
  • 第一轮 系统设计 TinyUrl
  • 第三轮 伊斯流 和 买水果
• 用途：
  • 说明 VO 里 design 和 coding 可能混搭

6. Amazon NG 三轮 VO

• 链接：https://www.1point3acres.com/bbs/thread-849964-1-1.html
• 可见关键信号：
  • search element in one sorted array which has infinate length
• 用途：
  • 作为 unknown-size binary search 的直接证据

Reddit

1. 频率榜是否有用

• 链接：https://www.reddit.com/r/leetcode/comments/1ivwbp1/do_the_percompany_frequency_rankings_matter_for/
• 可见关键信号：
  • 有用户明确说自己 Amazon 面试被问到 LRU Cache
  • 另一个回复说自己被问到 LFU Cache
• 用途：
  • 给 cache 家族增加跨社区证据

2. Amazon SDE2 loop 体验

• 链接：https://www.reddit.com/r/leetcode/comments/1mtr7t3/amazon_sde2_loop_rant_frustrating_experience/
• 可见关键信号：
  • coding 往往在大量 LP 之后被压缩
  • 设计 / coding 追问会很多
• 用途：
  • 指导这本书为什么强调 follow-up 和压缩表达

可信度说明

• 高可信：公开文本已足够指向具体题型
• 中可信：社区描述不足以 100% 锁定原题，但可以锁定常见题型

这本书里绝大多数 S 级题都属于高可信。