CodeSignal Technical Assessment Graph and Tree Algorithms 2 — Questions and Answers
Question 1: In Dijkstra's algorithm using a min-heap, what is the time complexity for a graph with V vertices and E edges?
- O(V^2)
- O((V + E) log V) (Correct answer)
- O(E log E)
- O(V * E)
Correct answer: O((V + E) log V)
Using a binary min-heap, each edge relaxation costs O(log V), giving O((V + E) log V) overall.
Question 2: Which traversal of a Binary Search Tree visits nodes in sorted ascending order?
- Pre-order
- Post-order
- In-order (Correct answer)
- Level-order
Correct answer: In-order
In-order traversal (left → root → right) on a BST always visits keys in non-decreasing order.
Question 3: A graph has a cycle if and only if DFS produces a back edge. What does a 'back edge' connect?
- Two nodes at the same DFS depth
- A node to an ancestor in the DFS tree (Correct answer)
- Two unvisited nodes
- A node to a node in a different DFS component
Correct answer: A node to an ancestor in the DFS tree
A back edge connects a vertex to one of its ancestors in the DFS recursion stack, forming a cycle.
Question 4: What is the maximum number of nodes in a complete binary tree of height h?
- 2^h
- 2^(h+1) - 1 (Correct answer)
- h^2
- 2h + 1
Correct answer: 2^(h+1) - 1
A complete binary tree of height h has at most 2^(h+1) - 1 nodes (all levels filled).
Question 5: Which algorithm finds the Minimum Spanning Tree by always adding the globally smallest edge that does not form a cycle?
- Prim's
- Kruskal's (Correct answer)
- Borůvka's
- Dijkstra's
Correct answer: Kruskal's
Kruskal's algorithm sorts all edges and greedily adds the smallest edge that connects two different components.
Question 6: In a directed graph, what does Kosaraju's algorithm compute?
- Shortest paths from a single source
- Strongly Connected Components (SCCs) (Correct answer)
- Minimum Spanning Tree
- Topological sort
Correct answer: Strongly Connected Components (SCCs)
Kosaraju's runs DFS twice—once on the original and once on the transposed graph—to identify all SCCs.
Question 7: What property must a graph satisfy for a topological sort to exist?
- It must be undirected
- It must be a DAG (Directed Acyclic Graph) (Correct answer)
- It must be connected
- It must have no self-loops only
Correct answer: It must be a DAG (Directed Acyclic Graph)
Topological ordering is only defined for Directed Acyclic Graphs; any cycle makes a linear ordering impossible.
CodeSignal Technical Assessment Graph and Tree Algorithms 2
In Dijkstra's algorithm using a min-heap, what is the time complexity for a graph with V vertices and E edges?