How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Find the Extra Edge | Apple Coding Question

Q: Find the Extra Edge

This question evaluates understanding of graph theory concepts—cycle formation and edge connectivity—and the competency in applying graph algorithm techniques to identify and remove a redundant edge in an undirected graph.

Find the Extra Edge

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an undirected graph that started as a tree with `n` nodes labeled from `1` to `n`. One additional edge was then added between two different existing nodes, creating exactly one cycle. You are given an array `edges`, where `edges[i] = [u, v]` represents an undirected edge between nodes `u` and `v`. Return the edge that can be removed so that the remaining graph is a tree again. If multiple edges could be removed, return the one that appears last in the input order. **Example** ```text Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3] ``` **Constraints** - `n == edges.length` - `3 <= n <= 1000` - `1 <= u, v <= n` - `u != v` - The input graph is connected and contains exactly one cycle.

Quick Answer: This question evaluates understanding of graph theory concepts—cycle formation and edge connectivity—and the competency in applying graph algorithm techniques to identify and remove a redundant edge in an undirected graph.

You are given an undirected graph that originally formed a tree with nodes labeled from 1 to n. Exactly one additional edge was added between two different existing nodes, creating exactly one cycle. Given the list of edges, return the edge that can be removed so the graph becomes a tree again. If more than one edge could be removed, return the one that appears last in the input order.

Constraints

n == len(edges)
3 <= n <= 1000
1 <= u, v <= n
u != v
The graph is connected and contains exactly one cycle

Examples

Input: ([[1, 2], [1, 3], [2, 3]],)

Expected Output: [2, 3]

Explanation: This is the smallest valid case. The third edge closes the cycle 1-2-3-1, so removing [2, 3] restores a tree.

Input: ([[1, 4], [1, 2], [2, 3], [3, 4]],)

Expected Output: [3, 4]

Explanation: All four edges are part of the cycle. Any of them could be removed, so we return the one that appears last in the input: [3, 4].

Input: ([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]],)

Expected Output: [1, 4]

Explanation: The cycle is 1-2-3-4-1. The last edge from that cycle in the input is [1, 4].

Input: ([[1, 2], [2, 3], [3, 4], [4, 5], [2, 5]],)

Expected Output: [2, 5]

Explanation: The cycle is 2-3-4-5-2, and [2, 5] is the last edge from that cycle in the input.

Hints

A tree has no cycles. As you process edges one by one, what does it mean if the two endpoints are already connected?
Use a Disjoint Set Union (Union-Find) structure to track connected components efficiently while scanning the edges in input order.

Quick Overview

This question evaluates understanding of graph theory concepts—cycle formation and edge connectivity—and the competency in applying graph algorithm techniques to identify and remove a redundant edge in an undirected graph.