How should I practice Reconstruct a Graph into a Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related LinkedIn onsite interview problems in FastPrep.

Is Reconstruct a Graph into a Tree associated with LinkedIn?

FastPrep tags this as a LinkedIn onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Reconstruct a Graph into a Tree

Learn this problem

● Medium

LinkedInFULLTIMEONSITE INTERVIEW

Problem statement

You are given a connected, undirected graph with n vertices numbered from 0 through n - 1 and an array edges.

Reconstruct the graph as its canonical spanning tree. First normalize every edge as [min(u, v), max(u, v)] and sort all normalized edges lexicographically. Scan them in that order and keep an edge exactly when it connects two components that are not yet connected.

Return the kept edges in scan order. The result must contain exactly n - 1 edges and connect every vertex without a cycle.

Function

buildCanonicalTree(n: int, edges: int[][]) → int[][]

Examples

Example 1

n = 4edges = [[1,3],[0,2],[0,1],[1,2],[2,3]]return = [[0,1],[0,2],[1,3]]

After sorting, [0,1] and [0,2] are kept. Edge [1,2] would create a cycle, so it is skipped; [1,3] then connects the final vertex.

Example 2

n = 5edges = [[3,4],[1,4],[0,3],[1,2],[0,1],[2,3]]return = [[0,1],[0,3],[1,2],[1,4]]

The first four lexicographically sorted edges each join separate components, so they form the canonical tree. Every later edge would create a cycle.

Constraints

1 <= n <= 200000.
0 <= edges.length <= 200000.
Every edge contains two distinct valid vertex IDs.
The graph is connected and has no duplicate undirected edges.
For n = 1, edges is empty and the answer is empty.