Interview questions · Microsoft
Identify the Extra Directed Edge
This question evaluates understanding of graph theory concepts—directed trees, parent-child constraints, and cycle detection—and measures competency in reasoning about how a single extra directed edge can violate rooted-tree properties.
You are given a list of directed edges edges, where each edge is represented as [parent, child]. The graph contains nodes labeled from 1 to n, and it was originally a rooted tree with exactly one extra directed edge added.
A valid rooted tree must satisfy all of the following:
- Exactly one node is the root and has no parent.
- Every other node has exactly one parent.
- All nodes are reachable from the root.
- There are no directed cycles.
Your task is to return the single edge that should be removed so that the remaining edges form a valid rooted tree.
If there are multiple candidate edges, return the one that appears last in the input.
Example:
- Input:
[[1,2],[1,3],[2,3]] - Output:
[2,3]
Community answers
Nothing here yet.
Join in on CSWork →