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

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

Answer

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

Answer

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

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

Perform a binary search on each row individually.

Answer

Flatten the matrix into a 1D array and perform a single binary search.

Answer

Iterate through every element in the matrix until the target is found.

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

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

Answer

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

Answer

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

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

Check all 8 neighboring cells (including diagonals) to see if they are also 'L'.

Answer

Immediately increment the island count and move to the next cell in the iteration.

Answer

Add the coordinates of the 'L' to a queue but only increment the island count after the entire grid has been scanned.

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

It is inefficient because it requires iterating through the matrix multiple times.

Answer

It fails to handle matrices that contain only one row or one column.

Answer

It uses too much auxiliary space by creating a copy of the matrix.

Question 6

When implementing a zig-zag diagonal traversal of a matrix (e.g., `1, 2, 4, 7, 5, 3, ...`), what property of a cell's coordinates is typically used to determine the direction of traversal (up-right vs. down-left) for the diagonal it belongs to?

Accepted Answer

The parity (even or odd) of the sum of the row and column indices (`i + j`).

Answer

Whether the current row index `i` is even or odd.

Answer

The value of the element at the current position being even or odd.

Answer

The total number of elements visited so far.