← Apple Interview Insights

Apple·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Apple SWE interview with a graph problem that looks straightforward until you actually have to code it under pressure. One question, cycle detection, and the clock is ticking.

Questions Asked (1)

Q1

You're given an undirected graph that was originally a tree with n nodes, but one extra edge was added creating exactly one cycle. Given the edge list, find and return the edge that can be removed to restore it to a tree. If there are multiple valid answers, return the one that appears last in the input.

Algorithms & Data Structures
Author's notes

Union-Find is the clean solution here and I knew that going in, but I second-guessed myself halfway through and started rambling about DFS instead.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use Union-Find to process edges in order, and when an edge connects two already-connected nodes, it is part of the cycle. To handle multiple valid answers, process edges in reverse order and return the first edge that creates a cycle, which corresponds to the last such edge in the original input.

Pro tip: Clarify the tie-breaking rule upfront: if multiple edges can be removed, return the one that appears last in the input. This shows attention to detail and avoids ambiguity.

1. Understand the problem

Recognize that the graph is a tree plus one extra edge, so it contains exactly one cycle. Removing any edge on that cycle restores a tree, but we need the one that appears last in the input.

2. Choose Union-Find

Use Union-Find (Disjoint Set Union) to efficiently detect cycles while processing edges. This is optimal for connectivity checks.

3. Process edges in reverse

Iterate through the edge list from last to first. For each edge, if its endpoints are already in the same set, it is the redundant edge; return it immediately.

4. Handle union operations

If the endpoints are not connected, union their sets. Continue until the redundant edge is found.

5. Return the result

The first redundant edge encountered in reverse order is the last redundant edge in the original order, satisfying the tie-breaking rule.

Key Points to Mention

  • Union-Find data structure with path compression and union by rank for near-constant time operations.
  • Cycle detection: an edge creates a cycle if its endpoints are already in the same connected component.
  • Tie-breaking: processing in reverse ensures we find the last valid edge in the original input.
  • Time complexity: O(n α(n)) which is effectively linear, and space complexity O(n).
  • Alternative approach: DFS to find the cycle, then pick the last edge on the cycle, but Union-Find is simpler and more efficient.
  • Edge cases: multiple edges between same nodes? No, graph is simple. Ensure the graph is connected and has exactly n edges.

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