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 graph algorithm finds the minimum spanning tree using a greedy edge-addition approach?
Answer: Kruskal's algorithm
Kruskal's algorithm sorts edges by weight and greedily adds the lightest edge that doesn't form a cycle, yielding the MST.
What recurrence does binary search satisfy?
Answer: T(n) = T(n/2) + O(1)
Binary search splits the problem in half each step with constant work, giving T(n) = T(n/2) + O(1) and O(log n) total.
What is the key property that allows greedy algorithms to produce optimal solutions?
Answer: Greedy choice property and optimal substructure
Greedy algorithms work when a locally optimal choice at each step leads to a globally optimal solution (greedy choice property + optimal substructure).
Which algorithm detects a negative-weight cycle in a directed graph?
Answer: Bellman-Ford
Bellman-Ford detects negative cycles by checking if any edge can still be relaxed after V-1 iterations.
What is the average-case time complexity of hash table lookup?
Answer: O(1)
With a good hash function and low load factor, hash table lookup is O(1) average due to direct-address computation.
In the two-pointer technique, both pointers typically start at:
Answer: One at start, one at end (or both at start)
Two pointers are usually placed at opposite ends (converging) or both at the start (sliding) depending on the problem.
Which complexity class describes problems where a solution can be verified in polynomial time but no polynomial-time algorithm is known to find one?
Answer: NP
NP (nondeterministic polynomial) contains decision problems whose solutions are verifiable in polynomial time.