Redundant Connection
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
A tree with one extra edge added is given as edges (nodes 1 to n). Return the edge that can be removed to make it a tree again; if several, the one that appears last.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What does the extra edge do that no other edge does?
- Hint 2Use groups: an edge inside one group is redundant.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Laying cables between offices one at a time. For each new cable ask: "are these two offices already connected through other cables?" If yes, this cable is redundant. Since there is exactly one extra, the first cable that gets that answer (processing in the given order) is the extra one.
- The obvious way
Remove each edge in reverse order and test if the rest is a tree: O(n²).
- The key insight
Give every node its own head. For each edge in order: find both heads; if equal, this edge is the answer; otherwise merge. Because the input has exactly one cycle, the first edge to close it is the last one that was needed to form it, which is the answer.
- The algorithm
- head[v] = v for nodes 1..n.
- For each edge: find both heads.
- Equal heads: return this edge.
- Else merge the groups.
Watch it run
Exampleedges = [[1,2],[1,3],[2,3]]
Cable 1-2: the offices are separate. Connect them.
groups: {1,2} {3}Where people slip
- Nodes start at 1, so the array has n + 1 slots.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_redundant_connection(edges):
head = list(range(len(edges) + 1)) # nodes are numbered from 1
def find(office):
while head[office] != office:
head[office] = head[head[office]]
office = head[office]
return office
for first, second in edges:
first_head, second_head = find(first), find(second)
if first_head == second_head:
return [first, second] # already connected: this cable is extra
head[first_head] = second_headNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.