CodeSignal Technical Assessment Graph and Tree Algorithms 3 — Questions and Answers
Question 1: Given an undirected tree with N nodes, how many edges does it have?
- N
- N - 1 (Correct answer)
- N + 1
- 2N - 1
Correct answer: N - 1
Any tree with N nodes has exactly N - 1 edges, as each added node requires exactly one new edge.
Question 2: What is the time complexity of finding the Lowest Common Ancestor (LCA) using binary lifting after O(N log N) preprocessing?
- O(N)
- O(log N) (Correct answer)
- O(sqrt(N))
- O(1)
Correct answer: O(log N)
Binary lifting precomputes 2^k ancestors for each node, allowing LCA queries in O(log N) time.
Question 3: In BFS on an unweighted graph, the first time a node is dequeued, its distance from the source is guaranteed to be:
- An overestimate
- The shortest path distance (Correct answer)
- The longest path distance
- Undefined until all nodes are processed
Correct answer: The shortest path distance
BFS explores nodes in non-decreasing order of distance, so the first visit gives the exact shortest path.
Question 4: Which data structure is most commonly used to implement a disjoint set (Union-Find) with path compression and union by rank?
- Balanced BST
- Hash map of parent arrays
- Array-based parent pointers (Correct answer)
- Linked list
Correct 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.
Question 5: What does the 'diameter' of a tree represent?
- The number of leaf nodes
- The depth of the deepest node
- The longest path between any two nodes (Correct answer)
- The number of edges in a spanning tree
Correct 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.
Question 6: In a weighted directed graph, the Bellman-Ford algorithm detects negative weight cycles. How many edge relaxations does it perform?
- V relaxations
- E relaxations
- V - 1 relaxations per edge
- (V - 1) * E relaxations (Correct answer)
Correct 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.
Question 7: Which of the following graph representations uses O(V + E) space?
- Adjacency matrix
- Edge list only
- Adjacency list (Correct answer)
- Incidence matrix
Correct answer: Adjacency list
An adjacency list stores each vertex once and each edge (or two half-edges for undirected), totaling O(V + E) space.
CodeSignal Technical Assessment Graph and Tree Algorithms 3
Given an undirected tree with N nodes, how many edges does it have?