Matrix Traversal and Logic Flashcards
7 cards from real CodeSignal Technical Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Matrix Traversal and Logic flashcards as text
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?
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.
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?
Answer: 16
The outermost ring of a 5×5 matrix has 4*(5-1) = 16 elements.
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?
Answer: Reverse each column, then transpose
Counter-clockwise 90° rotation is achieved by reversing each column (flipping vertically) then transposing.
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?
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.
When performing BFS on a matrix to find the shortest path, what data structure should store the cells to visit next?
Answer: Queue (FIFO)
BFS uses a FIFO queue to explore neighbors level by level, guaranteeing shortest path in an unweighted grid.
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?
Answer: O(M*N)
Each cell is visited at most once during the DFS traversal, giving O(M*N) overall time complexity.
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?
Answer: 11
Row-major index = r * num_cols + c = 2 * 4 + 3 = 11.