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
What is the space complexity of a recursive depth-first search on a graph with V vertices and E edges?
Answer: O(V)
DFS uses O(V) stack space in the worst case (a path graph causes recursion depth V).
Which algorithm design strategy is used in Fast Fourier Transform (FFT)?
Answer: Divide and conquer
FFT recursively splits the DFT into two half-size DFTs, achieving O(n log n) instead of O(n²).
What is the primary advantage of using an adjacency list over an adjacency matrix for sparse graphs?
Answer: Lower space complexity O(V + E) vs O(V²)
An adjacency list uses O(V + E) space, far less than the O(V²) matrix for graphs where E << V².
Which approach does Prim's MST algorithm use to select the next edge?
Answer: Always pick the cheapest edge crossing the cut between visited and unvisited vertices
Prim's grows the MST from a starting vertex by always selecting the minimum-weight edge connecting the visited set to an unvisited vertex.
What does it mean for a problem to exhibit 'optimal substructure'?
Answer: An optimal solution contains optimal solutions to its subproblems
Optimal substructure means the global optimal solution is composed of optimal solutions to smaller subproblems, enabling DP or greedy approaches.
Which data structure supports O(log n) insert, delete, and search while maintaining sorted order?
Answer: Balanced BST (e.g., AVL or Red-Black tree)
A balanced BST maintains O(log n) height, guaranteeing O(log n) for all three operations while keeping elements sorted.
In the context of CodeSignal assessments, what does 'time complexity' primarily measure?
Answer: How runtime scales with input size n as n grows large
Time complexity (Big-O notation) describes the asymptotic growth rate of an algorithm's running time relative to input size.