CodeSignal Technical Assessment Matrix Traversal and Logic 2 — Questions and Answers
Question 1: Given a matrix where each cell contains a non-negative integer, you want to find the path from top-left to bottom-right (moving only right or down) that minimizes the maximum value encountered. Which algorithm is most appropriate?
- Binary search combined with BFS/DFS (Correct answer)
- Dijkstra's algorithm with a min-heap
- Standard dynamic programming (sum minimization)
- Depth-first search with memoization
Correct answer: Binary search combined with BFS/DFS
Binary search on the answer combined with BFS/DFS to check feasibility efficiently solves the minimax path problem.
Question 2: In a spiral traversal of an N×N matrix, after completing one full ring (outermost layer), the next ring starts at position [1][1]. For a 5×5 matrix, how many elements are in the outermost ring?
- 16 (Correct answer)
- 12
- 20
- 24
Correct answer: 16
The outermost ring of a 5×5 matrix has 4*(5-1) = 16 elements.
Question 3: You rotate a matrix 90 degrees clockwise by first transposing it, then reversing each row. What is the equivalent operation for a 90-degree counter-clockwise rotation?
- Transpose, then reverse each column
- Reverse each row, then transpose
- Reverse each column, then transpose (Correct answer)
- Transpose, then reverse each row
Correct answer: Reverse each column, then transpose
Counter-clockwise 90° rotation is achieved by reversing each column (flipping vertically) then transposing.
Question 4: A matrix is considered 'valid' if each row and each column contains all integers from 1 to N exactly once. What is this structure called?
- Latin square (Correct answer)
- Magic square
- Sudoku grid
- Permutation matrix
Correct answer: Latin square
A Latin square is an N×N array filled with N different symbols, each occurring exactly once in each row and column.
Question 5: When performing BFS on a matrix to find the shortest path, what data structure should store the cells to visit next?
- Queue (FIFO) (Correct answer)
- Stack (LIFO)
- Min-heap (priority queue)
- Deque with elements appended to both ends
Correct answer: Queue (FIFO)
BFS uses a FIFO queue to explore neighbors level by level, guaranteeing shortest path in an unweighted grid.
Question 6: Given an M×N matrix, you need to find the number of distinct islands (connected groups of 1s, where connectivity is 4-directional). You run DFS and mark visited cells. What is the time complexity?
- O(M*N) (Correct answer)
- O(M*N*log(M*N))
- O((M*N)^2)
- O(M+N)
Correct answer: O(M*N)
Each cell is visited at most once during the DFS traversal, giving O(M*N) overall time complexity.
Question 7: In a 0-indexed 4×4 matrix, element at row r and column c is stored in row-major order in a 1D array. What is the 1D index of element at row 2, column 3?
- 11 (Correct answer)
- 9
- 10
- 7
Correct answer: 11
Row-major index = r * num_cols + c = 2 * 4 + 3 = 11.
CodeSignal Technical Assessment Matrix Traversal and Logic 2
Given a matrix where each cell contains a non-negative integer, you want to find the path from top-left to bottom-right (moving only right or down) that minimizes the maximum value encountered.
Which algorithm is most appropriate?