Redundant Connection
Updated
Problem statement
A tree with n nodes labelled 1 to n had one extra edge added, between two different nodes that were not already directly connected. You are given all n undirected edges as edges[i] = [a_i, b_i].
Return an edge that can be removed so that the remaining n - 1 edges form a tree again. If several edges work, return the one that appears last in edges. Return it exactly as it appears in the input.
Function
findRedundantConnection(edges: int[][]) → int[]Examples
Example 1
edges = [[1,2],[1,3],[2,3]]return = [2,3]The three edges form one cycle 1-2-3. Removing any of them leaves a tree; the one that comes last in the input is [2, 3].
Example 2
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]return = [1,4]The cycle is 1-2-3-4-1, using edges [1,2], [2,3], [3,4] and [1,4]. Edge [1,5] is not on it, so removing it would cut node 5 off. Of the cycle edges, [1,4] comes last, so it is the answer.
Constraints
n == edges.lengthand3 <= n <= 500edges[i].length == 2and1 <= a_i < b_i <= n- No edge appears twice, and the graph is a tree on the nodes
1tonplus exactly one extra edge.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Evaluate DivisionPlaud · ONSITE INTERVIEW
- Count Friend CirclesOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Determine Whether Two Horses Are Genetically RelatedGoogle · ONSITE INTERVIEWGoogle interview questions
- Count Connected Components in an Undirected GraphNutanix · ONSITE INTERVIEWNutanix interview questions
- Connected GroupsFivetran · ONSITE INTERVIEWFivetran interview questions
- Largest Island After One Land ConversionAmazon · ONSITE INTERVIEW
- Making a Large IslandMeta · ONSITE INTERVIEWMeta interview questions
- Largest Island After One Land ConversionBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Evaluate DivisionApple · PHONE SCREENApple interview questions
- Minimum Unreachable WarehousesVisa · OAVisa interview questions