CodeSignal Technical Assessment Algorithm Design 3

Question 1

Which graph algorithm finds the minimum spanning tree using a greedy edge-addition approach?

Accepted Answer

Kruskal's algorithm

Answer

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?

Accepted Answer

T(n) = T(n/2) + O(1)

Answer

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?

Accepted Answer

Greedy choice property and optimal substructure

Answer

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?

Accepted Answer

Bellman-Ford

Answer

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?

Accepted Answer

O(1)

Answer

With a good hash function and low load factor, hash table lookup is O(1) average due to direct-address computation.

Codesignal Practice Test

Codesignal Practice Test

CodeSignal Technical Assessment Algorithm Design 3