Algorithm Design 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 Algorithm Design flashcards as text
Which algorithmic technique solves the 0/1 Knapsack problem optimally?
Answer: Dynamic programming
Dynamic programming solves 0/1 Knapsack in O(n·W) time by building a table of optimal subproblem solutions.
What is the worst-case time complexity of quicksort?
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).
In Dijkstra's algorithm, which data structure gives the best practical performance?
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.
Which sorting algorithm is stable and has O(n log n) worst-case time?
Answer: Merge sort
Merge sort is stable (preserves relative order of equal elements) and guarantees O(n log n) in all cases.
What does memoization primarily optimize?
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.
Which problem can be solved with the sliding window technique?
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).
What is the purpose of a sentinel value in algorithm design?
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.