Unthinkable Interview Experience

Problems in Round: 1

Problem: Shortest Path in a Binary Matrix

Given a binary matrix of size N × M, where each element is either 0 or 1, and a source and destination cell, find the length of the shortest path from the source to the destination using only valid cells. If no path exists, return -1.

The problem statement specifies 0-based coordinates, movement in four directions (Up, Down, Left, Right), and that the path length is the number of 1s on the path. The source cell is always filled with 1.

Constraints

• 1 ≤ N ≤ 500

• 1 ≤ M ≤ 500

• Matrix values are 0 or 1

• Source coordinates and destination coordinates are within the matrix

• MAT[sourceX][sourceY] = 1

• Time Limit: 1 second

Sample Input 1

3 3 0 1 0 0 0 1 1 1 1 2 0 1 2

Sample Output: 4

The shortest path is (2,0) → (2,1) → (2,2) → (1,2), giving a path length of 4.

Sample Input 2

4 4 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 3 2

Sample Output: -1

Step 1: I first understood the problem and identified that it is a shortest path problem in a grid where movement is allowed in eight directions.

Step 2: I initially considered using DFS but realized it would not guarantee the shortest path and could be inefficient.

Step 3: I then switched to using Breadth-First Search (BFS), since BFS is ideal for finding the shortest path in an unweighted grid.

Step 4: I used a queue to traverse the grid level by level, marking visited cells to avoid revisiting and maintaining the current path length.

Step 5: For each cell, I explored all eight possible directions and added valid cells (within bounds and with value = 0) to the queue.

Step 6: When I reached the bottom-right cell, I returned the current path length as the answer.

Step 7: Finally, I handled edge cases such as when the starting or ending cell is blocked, returning -1 in those cases.

Important Note from the Source

The candidate's recorded approach mentions movement in eight directions and cells with value 0, while the problem statement itself specifies four directions and paths consisting of 1s. This document preserves the source content rather than silently correcting or reconciling that discrepancy.

Problem Metadata

Problem Type: CODE

Average Solve Time: 37 minutes

Success Rate: 65%

Maximum Score: 80

Practice Topics: Matrices (2D Arrays), Backtracking, Breadth-first Search

Test Cases: 5

Default Language: js

Why the Candidate Was Rejected

The candidate was unable to clear the coding round, mainly because of time constraints and difficulty fully optimizing the approach for the given problems.

Although the candidate understood the logic, implementing efficient solutions within the limited time was challenging. The experience highlighted the importance of solving more problems under timed conditions and improving optimization skills.

Key Takeaways

Build strong DSA fundamentals before coding interviews.

Understand problem-solving patterns instead of relying only on question-by-question practice.

Practice coding problems under realistic time constraints.

Focus on optimization and implementation speed, not just identifying the correct logic.

Build and explain projects clearly to strengthen technical fundamentals and interview confidence.

Keep the resume concise and emphasize relevant contributions and achievements.