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

Dijkstra's algorithm

Answer

Bellman-Ford

Answer

Floyd-Warshall

Question 2

What recurrence does binary search satisfy?

Accepted Answer

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

Answer

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

Answer

T(n) = T(n-1) + O(1)

Answer

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

Question 3

What is the key property that allows greedy algorithms to produce optimal solutions?

Accepted Answer

Greedy choice property and optimal substructure

Answer

Overlapping subproblems

Answer

Divide and conquer decomposition

Answer

Memoization of all states

Question 4

Which algorithm detects a negative-weight cycle in a directed graph?

Accepted Answer

Bellman-Ford

Answer

Dijkstra's

Answer

Prim's

Answer

BFS

Question 5

What is the average-case time complexity of hash table lookup?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n log n)

Question 6

In the two-pointer technique, both pointers typically start at:

Accepted Answer

One at start, one at end (or both at start)

Answer

Both at the end

Answer

Both in the middle

Answer

Random positions

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?

Accepted Answer

NP

Answer

P

Answer

NP-hard

Answer

EXPTIME