Adobe·Machine Learning Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Adobe ML engineer interview with a graph/BFS problem. Pretty standard coding round, nothing too wild, but the problem has a few gotchas if you're not careful about how you initialize the BFS.

Questions Asked (1)

Given a binary matrix of M rows and N columns, compute the shortest distance from each cell to the nearest cell containing 0. Return the result as a new matrix of the same dimensions.

Algorithms & Data Structures

Author's notes

Multi-source BFS is the right move here.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS starting from all cells containing 0, updating distances level by level. Alternatively, use dynamic programming with two passes (top-left to bottom-right and vice versa) to compute distances efficiently. Discuss trade-offs between BFS (O(MN) time, O(MN) space) and DP (O(MN) time, O(1) extra space if in-place).

Pro tip: Mention that the DP approach can be done in-place if the input matrix can be modified, but if not, use a separate distance matrix. Also, highlight that BFS naturally handles obstacles (cells with 1) and is intuitive for interviews.

1. Clarify problem and constraints

Confirm the definition of distance (Manhattan distance) and whether the matrix contains only 0s and 1s. Ask about constraints on M and N to choose the optimal algorithm.

2. Choose an approach

Decide between multi-source BFS and two-pass DP. BFS is straightforward and guarantees shortest paths; DP is more space-efficient and can be done in-place.

3. Implement the algorithm

For BFS: initialize a queue with all 0 cells, set their distance to 0, and BFS to neighbors. For DP: initialize distances to infinity, then do two passes updating based on neighbors.

4. Analyze complexity and edge cases

Discuss time and space complexity. Handle edge cases: all 0s, all 1s (no 0s), single row/column, and large matrices.

5. Test with examples

Walk through a small example to verify correctness. Consider testing with a 3x3 matrix and a matrix with no zeros.

Key Points to Mention

Multi-source BFS: enqueue all 0 cells initially, then process level by level.
Dynamic programming: two passes (forward and backward) to propagate minimum distances.
Time complexity: O(M*N) for both approaches.
Space complexity: BFS uses O(M*N) for queue and distance matrix; DP can use O(1) extra space if in-place.
Edge cases: no zeros in matrix (return -1 or infinity?), all zeros, single row/column.
Manhattan distance vs. Euclidean: clarify that distance is Manhattan (grid steps).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.