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
Given an undirected tree with N nodes, how many edges does it have?
Answer: N - 1
Any tree with N nodes has exactly N - 1 edges, as each added node requires exactly one new edge.
What is the time complexity of finding the Lowest Common Ancestor (LCA) using binary lifting after O(N log N) preprocessing?
Answer: O(log N)
Binary lifting precomputes 2^k ancestors for each node, allowing LCA queries in O(log N) time.
In BFS on an unweighted graph, the first time a node is dequeued, its distance from the source is guaranteed to be:
Answer: The shortest path distance
BFS explores nodes in non-decreasing order of distance, so the first visit gives the exact shortest path.
Which data structure is most commonly used to implement a disjoint set (Union-Find) with path compression and union by rank?
Answer: Array-based parent pointers
Union-Find is typically implemented with a parent array plus a rank/size array, giving near-O(1) amortized operations.
What does the 'diameter' of a tree represent?
Answer: The longest path between any two nodes
The diameter of a tree is the length of the longest path (in edges or weight) between any two nodes.
In a weighted directed graph, the Bellman-Ford algorithm detects negative weight cycles. How many edge relaxations does it perform?
Answer: (V - 1) * E relaxations
Bellman-Ford relaxes all E edges exactly V - 1 times, for a total of (V-1)*E relaxations, then checks once more for negative cycles.
Which of the following graph representations uses O(V + E) space?
Answer: Adjacency list
An adjacency list stores each vertex once and each edge (or two half-edges for undirected), totaling O(V + E) space.