Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Microsoft SWE interview with a graph problem that sounds straightforward until you actually sit down with it. One question, tree/graph territory, no behavioral stuff mentioned.

Questions Asked (1)

You're given a directed graph that was originally a rooted tree of N nodes (values 1 to N), with exactly one extra directed edge added. Given the edge list, find and return an edge that can be removed to restore it to a valid rooted tree. If multiple valid answers exist, return the one that appears last in the input array.

Algorithms & Data Structures

Author's notes

This one took me a minute to even parse correctly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify the type of violation introduced by the extra edge: either a node has two parents (in-degree 2) or the graph contains a cycle (or both). Then, systematically test candidate edges to remove, ensuring the remaining graph is a valid rooted tree with exactly one root (in-degree 0) and all other nodes having in-degree 1, and no cycles. If multiple valid edges exist, return the one that appears last in the input.

Pro tip: Clarify with the interviewer whether the tree is rooted at a specific node or if any node can be the root; this affects the validity check. Also, mention that you can solve it in O(N) time by using union-find or DFS to detect cycles and in-degree violations.

1. Analyze in-degrees

Compute the in-degree of each node. If any node has in-degree 2, the extra edge is one of the two incoming edges to that node; otherwise, the extra edge creates a cycle and all nodes have in-degree 1.

2. Identify candidate edges

If a node has in-degree 2, the two edges pointing to it are candidates. If no such node, the extra edge is part of a cycle; find the cycle and consider each edge in the cycle as a candidate.

3. Test candidates

For each candidate edge (in reverse order if multiple), remove it and check if the remaining graph is a valid rooted tree: exactly one node with in-degree 0 (root), all others in-degree 1, and no cycles (connected and acyclic).

4. Return the last valid edge

If multiple candidates yield a valid tree, return the one that appears last in the input array. If only one works, return that.

Key Points to Mention

In-degree analysis: a valid rooted tree has exactly one node with in-degree 0 (root) and all others with in-degree 1.
Cycle detection: use DFS or union-find to detect cycles efficiently.
Handling multiple candidates: test edges in reverse order to satisfy the 'last in input' requirement.
Time complexity: O(N) with careful implementation, where N is the number of nodes.
Edge cases: when the extra edge creates both a cycle and a node with in-degree 2, only one of the two incoming edges will resolve both issues.
Root determination: the root is the node with in-degree 0 after removal; ensure exactly one such node exists.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.