CodeSignal Technical Assessment Algorithm Design 2 — Questions and Answers
Question 1: Which algorithmic technique solves the 0/1 Knapsack problem optimally?
- Greedy algorithm
- Dynamic programming (Correct answer)
- Divide and conquer
- Backtracking only
Correct answer: Dynamic programming
Dynamic programming solves 0/1 Knapsack in O(n·W) time by building a table of optimal subproblem solutions.
Question 2: What is the worst-case time complexity of quicksort?
- O(n log n)
- O(n²) (Correct answer)
- O(n)
- O(log n)
Correct answer: O(n²)
Quicksort degrades to O(n²) when the pivot is always the smallest or largest element (e.g., sorted input with naive pivot).
Question 3: In Dijkstra's algorithm, which data structure gives the best practical performance?
- Stack
- Unsorted array
- Min-heap (priority queue) (Correct answer)
- Max-heap
Correct answer: Min-heap (priority queue)
A min-heap reduces the extract-minimum operation to O(log n), giving overall O((V + E) log V) complexity.
Question 4: Which sorting algorithm is stable and has O(n log n) worst-case time?
- Quicksort
- Heapsort
- Merge sort (Correct answer)
- Shell sort
Correct answer: Merge sort
Merge sort is stable (preserves relative order of equal elements) and guarantees O(n log n) in all cases.
Question 5: What does memoization primarily optimize?
- Space usage by compressing arrays
- Repeated computation of identical subproblems (Correct answer)
- Cache eviction policies
- Sorting order of recursive calls
Correct answer: Repeated computation of identical subproblems
Memoization caches results of subproblems so each unique input is computed only once, converting exponential recursion to polynomial time.
Question 6: Which problem can be solved with the sliding window technique?
- Finding the shortest path in a graph
- Maximum sum subarray of size k (Correct answer)
- Detecting cycles in a linked list
- Checking balanced parentheses
Correct answer: Maximum sum subarray of size k
Sliding window maintains a running sum over a fixed-size window, solving maximum sum of k consecutive elements in O(n).
Question 7: What is the purpose of a sentinel value in algorithm design?
- To mark the end of recursion depth
- To simplify boundary checks by providing a dummy boundary element (Correct answer)
- To store intermediate DP results
- To balance a binary search tree
Correct answer: To simplify boundary checks by providing a dummy boundary element
A sentinel is a special dummy value placed at array boundaries to eliminate edge-case checks inside loops.
CodeSignal Technical Assessment Algorithm Design 2
Which algorithmic technique solves the 0/1 Knapsack problem optimally?