CodeSignal Technical Assessment Matrix Traversal and Logic 3 — Questions and Answers
Question 1: You are given a matrix of 0s and 1s. You want to find the largest rectangle containing only 1s. Which approach leverages the 'largest rectangle in histogram' problem?
- Process each row as a histogram of heights, apply stack-based largest rectangle algorithm (Correct answer)
- Use DP to track 2D prefix sums then iterate over all pairs
- Run BFS from every cell with value 1
- Sort cells by value and use union-find
Correct answer: Process each row as a histogram of heights, apply stack-based largest rectangle algorithm
Building a running height histogram per row and applying the O(N) stack algorithm gives O(M*N) total time.
Question 2: What does it mean for a matrix traversal algorithm to be 'in-place'?
- It modifies the matrix directly without allocating extra storage proportional to input size (Correct answer)
- It uses a separate copy of the matrix for all operations
- It always runs in O(1) time
- It processes elements in sorted order without extra memory
Correct answer: It modifies the matrix directly without allocating extra storage proportional to input size
An in-place algorithm uses O(1) extra space (excluding output) by modifying the original data structure.
Question 3: In the 'word search' problem, you search for a word in a matrix by moving to adjacent cells (up, down, left, right). Why must you mark cells as visited during DFS and unmark them on backtrack?
- To allow the same cell to be reused in other candidate paths while preventing reuse within the current path (Correct answer)
- To permanently eliminate explored cells from the matrix
- Because the problem requires each cell to be visited exactly once globally
- To reduce the time complexity from exponential to polynomial
Correct answer: To allow the same cell to be reused in other candidate paths while preventing reuse within the current path
Temporary marking prevents using the same cell twice within one path but allows it for entirely different paths explored via backtracking.
Question 4: A 'diagonal' of an M×N matrix where row - col = k contains elements sharing the same value of (row - col). How many distinct diagonals (top-left to bottom-right) exist in a 4×5 matrix?
- 8 (Correct answer)
- 9
- 7
- 20
Correct answer: 8
The value (row - col) ranges from -(N-1) = -4 to (M-1) = 3, giving M+N-1 = 4+5-1 = 8 diagonals.
Question 5: When using Union-Find (Disjoint Set Union) to count connected components in a matrix, what operation determines if two cells are in the same component?
- Find with path compression on both cells and compare roots (Correct answer)
- Check if both cells have the same direct parent
- Merge the sets of both cells unconditionally
- BFS from one cell to check if it reaches the other
Correct answer: Find with path compression on both cells and compare roots
The Find operation (with path compression) returns the root representative of each cell's set; equal roots mean same component.
Question 6: Given a matrix where you can move up, down, left, or right, and you want the minimum number of steps from source to destination, which is guaranteed to give the correct answer?
- BFS from the source cell (Correct answer)
- DFS with a visited set
- Greedy best-first search
- Bidirectional DFS
Correct answer: BFS from the source cell
BFS on an unweighted grid explores cells in order of their distance, guaranteeing the first time the destination is reached is via the shortest path.
Question 7: You need to set all cells in the same row and column as any zero to zero in-place in O(1) extra space. Which technique avoids using O(M+N) extra arrays?
- Use the first row and first column of the matrix itself as markers (Correct answer)
- Allocate a separate boolean matrix
- Sort all zeros first then expand
- Use bitmasking with 64-bit integers
Correct answer: Use the first row and first column of the matrix itself as markers
By using the first row and first column as flag arrays (with separate variables for their own zero status), the algorithm runs in O(1) extra space.
CodeSignal Technical Assessment Matrix Traversal and Logic 3
You are given a matrix of 0s and 1s.
You want to find the largest rectangle containing only 1s.
Which approach leverages the 'largest rectangle in histogram' problem?