CodeSignal Technical Assessment Matrix Traversal and Logic 2

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?

Accepted Answer

Binary search combined with BFS/DFS

Answer

Dijkstra's algorithm with a min-heap

Answer

Standard dynamic programming (sum minimization)

Answer

Depth-first search with memoization

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?

Accepted Answer

16

Answer

12

Answer

20

Answer

24

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?

Accepted Answer

Reverse each column, then transpose

Answer

Transpose, then reverse each column

Answer

Reverse each row, then transpose

Answer

Transpose, then reverse each row

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?

Accepted Answer

Latin square

Answer

Magic square

Answer

Sudoku grid

Answer

Permutation matrix

Question 5

When performing BFS on a matrix to find the shortest path, what data structure should store the cells to visit next?

Accepted Answer

Queue (FIFO)

Answer

Stack (LIFO)

Answer

Min-heap (priority queue)

Answer

Deque with elements appended to both ends

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?

Accepted Answer

O(M*N)

Answer

O(M*N*log(M*N))

Answer

O((M*N)^2)

Answer

O(M+N)

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?

Accepted Answer

11

Answer

9

Answer

10

Answer

7