Coupang Software Engineer Interview Experience — Live-Coded LeetCode 934, Debugged a Stack Overflow Myself

Problem
LeetCode 934, Shortest Bridge

When I answered, I first laid out all his examples in a structured way below, then started with the function just returning 0.

Running it gave n zeros, and I told him this was the first iteration. The next step was to finish the function so it returns the correct result.

While working through it, I ran into a case where the recursion wasn't controlled properly and it blew up. I fixed that myself. There was also a case where the result was wrong, and I debugged it myself by printing out info.

Solution
First, DFS to find the two islands, then BFS starting from island 1 to expand into the water.

To find an island with DFS: first use (i, j) to find a point with value 1, then DFS floodfill it to -1, and at the same time put its coordinates into a set called island1.

Then traverse the whole grid and set the remaining points with value 1 to -2. This gives us a grid with values 0, -1, and -2.

Starting the expansion from island1, set step to 0. If a neighbor is water, add it to next_expansion. If a neighbor is island 2, we get the result immediately and return step.