Graph and Tree Algorithms 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 Graph and Tree Algorithms flashcards as text
Which tree rotation is performed in an AVL tree when a left-right imbalance is detected?
Answer: Left rotation followed by right rotation
A left-right case is fixed by first rotating the left child left, then rotating the unbalanced root right.
In Prim's algorithm, which data structure gives the best practical runtime for dense graphs?
Answer: Simple array / linear scan
For dense graphs (E ≈ V^2), a simple array gives O(V^2), which beats the O(E log V) binary heap approach.
What is the height of a Red-Black Tree containing N nodes in the worst case?
Answer: O(2 log N)
A Red-Black Tree guarantees height at most 2 log(N+1), ensuring O(log N) search, insert, and delete.
Given a DAG, Kahn's algorithm for topological sort initializes a queue with nodes that have:
Answer: In-degree 0
Kahn's starts with all nodes having in-degree 0 (no dependencies), then repeatedly removes them and decrements neighbors' in-degrees.
The Lowest Common Ancestor of two nodes u and v in a rooted tree can also be found by reducing it to a Range Minimum Query (RMQ) problem. What is the preprocessing time for this approach?
Answer: O(N log N)
Euler tour + sparse table preprocessing for RMQ takes O(N log N) time and enables O(1) LCA queries thereafter.
In an undirected graph, an articulation point (cut vertex) is a vertex whose removal increases the number of connected components. Which algorithm efficiently finds all articulation points?
Answer: Tarjan's DFS-based algorithm using discovery times and low values
Tarjan's algorithm tracks DFS discovery times and 'low' values to identify articulation points in O(V + E).
What is the space complexity of storing a trie (prefix tree) for a set of strings with total N characters?
Answer: O(N)
Each character in the input creates at most one trie node, so total nodes ≤ N, giving O(N) space (excluding per-node child pointers).