Doordash 店面挂经

刀大师挂经。

网上海投，hr联系，约了一周后店面。

面试官是个国人小姐姐 + abc小哥，都还是和颜悦色的。上来5分钟先做了自我介绍，自己在哪个组，做了什么项目，用的什么技术。

后面45分钟做题。题目 + 答案如下：

给一个 nxn的数组 grid，grid[i][j] 代表在(i, j) cell里面的obestacles。每隔1秒，每个cell里面的obstacle数值减一，减到0以后不会再减。 假设你是一个dasher，可以往上下左右四个方向移动，但只能去到obstacle = 0 的cells。
你的起始位置在 (0, 0)，需要到达右下角(n-1, n-1). 每次移动，你可以在同一方向走过多个cells。
求到达右下角的最短时间。

Constraints: * n == grid.length * n == grid[i].length * 1 <= n <= 50 * 0 <= grid[i][j] < n^2 * Each value grid[i][j] is unique.
Example

Input:
grid = [[0,1,2,3,4],[24,16,22,21,5],[12,13,14,15,23],[11,17,18,19,20],[10,9,8,7,6]] Output:16.

lz给出了一个solution，结果面试官让lz按着这个solution logic，照着example 一步一步手动iterate，每一步queue里有什么，每个variable的值是多少。。
手动iterate到最后，才跟我说 好了可以 写代码吧。。
（这一步真的有点累哈哈哈）
写完代码以后，面试官自己有几个test cases，跑了一下全都pass。

lz的答案：用bfs：
public int minTimeToDestination(int[][] grid) {
        int n = grid.length;
        int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Priority queue to explore cells, sorting by time (minimum time first)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
        
        // Start from the top-left corner
        pq.offer(new int[]{0, 0, grid[0][0]});
        
        // Visited array to prevent re-processing of cells
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        
        // Perform Dijkstra-like search
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int row = current[0], col = current[1], time = current[2];
            
            // If we've reached the bottom-right corner, return the time
            if (row == n - 1 && col == n - 1) {
                return time;
            }
            
        

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

olor="#008080">        return -1;
}


follow up：如果dasher只能向下或者向右移动，求最短时间。
这一步没有要求lz写出来，用dp就可以做。
然后lz说了一下 如何构建dp array，dp[i][j] 代表什么，initialization怎么做，induction step怎么做。
面试官听完说，对 就是这样。


全程聊的挺开心的。第二天一大清早收到拒信


可能是lz在手动iterate的过程中表现的有点不耐烦，希望大家引以为戒，面试的时候不要不耐烦，全程尽量散发正能量，表现出自己enjoy challenge，具有很强的抗压能力，争取做一个正能量小天使。哈哈哈

看着像是利口 气气吧 反过来？觉得有用麻烦➕大米

请问这个题有对应的lc吗？谢谢lz

desperado721 发表于 2024-09-10 20:40:52
请问这个题有对应的lc吗？谢谢lz

我没找到对应的题

请问下  是在同一个时间只能在一个方向上连续移动吗？每次移动可以变换方向吗？
如果不可以的话，那么按照给出的input，output应该是16+3才对，在16秒的时候只能到达input中16或者13（走到底），接下来还要再走3次才可以到达终点