Amazon VO 唯一路径(Unique Paths II)——Amazon 面试实录 – 一亩三分地 – 亚麻面试 – 亚麻面经 – 面试辅助 – 代面试

Amazon 2025年夏天高强度的发面试中,为了提高效率基本都是3场技术面一起来,全程使用chime平台完成,我们一起来看看最近亚马逊出了什么题目吧。以下来自于我们CSOahelp真实客户的面试记录,CSOahelp面试辅助老师全程提供解题思路、Follow up 以及详细完整代码; 不用刷题轻松进大厂。

首先上来一道算法题

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and space is marked as 1 and 0 respectively in the grid.

给你一个 m×n 的整型网格 obstacleGrid,1 表示障碍、0 表示空格。机器人初始在 (0,0),目标是 (m-1,n-1),只能向右或向下移动,问共有多少条唯一路径,不得经过任何障碍格。

题目虽然我没有看懂,但是CSOahelp的面试辅助上已经出现了若干澄清问题,按照之前的演练,我需要先把问题一一和面试官确认,这样我可以为辅助老师争取更多的时间去写代码。

我的ipad上出现了以下3个澄清问题,我依次向面试官进行了询问:

  1. 起点或终点若为障碍,直接返回 0?
  2. 整个网格行数或列数为 0 时,也返回 0?

面试官依次进行了回答:

是的,所有无法到达的情况都返回 0。

随机我的ipad现实出了辅助老师写下的详细思路,我照着念。

        
Algorithm

We can use a matrix traversal algorithm and take advantage of a dynamic programming 
    idea to solve this question

 Create a 2D DP table where dp[i][j] = number of ways to reach cell (i,j)

Base Cases:

dp[0][0] = 1 (one way to start)
If start/end has obstacle → return 0

We can start by filling the boundaries 
First row: can only come from left
First column: can only come from above

Then iteratively we can fill the internal cells 
For each cell (i,j):

If obstacle → dp[i][j] = 0
Otherwise → dp[i][j] = dp[i-1][j] + dp[i][j-1]

finally we can return Return dp[m-1][n-1] (bottom-right corner)

        
    

看完后我告诉面试官:接下来我会用动态规划来求解。首先,定义一个大小同原网格的二维数组 dp,其中 dp[i][j] 表示到达格子 (i,j) 的路径数。初始时把所有元素设为 0,起点 dp[0][0] = 1(前提是 grid[0][0] == 0)。

面试官:第一行和第一列如何初始化?
我:对第一行,仅能从左向右移动,dp[0][j] = grid[0][j] == 1 ? 0 : dp[0][j-1]
第一列仅能从上向下移动,dp[i][0] = grid[i][0] == 1 ? 0 : dp[i-1][0]

面试官:内层格子的状态转移是什么?
我:对于非边界的格子 (i,j),如果 grid[i][j] == 1,则 dp[i][j] = 0;否则 dp[i][j] = dp[i-1][j] + dp[i][j-1]

接下来面试官要求我对示例进行一个walkthrough,正当我惊慌的时候,我看到ipad上及时出现了如下提示。

        
    Step by step walkthrough

    we first create our dp array of size 3*3
    and then we can start the base case and 
    fill dp[0][0] to 1
    then for the first row we fill them as the value of the 
    cell on the left since we can
    only move right, so the first row is filled with 1
    also for the first column we can only move down, 
    so they can also be filled with 1 as
    well
    at this point dp is:
    1 1 1
    1 0 0
    1 0 0

    for that we can do a nested for loop to loop over the internal of the dp 
    so the loop is for i in range 1 to 2, and j in range 1 to 2
    at dp[1][1] since it's a blocker, we set to 0
    at dp[1][2] since it's not a blocker it's equal 
      dp[i-1][j] + dp[i][j-1] which is 1 + 0 = 1
    at dp[2][1] since it's not a blocker it's equal 
      dp[i-1][j] + dp[i][j-1] which is 1 + 0 = 1
    at dp[2][2] since it's not a blocker it's equal 
      dp[i-1][j] + dp[i][j-1] which is 1 + 1 = 2

    so at the end the dp array is
    1 1 1
    1 0 1
    1 1 2

    then we return the dp value at bottom right which is dp[2][2] so we return 2
        
    

我边写边念,向面试官一步步的讲解我的答案和思路。最后的环节,我抄写了老师的代码,因为我习惯使用Java,所以老师给我提供了Java的全套代码。由于Java代码的代码量较多,这个环节反而花费了我大量的时间,应该之前练习一下抄代码的速度。代码略过~

最后的阶段面试官让我有什么问题可以问他,这个时候辅助老师给出了若干个适合问的问题放在了屏幕上,同时提醒我不要超时,随便选择几个就好。最后面试官怎么答的我已经不记得了。

这是连续的三轮Amazon面试,我只分享了其中一道题, 我本来以为还有系统设计,老师帮我准备好了画图的软件,但是最后也没有用上。

另外2轮面试中的题目也有的我自己本来就会做,但是有了老师的提示,我自信心提升了很多,缓解了很多焦虑,我认为花钱请面试辅助也是非常值得的。

收到面试通过的消息之后,我非常感慨,到现在为止其实我还是不太懂这道题问的是什么,但是由于有CSOahelp面试辅助服务,我成功的又向北美大厂迈进了一步。听辅助老师说,前面入职大厂的师兄姐们都混的不错,因为面试真的难度太高了反而入职工作之后工作很简单很容易做,再加上现在有强力AI,其实入职之后的初级岗位真的不难。现在我非常期待在北美开启新的职场生涯。

如果你也在准备Point72、Meta、TikTok等大厂的算法与系统设计面试,却不清楚如何拆题和应对各种边界,欢迎添加微信 csvohelp,即可领取北美面试求职通关秘诀。我们也有代面试,面试辅助,OA代写等服务助您早日上岸~

Leave a Reply

Your email address will not be published. Required fields are marked *