DoorDash 面试经验分享：网格路径规划挑战

Sep 7

DoorDash 面试经验分享：网格路径规划挑战

面试过程

通过网上海投获得了 DoorDash 的面试机会，一周后进行了线上面试。面试官由两位组成，一位中国小姐姐和一位 ABC 小哥，整体氛围轻松友好。面试开始先进行了 5 分钟的自我介绍，包括工作经历、项目经验和技术栈等。

随后进入 45 分钟的 coding 环节。

题目描述：网格中的 Dasher

给定一个 n x n 的数组 grid，grid[i][j] 表示在坐标 (i, j) 的格子中的障碍物数值。每过 1 秒，每个格子中的障碍物数值减 1，减到 0 后不再减少。你扮演一名 Dasher，可以向上下左右四个方向移动，但只能移动到障碍物数值为 0 的格子。

你的起始位置在 (0, 0)，目标是到达右下角 (n-1, n-1)。每次移动，你可以在同一方向上穿过多个格子。

求到达右下角的最短时间。

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n^2
grid[i][j] 的值均不相同

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

面试官要求我按照自己的思路，手动模拟示例的执行过程，详细说明每一步队列中的元素和变量的值。

解决方案：BFS

public int minTimeToDestination(int[][] grid) {
    int n = grid.length;
    int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 优先队列，按照时间（最小时间优先）探索格子
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));

    // 从左上角开始
    pq.offer(new int[]{0, 0, grid[0][0]});

    // 访问数组，防止重复处理格子
    boolean[][] visited = new boolean[n][n];
    visited[0][0] = true;

    // 执行 Dijkstra 式搜索
    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int row = current[0], col = current[1], time = current[2];

        // 如果到达右下角，返回时间
        if (row == n - 1 && col == n - 1) {
            return time;
        }

        // 探索相邻格子（上、下、左、右）
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];

            // 检查新位置是否在边界内
            if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                // 计算新格子可访问的时间
                int newTime = Math.max(time, grid[newRow][newCol]);

                // 将新格子添加到优先队列
                pq.offer(new int[]{newRow, newCol, newTime});
                visited[newRow][newCol] = true;
            }
        }
    }
    // 如果未找到路径，返回 -1
    return -1;
}

Follow Up：只能向下或向右移动

面试官进一步提问：如果 Dasher 只能向下或向右移动，如何求最短时间？

我没有被要求写出代码，但解释了使用动态规划（DP）的思路：

dp[i][j] 表示到达坐标 (i, j) 的最短时间。
初始化：dp[0][0] = grid[0][0]，其他位置初始化为无穷大。
递推：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]（注意边界情况）。
最终答案为 dp[n-1][n-1]。

总结与建议

这次 DoorDash 面试考察了对 BFS 算法的理解和应用能力。手动模拟执行过程的要求比较独特，需要对算法细节有清晰的把握。建议在准备面试时，除了刷题，也要注重算法的原理和实现细节，培养良好的代码风格和沟通能力。

如果您需要更专业的系统设计辅导、编程测试优化或面试模拟服务，欢迎联系我们的团队，我们将竭诚为您提供支持，助您在技术面试中脱颖而出！

Gabby Fox

DoorDash 面试经验分享：网格路径规划挑战