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
What is the time complexity of building a max-heap from an unsorted array of n elements?
Answer: O(n)
Bottom-up heap construction runs in O(n) because lower levels do less work, and the sum telescopes to linear time.
Which technique is used in the Kadane's algorithm to find the maximum subarray sum?
Answer: Dynamic programming with a running max
Kadane's keeps a running maximum ending at each index, resetting to 0 when it goes negative, achieving O(n) time.
When does the Floyd-Warshall algorithm apply best?
Answer: All-pairs shortest paths on dense graphs
Floyd-Warshall computes all-pairs shortest paths in O(V³) and is efficient when the graph is dense (E ≈ V²).
What does amortized O(1) mean for a dynamic array's append operation?
Answer: The average cost per append over a sequence of operations is O(1)
Occasional O(n) resizing is spread across n appends, making the amortized cost per operation O(1) on average.
Which traversal order of a BST produces elements in sorted order?
Answer: In-order
In-order traversal (left → root → right) of a BST visits nodes in non-decreasing key order.
What problem does topological sorting solve?
Answer: Ordering tasks with dependencies (DAG)
Topological sort linearly orders vertices of a DAG so that for every edge u→v, u appears before v.
Which recurrence solves to O(n log n) by the Master Theorem?
Answer: T(n) = 2T(n/2) + O(n)
T(n) = 2T(n/2) + O(n) matches Master Theorem Case 2, giving Θ(n log n) — the merge sort recurrence.