CodeSignal Technical Assessment Matrix Traversal and Logic Questions and Answers 1 — 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?
- 1, 2, 3, 8, 9, 4, 7, 6, 5
- 1, 8, 7, 6, 5, 4, 3, 2, 9
- 1, 2, 3, 4, 5, 6, 7, 8, 9 (Correct answer)
- 1, 2, 9, 4, 5, 6, 7, 8, 3
Correct answer: 1, 2, 3, 4, 5, 6, 7, 8, 9
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?
- Perform a binary search on each row individually.
- Flatten the matrix into a 1D array and perform a single binary search.
- Iterate through every element in the matrix until the target is found.
- Start from the top-right corner. If the target is smaller, move left; if larger, move down. (Correct answer)
Correct answer: Start from the top-right corner. If the target is smaller, move left; if larger, move down.
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?
- [[13, 2, 5], [3, 4, 1], [6, 8, 9]] (Correct answer)
- [[9, 8, 6], [1, 4, 3], [5, 2, 13]]
- [[5, 2, 13], [1, 4, 3], [9, 8, 6]]
- [[6, 3, 13], [8, 4, 2], [9, 1, 5]]
Correct answer: [[13, 2, 5], [3, 4, 1], [6, 8, 9]]
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?
- Check all 8 neighboring cells (including diagonals) to see if they are also 'L'.
- 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. (Correct answer)
- Immediately increment the island count and move to the next cell in the iteration.
- Add the coordinates of the 'L' to a queue but only increment the island count after the entire grid has been scanned.
Correct 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.
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?
- It is inefficient because it requires iterating through the matrix multiple times.
- It fails to handle matrices that contain only one row or one column.
- The zeros that are newly set as part of the process can cause additional, incorrect rows and columns to be zeroed out. (Correct answer)
- It uses too much auxiliary space by creating a copy of the matrix.
Correct answer: The zeros that are newly set as part of the process can cause additional, incorrect rows and columns to be zeroed out.
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.
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?
- Whether the current row index `i` is even or odd.
- The parity (even or odd) of the sum of the row and column indices (`i + j`). (Correct answer)
- The value of the element at the current position being even or odd.
- The total number of elements visited so far.
Correct answer: The parity (even or odd) of the sum of the row and column indices (`i + j`).
In a zig-zag diagonal traversal, all elements on the same diagonal share the same sum of their indices (`i + j`). The direction of traversal for a given diagonal is constant. This direction can be determined by the parity of this sum. For example, all diagonals where `i + j` is even might be traversed up-right, while those where `i + j` is odd are traversed down-left.
CodeSignal Technical Assessment Matrix Traversal and Logic Questions and Answers 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?