AmazonCrackedResource第1周刷题解析从Two Sum到LRU Cache10道基础题逐个击破【免费下载链接】AmazonCrackedResourceA List of frequently asked questions in Amazons Online Assessment and Interviews项目地址: https://gitcode.com/gh_mirrors/am/AmazonCrackedResource正在备战 Amazon 面试的同学OA 刷题是第一道坎。本文基于开源题库项目 AmazonCrackedResource把第 1 周的 10 道高频题逐个击破——从最经典的 Two Sum 到设计题 LRU Cache覆盖每道题的核心思路、复杂度与避坑点帮你从零建立完整的刷题节奏。 AmazonCrackedResource 是什么AmazonCrackedResource 是一个专为Amazon OAOnline Assessment和现场面试整理的算法题库把高频题按5 周学习计划、每周 10 题、共 50 题组织成完整的刷题路线。它的特点✅ 难度从 Easy 到 Hard 分级标注适合循序渐进✅ 自带进度跟踪表Done ✅ / In Progress / Skipped ❌做完一题打个勾✅ MIT 开源协议免费使用、可自由 Fork核心题库在CrackAmazonResource.md文件里项目介绍见README.md协议文件为LICENSE。 获取完整题库一条命令克隆到本地git clone https://gitcode.com/gh_mirrors/am/AmazonCrackedResource打开CrackAmazonResource.md找到 Problems for Week 1 小节本周要练的 10 道题一目了然。 第 1 周 10 道题速览#题目难度核心技巧1Number of IslandsMediumBFS / DFS 网格遍历2Partition LabelsMedium贪心 字符最后出现位置3Two SumEasy哈希表4Reorder Data in Log FilesMedium稳定排序 自定义比较器5LRU CacheMedium哈希表 双向链表6Minimum Difficulty of a Job ScheduleHard动态规划划分型7Critical Connections in a NetworkHardTarjan 求桥8Pairs of Songs With Total Durations Divisible by 60Medium余数计数9K Closest Points to OriginMedium堆 / 快速选择10Merge Two Sorted ListsEasy双指针 哑节点可以看到题库刻意混合了 Easy / Medium / Hard一周之内既练数组与哈希基本功也提前预热图论和设计题节奏非常贴近真实 Amazon OA。 10 道题逐个击破1️⃣ Number of Islands —— 网格连通块计数给定由 1陆地和 0水组成的二维网格计算岛屿数量上下左右相连的陆地算一座岛。核心思路遍历网格踩到陆地就用 DFS 或 BFS 把整座岛淹掉岛屿计数 1。复杂度时间 O(m×n)空间最坏 O(m×n)。 提示这是所有二维网格题的入门模板建议背熟再进下一题Amazon 的网格题十有八九是它的变体。2️⃣ Partition Labels —— 贪心最大化分块数把字符串拆成尽可能多的片段使每个字符最多只出现在一个片段里返回各片段长度。核心思路先遍历一遍记录每个字符的最后出现位置再从左到右走把当前片段右端不断扩展到片段内字符最远的最后位置。复杂度时间 O(n)空间 O(1)最多 26 个字母。 提示本质是贪心滑动窗口别急着剪断片段——只要还有字符还没走完片段就必须继续拉长。3️⃣ Two Sum —— 哈希表最经典热身给定数组和目标值返回和为目标值的两个数的下标。核心思路一边扫描一边把数值 → 下标存入哈希表每来一个数先查它的补数target − 当前值在不在表里。复杂度时间 O(n)空间 O(n)。 提示这是 Amazon OA 的守门题务必做到一次无 bug 通过它还是后面好几道题比如余数配对题的前置技能。4️⃣ Reorder Data in Log Files —— 稳定排序实战日志分两类字母日志按内容字母序排数字日志保持原始相对顺序且数字日志整体排在字母日志之后。核心思路把日志分成两组分别处理字母日志用自定义比较器排序数字日志不动靠稳定排序保住原始顺序。复杂度时间 O(n log n)。 提示面试时要能主动解释为什么必须稳定排序这是 Amazon 面试官非常爱追问的点。5️⃣ LRU Cache —— 本周最高频设计题实现一个容量固定的缓存get 和 put 都要 O(1)容量满时淘汰最久未使用的条目。核心思路哈希表存键 → 链表节点实现 O(1) 定位双向链表维护访问先后每次访问把节点移到链头链尾就是最久未用者。复杂度get 与 put 均 O(1)。 提示这是 Amazon 出现率最高的设计题之一哈希表 双向链表这套组合拳背下来操作系统、数据库课程还会再见到它。6️⃣ Minimum Difficulty of a Job Schedule —— 一维划分 DP把连续任务切成 d 天顺序不能变每天难度取当天最大难度求 d 天总难度最小值。核心思路设 dp[i][j] 为前 i 天完成前 j 个任务的最小难度枚举第 i 天从哪个任务开始做到第 j 个来转移。复杂度时间 O(d×n²)。 提示这是划分型 DP的代表题。先在纸上写清楚状态转移方程再动手切忌边想边写。7️⃣ Critical Connections in a Network —— Tarjan 求桥找出网络中所有去掉后会使网络断开的关键连接图论中的桥。核心思路DFS 时维护 disc发现时间与 low能回溯到的最早时间两个数组若树边 u→v 满足 low[v] disc[u]这条边就是桥。复杂度时间 O(V E)。 提示本周最难的进阶题。DFS 模板抄一遍后建议在纸上画出递归树理解 low 到底在统计什么。8️⃣ Pairs of Songs With Total Durations Divisible by 60 —— 余数配对统计两两时长之和能被 60 整除的歌曲对数。核心思路每首歌时长对 60 取余得 r只往前找余数为 (60 − r) % 60 的歌曲用一个长度为 60 的数组累加即可。复杂度时间 O(n)空间 O(60)。 提示千万别写双重循环O(n²) 会超时。关键洞察是两数之和能被 60 整除 ⟺ 两个余数凑成 60。9️⃣ K Closest Points to Origin —— 求距离最近 K 个点给定平面上的一组点返回离原点 (0, 0) 最近的 k 个点。核心思路维护大小为 k 的最大堆逐个淘汰或用快速选择平均 O(n) 直接定位第 k 近的点。复杂度堆 O(n log k)快速选择平均 O(n)。 提示两种方案都要能当场写出来Amazon 面试官最爱追问能不能再快一点。 Merge Two Sorted Lists —— 链表第一题将两条升序链表合并为一条新的升序链表。核心思路哑节点dummy node打底双指针分别指向两条链表谁小就接谁最后把剩余尾巴直接接上。复杂度时间 O(m n)空间 O(1)。 提示哑节点技巧是链表题的万能起手式本周吃透它下周的 Merge k Sorted Lists 就不会被边界条件卡住。️ 推荐 7 天刷题节奏天数主题题目Day 1哈希基本功Two Sum、Pairs of SongsDay 2链表热身Merge Two Sorted ListsDay 3网格入门Number of IslandsDay 4贪心与滑动窗口Partition LabelsDay 5设计题专项LRU CacheDay 6排序与选择Reorder Data in Log Files、K Closest PointsDay 7进阶挑战Minimum Difficulty、Critical Connections⏰ 小技巧单题限时 45 分钟超时就先看题解看完合上再独立重做一遍——只看不练等于白刷。 新手避坑三件必须坚持的事用题库里的表格记录进度在CrackAmazonResource.md的 Status 列维护 Done ✅ / In Progress 每周回看一次这是防止刷完就忘最有效的方式。先写思路再写代码每题先在纸上用两三句话描述我打算怎么做再动手编码正好对应 Amazon 白板面试的表达要求。别停在第 1 周题库共 5 周 50 题。第 1 周完成后第 2 周还有 Top K Frequent Words、Trapping Rain Water 等题目等着你坚持刷完就能覆盖 Amazon 面试的高频考点网络。搞定这 10 道题如果能在限时内稳定做出 8 道你就可以放心开启第 2 周了【免费下载链接】AmazonCrackedResourceA List of frequently asked questions in Amazons Online Assessment and Interviews项目地址: https://gitcode.com/gh_mirrors/am/AmazonCrackedResource创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 AmazonCrackedResource第1周刷题解析：从Two Sum到LRU Cache，10道基础题逐个击破
AmazonCrackedResource第1周刷题解析从Two Sum到LRU Cache10道基础题逐个击破【免费下载链接】AmazonCrackedResourceA List of frequently asked questions in Amazons Online Assessment and Interviews项目地址: https://gitcode.com/gh_mirrors/am/AmazonCrackedResource正在备战 Amazon 面试的同学OA 刷题是第一道坎。本文基于开源题库项目 AmazonCrackedResource把第 1 周的 10 道高频题逐个击破——从最经典的 Two Sum 到设计题 LRU Cache覆盖每道题的核心思路、复杂度与避坑点帮你从零建立完整的刷题节奏。 AmazonCrackedResource 是什么AmazonCrackedResource 是一个专为Amazon OAOnline Assessment和现场面试整理的算法题库把高频题按5 周学习计划、每周 10 题、共 50 题组织成完整的刷题路线。它的特点✅ 难度从 Easy 到 Hard 分级标注适合循序渐进✅ 自带进度跟踪表Done ✅ / In Progress / Skipped ❌做完一题打个勾✅ MIT 开源协议免费使用、可自由 Fork核心题库在CrackAmazonResource.md文件里项目介绍见README.md协议文件为LICENSE。 获取完整题库一条命令克隆到本地git clone https://gitcode.com/gh_mirrors/am/AmazonCrackedResource打开CrackAmazonResource.md找到 Problems for Week 1 小节本周要练的 10 道题一目了然。 第 1 周 10 道题速览#题目难度核心技巧1Number of IslandsMediumBFS / DFS 网格遍历2Partition LabelsMedium贪心 字符最后出现位置3Two SumEasy哈希表4Reorder Data in Log FilesMedium稳定排序 自定义比较器5LRU CacheMedium哈希表 双向链表6Minimum Difficulty of a Job ScheduleHard动态规划划分型7Critical Connections in a NetworkHardTarjan 求桥8Pairs of Songs With Total Durations Divisible by 60Medium余数计数9K Closest Points to OriginMedium堆 / 快速选择10Merge Two Sorted ListsEasy双指针 哑节点可以看到题库刻意混合了 Easy / Medium / Hard一周之内既练数组与哈希基本功也提前预热图论和设计题节奏非常贴近真实 Amazon OA。 10 道题逐个击破1️⃣ Number of Islands —— 网格连通块计数给定由 1陆地和 0水组成的二维网格计算岛屿数量上下左右相连的陆地算一座岛。核心思路遍历网格踩到陆地就用 DFS 或 BFS 把整座岛淹掉岛屿计数 1。复杂度时间 O(m×n)空间最坏 O(m×n)。 提示这是所有二维网格题的入门模板建议背熟再进下一题Amazon 的网格题十有八九是它的变体。2️⃣ Partition Labels —— 贪心最大化分块数把字符串拆成尽可能多的片段使每个字符最多只出现在一个片段里返回各片段长度。核心思路先遍历一遍记录每个字符的最后出现位置再从左到右走把当前片段右端不断扩展到片段内字符最远的最后位置。复杂度时间 O(n)空间 O(1)最多 26 个字母。 提示本质是贪心滑动窗口别急着剪断片段——只要还有字符还没走完片段就必须继续拉长。3️⃣ Two Sum —— 哈希表最经典热身给定数组和目标值返回和为目标值的两个数的下标。核心思路一边扫描一边把数值 → 下标存入哈希表每来一个数先查它的补数target − 当前值在不在表里。复杂度时间 O(n)空间 O(n)。 提示这是 Amazon OA 的守门题务必做到一次无 bug 通过它还是后面好几道题比如余数配对题的前置技能。4️⃣ Reorder Data in Log Files —— 稳定排序实战日志分两类字母日志按内容字母序排数字日志保持原始相对顺序且数字日志整体排在字母日志之后。核心思路把日志分成两组分别处理字母日志用自定义比较器排序数字日志不动靠稳定排序保住原始顺序。复杂度时间 O(n log n)。 提示面试时要能主动解释为什么必须稳定排序这是 Amazon 面试官非常爱追问的点。5️⃣ LRU Cache —— 本周最高频设计题实现一个容量固定的缓存get 和 put 都要 O(1)容量满时淘汰最久未使用的条目。核心思路哈希表存键 → 链表节点实现 O(1) 定位双向链表维护访问先后每次访问把节点移到链头链尾就是最久未用者。复杂度get 与 put 均 O(1)。 提示这是 Amazon 出现率最高的设计题之一哈希表 双向链表这套组合拳背下来操作系统、数据库课程还会再见到它。6️⃣ Minimum Difficulty of a Job Schedule —— 一维划分 DP把连续任务切成 d 天顺序不能变每天难度取当天最大难度求 d 天总难度最小值。核心思路设 dp[i][j] 为前 i 天完成前 j 个任务的最小难度枚举第 i 天从哪个任务开始做到第 j 个来转移。复杂度时间 O(d×n²)。 提示这是划分型 DP的代表题。先在纸上写清楚状态转移方程再动手切忌边想边写。7️⃣ Critical Connections in a Network —— Tarjan 求桥找出网络中所有去掉后会使网络断开的关键连接图论中的桥。核心思路DFS 时维护 disc发现时间与 low能回溯到的最早时间两个数组若树边 u→v 满足 low[v] disc[u]这条边就是桥。复杂度时间 O(V E)。 提示本周最难的进阶题。DFS 模板抄一遍后建议在纸上画出递归树理解 low 到底在统计什么。8️⃣ Pairs of Songs With Total Durations Divisible by 60 —— 余数配对统计两两时长之和能被 60 整除的歌曲对数。核心思路每首歌时长对 60 取余得 r只往前找余数为 (60 − r) % 60 的歌曲用一个长度为 60 的数组累加即可。复杂度时间 O(n)空间 O(60)。 提示千万别写双重循环O(n²) 会超时。关键洞察是两数之和能被 60 整除 ⟺ 两个余数凑成 60。9️⃣ K Closest Points to Origin —— 求距离最近 K 个点给定平面上的一组点返回离原点 (0, 0) 最近的 k 个点。核心思路维护大小为 k 的最大堆逐个淘汰或用快速选择平均 O(n) 直接定位第 k 近的点。复杂度堆 O(n log k)快速选择平均 O(n)。 提示两种方案都要能当场写出来Amazon 面试官最爱追问能不能再快一点。 Merge Two Sorted Lists —— 链表第一题将两条升序链表合并为一条新的升序链表。核心思路哑节点dummy node打底双指针分别指向两条链表谁小就接谁最后把剩余尾巴直接接上。复杂度时间 O(m n)空间 O(1)。 提示哑节点技巧是链表题的万能起手式本周吃透它下周的 Merge k Sorted Lists 就不会被边界条件卡住。️ 推荐 7 天刷题节奏天数主题题目Day 1哈希基本功Two Sum、Pairs of SongsDay 2链表热身Merge Two Sorted ListsDay 3网格入门Number of IslandsDay 4贪心与滑动窗口Partition LabelsDay 5设计题专项LRU CacheDay 6排序与选择Reorder Data in Log Files、K Closest PointsDay 7进阶挑战Minimum Difficulty、Critical Connections⏰ 小技巧单题限时 45 分钟超时就先看题解看完合上再独立重做一遍——只看不练等于白刷。 新手避坑三件必须坚持的事用题库里的表格记录进度在CrackAmazonResource.md的 Status 列维护 Done ✅ / In Progress 每周回看一次这是防止刷完就忘最有效的方式。先写思路再写代码每题先在纸上用两三句话描述我打算怎么做再动手编码正好对应 Amazon 白板面试的表达要求。别停在第 1 周题库共 5 周 50 题。第 1 周完成后第 2 周还有 Top K Frequent Words、Trapping Rain Water 等题目等着你坚持刷完就能覆盖 Amazon 面试的高频考点网络。搞定这 10 道题如果能在限时内稳定做出 8 道你就可以放心开启第 2 周了【免费下载链接】AmazonCrackedResourceA List of frequently asked questions in Amazons Online Assessment and Interviews项目地址: https://gitcode.com/gh_mirrors/am/AmazonCrackedResource创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考