CodeSignal Technical Assessment Algorithm Design 3 — Questions and Answers
Question 1: Which graph algorithm finds the minimum spanning tree using a greedy edge-addition approach?
- Dijkstra's algorithm
- Bellman-Ford
- Kruskal's algorithm (Correct answer)
- Floyd-Warshall
Correct 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.
Question 2: What recurrence does binary search satisfy?
- T(n) = 2T(n/2) + O(n)
- 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 splits the problem in half each step with constant work, giving T(n) = T(n/2) + O(1) and O(log n) total.
Question 3: What is the key property that allows greedy algorithms to produce optimal solutions?
- Overlapping subproblems
- Greedy choice property and optimal substructure (Correct answer)
- Divide and conquer decomposition
- Memoization of all states
Correct 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).
Question 4: Which algorithm detects a negative-weight cycle in a directed graph?
- Dijkstra's
- Prim's
- Bellman-Ford (Correct answer)
- BFS
Correct answer: Bellman-Ford
Bellman-Ford detects negative cycles by checking if any edge can still be relaxed after V-1 iterations.
Question 5: What is the average-case time complexity of hash table lookup?
- O(log n)
- O(n)
- O(1) (Correct answer)
- O(n log n)
Correct answer: O(1)
With a good hash function and low load factor, hash table lookup is O(1) average due to direct-address computation.
Question 6: In the two-pointer technique, both pointers typically start at:
- Both at the end
- One at start, one at end (or both at start) (Correct answer)
- Both in the middle
- Random positions
Correct 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.
Question 7: Which complexity class describes problems where a solution can be verified in polynomial time but no polynomial-time algorithm is known to find one?
- P
- NP (Correct answer)
- NP-hard
- EXPTIME
Correct answer: NP
NP (nondeterministic polynomial) contains decision problems whose solutions are verifiable in polynomial time.
CodeSignal Technical Assessment Algorithm Design 3
Which graph algorithm finds the minimum spanning tree using a greedy edge-addition approach?