CodeSignal Technical Assessment Matrix Traversal and Logic 4

Question 1

In a matrix DP problem for counting paths from top-left to bottom-right (moving only right or down), the recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1]. What are the base cases?

Accepted Answer

dp[0][j] = 1 for all j and dp[i][0] = 1 for all i

Answer

The entire first row and first column have exactly one path each (only move right or only move down), so they are all initialized to 1.

Question 2

You want to find the shortest path in a weighted grid where each cell has a cost to enter. Which algorithm handles this correctly?

Accepted Answer

Dijkstra's algorithm with a min-heap priority queue

Answer

Dijkstra's algorithm correctly handles non-negative weighted edges and finds the minimum-cost path in a weighted grid.

Question 3

In the 'surrounded regions' problem, you flip all 'O' regions not connected to the border to 'X'. What is the most efficient first step?

Accepted Answer

Mark all 'O' cells reachable from any border cell using BFS/DFS

Answer

Starting BFS/DFS from border 'O' cells and marking them safe in one pass avoids redundant work and is O(M*N).

Question 4

A matrix is called Toeplitz if every diagonal from top-left to bottom-right has the same value. What is the time complexity to verify a Toeplitz matrix of size M×N?

Accepted Answer

O(M*N)

Answer

You must check each cell (except the first row and column) against its top-left neighbor, visiting each cell once: O(M*N).

Question 5

When transposing a non-square M×N matrix in-place is not possible (since the result is N×M), what is a common out-of-place solution's space complexity?

Accepted Answer

O(M*N)

Answer

An out-of-place transpose requires allocating a new N×M matrix to hold all M*N elements, so space is O(M*N).

Codesignal Practice Test

Codesignal Practice Test

CodeSignal Technical Assessment Matrix Traversal and Logic 4