CodeSignal Technical Assessment Algorithm Design 5

Question 1

What is the space complexity of a recursive depth-first search on a graph with V vertices and E edges?

Accepted Answer

O(V)

Answer

DFS uses O(V) stack space in the worst case (a path graph causes recursion depth V).

Question 2

Which algorithm design strategy is used in Fast Fourier Transform (FFT)?

Accepted Answer

Divide and conquer

Answer

FFT recursively splits the DFT into two half-size DFTs, achieving O(n log n) instead of O(n²).

Question 3

What is the primary advantage of using an adjacency list over an adjacency matrix for sparse graphs?

Accepted Answer

Lower space complexity O(V + E) vs O(V²)

Answer

An adjacency list uses O(V + E) space, far less than the O(V²) matrix for graphs where E << V².

Question 4

Which approach does Prim's MST algorithm use to select the next edge?

Accepted Answer

Always pick the cheapest edge crossing the cut between visited and unvisited vertices

Answer

Prim's grows the MST from a starting vertex by always selecting the minimum-weight edge connecting the visited set to an unvisited vertex.

Question 5

What does it mean for a problem to exhibit 'optimal substructure'?

Accepted Answer

An optimal solution contains optimal solutions to its subproblems

Answer

Optimal substructure means the global optimal solution is composed of optimal solutions to smaller subproblems, enabling DP or greedy approaches.

Codesignal Practice Test