← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Microsoft SWE interview with a graph/tree problem that looks deceptively clean until you actually try to implement it. One question, but it had enough edge cases to keep me busy.

Questions Asked (1)

Q1

You're given a list of directed edges that originally formed a rooted tree, but one extra edge was added. Find and return the edge to remove so the graph becomes a valid rooted tree again. If multiple candidates exist, return the last one in the input.

Algorithms & Data Structures
Author's notes

I knew union-find was involved but kept second-guessing myself on the two-case split: when a node ends up with two parents vs when there's a cycle but no double-parent.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify nodes with indegree 2 (candidates for the extra edge) and detect if a cycle exists. If a cycle exists, remove the edge that breaks the cycle; otherwise, remove the last candidate edge in the input order. Use DFS or Union-Find to efficiently detect cycles and validate the tree structure.

Pro tip: Clarify the definition of a rooted tree: exactly one root with indegree 0, all other nodes indegree 1, and no cycles. Handling the 'last in input' tie-breaker correctly shows attention to detail.

1. Understand the problem and constraints

Confirm that a valid rooted tree has exactly one root (indegree 0), all other nodes indegree 1, and no cycles. Note that the extra edge may create a node with indegree 2 or a cycle, or both.

2. Identify candidate edges

Scan the edges to find any node with indegree 2. If such a node exists, the two incoming edges are candidates for removal. If no node has indegree 2, the extra edge must be part of a cycle.

3. Detect cycles

Use DFS or Union-Find to check for cycles in the graph. If a cycle exists, determine which candidate edge (if any) lies on the cycle; that edge must be removed to break the cycle.

4. Apply tie-breaking rule

If multiple edges could be removed (e.g., both candidates break the cycle or no cycle exists), choose the one that appears last in the input order.

5. Validate and return

After removing the chosen edge, verify that the resulting graph is a valid rooted tree (single root, no cycles, all indegrees correct). Return the removed edge.

Key Points to Mention

  • Definition of a rooted tree: exactly one root with indegree 0, all other nodes indegree 1, and no cycles.
  • Indegree analysis to find nodes with indegree 2, which indicate the extra edge.
  • Cycle detection using DFS (with recursion stack) or Union-Find to identify if the extra edge creates a cycle.
  • Handling cases: extra edge creates only indegree 2, only a cycle, or both.
  • Tie-breaking rule: when multiple valid edges exist, return the one that appears last in the input.
  • Time and space complexity: O(n) time and O(n) space for graph traversal.

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