CodeSignal Technical Assessment Matrix Traversal and Logic Questions and Answers

Question 1

A developer is implementing a spiral traversal algorithm for a 2D matrix, starting from the top-left corner and moving clockwise. Given the matrix `[[1, 2, 3], [8, 9, 4], [7, 6, 5]]`, what is the correct sequence of visited elements?

Accepted Answer

1, 2, 3, 4, 5, 6, 7, 8, 9

Answer

The traversal starts at the top-left (1), moves right (2, 3), then down (4, 5), then left (6, 7), then up (8), and finally inwards to the center (9). This path traces the numbers in ascending order in this specific matrix, resulting in the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9.

Question 2

You are tasked with finding a target value in an `M x N` matrix where each row is sorted from left to right, and each column is sorted from top to bottom. Which of the following strategies offers the best worst-case time complexity?

Accepted Answer

Start from the top-right corner. If the target is smaller, move left; if larger, move down.

Answer

The strategy of starting at the top-right (or bottom-left) corner allows you to eliminate one row or one column at each step. This reduces the search space linearly, leading to a time complexity of O(M + N), which is more efficient than O(M log N) or O(M * N) in the worst case.

Question 3

A programmer is writing a function to rotate an `N x N` matrix 90 degrees clockwise in-place. If the input matrix is `[[5, 1, 9], [2, 4, 8], [13, 3, 6]]`, what should the matrix look like after the rotation?

Accepted Answer

[[13, 2, 5], [3, 4, 1], [6, 8, 9]]

Answer

A 90-degree clockwise rotation can be achieved by first transposing the matrix (swapping matrix[i][j] with matrix[j][i]) and then reversing each row. Transposing the input gives `[[5, 2, 13], [1, 4, 3], [9, 8, 6]]`. Reversing each row of the transposed matrix results in `[[13, 2, 5], [3, 4, 1], [6, 8, 9]]`.

Question 4

In a 2D grid representing a map of land ('L') and water ('W'), an island is a group of adjacent 'L's (horizontally or vertically). To count the number of distinct islands, a common algorithm iterates through each cell. What is the crucial next step when the iteration encounters an 'L' that has not been visited yet?

Accepted Answer

Increment the island count, then perform a traversal (like DFS or BFS) starting from that cell to find and mark all parts of the same island as visited.

Answer

When an unvisited land cell is found, it signifies the discovery of a new, distinct island. The island count must be incremented. Then, a graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) must be launched from that cell to explore and mark all connected land cells belonging to that same island. This marking prevents recounting parts of the same island later in the iteration.

Question 5

You are given an `M x N` matrix. If an element is 0, its entire row and column must be set to 0. Why is a naive approach of immediately setting rows and columns to zero upon finding a 0 logically flawed?

Accepted Answer

The zeros that are newly set as part of the process can cause additional, incorrect rows and columns to be zeroed out.

Answer

If you find a 0 at `matrix[i][j]` and immediately set row `i` and column `j` to zero, you introduce new zeros. When the algorithm's iteration later encounters one of these newly created zeros, it will incorrectly zero out that cell's entire row and column, which was not part of the original problem's requirement. The correct approach requires first marking which rows/columns need to be zeroed (e.g., using the first row/column or separate arrays) and then performing the zeroing in a second pass.

Codesignal Practice Test

Codesignal Practice Test

CodeSignal Technical Assessment Matrix Traversal and Logic Questions and Answers