这次分享的是一场 Amazon SDE OA 面经，主要记录 Coding Assessment 中遇到的两道题。从题型来看，一道偏 Dynamic Programming，另一道偏 Hash Table + Heap 的数据结构设计。两道题的考察方向不同，但都比较注重对状态、数据结构以及边界情况的处理。
需要注意的是，Amazon SDE OA 的具体形式会根据岗位、地区和招聘流程有所不同。Amazon 官方也说明，SDE OA 的结构并非所有岗位完全一致，因此下面的题目主要作为一次实际面经参考。
Amazon SDE OA 包含什么？
Amazon 官方资料显示，SDE Online Assessment 会考察 Coding、Technical Problem Solving，以及与 Leadership Principles 相关的部分内容。对于学生和应届 SDE 岗位，Coding Assessment 平均约 70 分钟，完整 OA 的具体组成则可能因岗位和地区有所变化。
因此，准备 Amazon SDE OA 时，除了熟悉常见算法题，还需要注意：
- Dynamic Programming
- Hash Table
- Heap / Priority Queue
- Graph / Grid
- Sorting
- Two Pointers
- Sliding Window
- 时间和空间复杂度分析
Amazon 官方也建议候选人在 Coding Assessment 中重点练习代码实现、问题拆解和边界情况处理。
Amazon SDE OA Coding 题目
T1：最多穿过 K 个障碍的路径数量
题意
给一个有障碍的网格，机器人从左上角出发，每次只能向右或向下走，最多穿过 k 个障碍，求走到右下角一共有多少条不同的路径，结果按要求取模。
解题思路
这道题可以使用三维 DP。定义：dp[i][j][t]，表示到达 (i, j) 时，一共穿过 t 个障碍的路径数量。对于当前位置 (i, j)，可以从上方或者左侧转移：dp[i][j][t] = dp[i-1][j][t-cost] + dp[i][j-1][t-cost]
其中 cost 表示当前位置是否为障碍：cost = 1 如果当前位置是障碍 ，cost = 0 如果当前位置不是障碍，同时需要保证：t<= k，这样可以避免统计超过障碍数量限制的路径。
为什么适合用 DP？
因为到达当前 Grid 位置的路径数量，只依赖于前面的状态。如果当前位置不是障碍，那么从上方和左侧转移时不增加障碍数量；如果当前位置是障碍，则需要将已经使用的障碍数量加 1。因此可以把问题拆成多个状态进行计算。
空间优化
如果直接使用三维数组，空间复杂度为：O(m × n × K)，如果 m 和 n 较大，可以进一步使用 Rolling Array 进行空间优化，将空间复杂度降低到：O(n × K)，这也是这道题比较值得关注的地方：不仅要能够写出 DP，还需要考虑状态数量以及空间使用。
T2：带访问频率的缓存淘汰
题意
实现一个有容量限制的缓存，支持写入、读取和只查看。空间不够时，先淘汰访问次数最少的数据，次数相同再淘汰最久没访问的。读取会更新访问记录，只查看不会；查不到返回负一，单条数据超过总容量就忽略这次写入。
解题思路
用哈希表保存每条数据的值、大小、访问次数和最近访问时间，再用小根堆按次数和时间排序，方便找到该淘汰的数据。记录发生变化时，把新版本放进堆，旧版本先留着，之后取出来发现过期就跳过。写入前检查容量，不够就连续淘汰，同时更新已用空间；修改已有数据时，也要先扣掉原来的大小，避免重复计算。
懒删除
这道题还有一个比较容易出错的地方，就是 Lazy Deletion。因为一个 Cache Entry 的访问频次和 timestamp 会不断变化，如果每次 GET 后都直接修改 Heap 中原来的节点，维护成本会比较高。
一种常见做法是：每次状态发生变化时，将新的状态重新加入 Heap，而不是立即删除旧节点。例如：(key=A, frequency=2, timestamp=10)，更新后：(key=A, frequency=3, timestamp=20) 那么新的状态重新加入 Heap。当 Heap 顶部出现旧状态时，再检查它是否仍然与 Hash Table 中保存的最新状态一致。如果不一致，就直接删除这个 Heap Entry，继续检查下一个。这种方式就是 Lazy Deletion。
这两道 Amazon SDE OA 题目考察什么？
虽然两道题的类型不同，但可以看到比较明显的考察方向。
1. Dynamic Programming
第一题主要考察：
- Grid DP
- 状态定义
- 多维状态
- 障碍数量限制
- 空间优化
重点不是单纯套用二维路径 DP，而是增加了 K 这个状态维度。
2. Data Structure Design
第二题则更偏向实际的数据结构组合：
- Hash Table
- Min Heap
- Frequency
- Timestamp
- Lazy Deletion
需要同时考虑查询效率和淘汰顺序。
3. Edge Cases
准备这类 OA 时，也需要提前考虑边界情况，例如：
K = 0- 起点或终点是障碍
- Grid 只有一行或一列
- Cache 容量为 1
- 多个 Entry 的 frequency 相同
- 多个 Entry 的 frequency 和 timestamp 都需要比较
- Heap 中存在已经失效的旧状态
这些情况很容易影响最终结果。
Amazon SDE OA 怎么准备？
准备 Amazon SDE OA 时，可以先围绕常见 Coding 题型进行系统练习，再重点关注解题速度和代码实现。结合这次面经，可以重点复习 Dynamic Programming、Hash Table、Heap / Priority Queue 等方向，尤其是 Grid DP、路径计数、Frequency Counting、Top K 以及需要同时维护多个状态的数据结构题。练习时不要只关注能否写出答案，还要熟悉不同数据结构的使用场景，能够快速判断题目需要维护哪些状态。
实际 Coding 时，还需要注意 Time Complexity、Space Complexity 和边界情况。完成主要逻辑后，可以主动检查 K = 0、空数据、容量限制以及多个元素状态相同等特殊 Case，确认代码在极端输入下仍能正常运行。对于时间有限的 OA，这种先确定状态和数据结构、再处理边界情况的解题方式，可以减少反复修改代码的时间。
总结
这次 Amazon SDE 中的两道 Coding 题，一道是带障碍数量限制的 Grid Dynamic Programming，另一道是结合 Hash Table、Min Heap 和 Lazy Deletion 的 Cache 模拟题。
如果只从题型来看，准备 Amazon OA 时可以重点覆盖 DP、Hash Table、Heap、Graph/Grid 和常见数据结构设计。实际 OA 的题目和流程可能因岗位及候选人情况有所不同，因此面经更适合作为题型参考，而不是固定题库。Amazon 官方也提供了 SDE OA Practice Test 和 Coding Preparation 资料，可以用来熟悉实际测试环境。
如果你正在准备 Amazon SDE OA，除了刷题，也可以结合真实面经熟悉不同题型和解题思路。InterviewShow 提供 Amazon、Google、Microsoft、Stripe、TikTok 等科技公司的SDE 面试资料与一对一面试辅导，帮助你针对Coding、System Design 和 Behavioral Interview 进行准备。
想进一步了解 Amazon SDE 面试准备，可以联系 InterviewShow 获取更多面试支持。
FAQ
Amazon SDE OA 难吗？
Amazon SDE OA 的难度会根据岗位、地区和具体测试内容有所不同。Coding 部分通常需要在有限时间内完成算法题，因此除了掌握常见数据结构和算法，还需要具备较快的问题分析和代码实现能力。对于学生和应届 SDE 岗位，建议重点练习 Dynamic Programming、Hash Table、Heap、Graph/Grid 等常见题型。
Amazon SDE OA 有几道 Coding 题？
Amazon SDE OA 的题目数量并不是所有岗位都完全固定，具体安排可能根据岗位和招聘流程有所变化。Coding Assessment 通常会在限定时间内完成若干 Coding 任务，因此准备时更应该关注题型覆盖和解题速度，而不是只记固定的题目数量。
Amazon SDE OA 考哪些算法？
Amazon SDE OA 常见的准备方向包括 Dynamic Programming、Hash Table、Heap / Priority Queue、Graph / Grid、Sorting、Two Pointers 和 Sliding Window。此外，还需要掌握 Time Complexity、Space Complexity 以及常见 Edge Cases 的处理方法。
Amazon SDE OA 会考数据结构设计吗？
部分 Coding 题会涉及数据结构的组合使用。例如本文中的 Cache 题就需要结合 Hash Table、Min Heap、Frequency 和 Timestamp，并通过 Lazy Deletion 维护 Heap 状态。这类题目不仅考察算法，还需要根据操作需求选择合适的数据结构。
Amazon SDE OA 怎么准备？
准备 Amazon SDE OA 可以从常见 Coding 题型入手，同时训练限时解题能力。除了刷题，还需要熟悉题目中的边界情况和复杂度分析。对于 Cache、Grid DP 等需要维护多个状态的题目，可以重点练习如何定义状态、选择数据结构，以及如何优化 Time Complexity 和 Space Complexity。