CodeSignal Technical Assessment Coding Challenges and Practice 3 ā Questions and Answers
Question 1: A CodeSignal problem gives you a matrix and asks for the number of islands (connected groups of 1s). Which algorithm is best suited?
- Dijkstra's shortest path
- BFS or DFS flood-fill from each unvisited land cell (Correct answer)
- Binary search on the matrix rows
- Topological sort
Correct answer: BFS or DFS flood-fill from each unvisited land cell
BFS or DFS starting from each unvisited '1' marks its entire island as visited, counting one island per launch.
Question 2: You are given an integer array and must return the length of the longest increasing subsequence (LIS). What is the time complexity of the optimal patience-sorting solution?
- O(nĀ²)
- O(n log n) (Correct answer)
- O(n)
- O(2āæ)
Correct answer: O(n log n)
Binary search on a maintained 'piles' array processes each element in O(log n), giving O(n log n) total.
Question 3: In a CodeSignal challenge, you must validate a set of parentheses including '(', ')', '{', '}', '[', ']'. Which structure is essential?
- Queue (FIFO)
- Stack (LIFO) (Correct answer)
- Deque
- Heap
Correct answer: Stack (LIFO)
A stack's last-in-first-out behavior matches the requirement that the most recently opened bracket must be the next one closed.
Question 4: What does the space complexity O(1) mean in the context of an in-place sorting algorithm?
- The algorithm runs in constant time regardless of input size
- The algorithm uses a fixed amount of additional memory beyond the input (Correct answer)
- The algorithm sorts only one element per pass
- The algorithm requires no comparisons
Correct answer: The algorithm uses a fixed amount of additional memory beyond the input
O(1) space means the algorithm's extra memory usage does not grow with the input size.
Question 5: A CodeSignal task requires implementing a min-heap. After inserting a new element, what operation restores the heap property?
- Sift-down from the root
- Sift-up from the newly inserted position (Correct answer)
- Rebuild the entire heap
- Swap root with the last element
Correct answer: Sift-up from the newly inserted position
Sift-up compares the new element with its parent and swaps upward until the heap property is restored.
Question 6: Which recurrence relation correctly describes the time complexity of binary search?
- T(n) = 2T(n/2) + O(1)
- T(n) = T(n/2) + O(1) (Correct answer)
- T(n) = T(n-1) + O(1)
- T(n) = 2T(n-1) + O(1)
Correct answer: T(n) = T(n/2) + O(1)
Binary search discards half the input each step and does constant work, giving T(n) = T(n/2) + O(1), which solves to O(log n).
Question 7: In a CodeSignal coding challenge, memoization is used to optimize a recursive function. What does memoization store?
- All recursive call stacks for debugging
- Previously computed results keyed by their input parameters (Correct answer)
- The base cases of the recursion
- Random samples of the input for approximation
Correct answer: Previously computed results keyed by their input parameters
Memoization caches the output for each unique set of inputs so repeated calls return instantly without recomputation.
CodeSignal Technical Assessment Coding Challenges and Practice 3
A CodeSignal problem gives you a matrix and asks for the number of islands (connected groups of 1s).
Which algorithm is best suited?