FastPrepRedundant Connection
Problems/Redundant Connection

Redundant Connection

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a review of a Microsoft software engineering internship. The task as reported is a hard graph question in one of two interviews held one after the other, after some behavioral questions. The author is not sure which problem it was and guesses the redundant-connection problem. The same interview had a behavioral question about teamwork.

We use that guess. The graph is a tree on n nodes plus one extra edge. You return the edge to remove so that a tree is left, choosing the one that comes last in the input when several work. Nodes are labelled 1 to n with n up to 500.

Our version is about 65% the same as the reported question.

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.length and 3 <= n <= 500
  • edges[i].length == 2 and 1 <= a_i < b_i <= n
  • No edge appears twice, and the graph is a tree on the nodes 1 to n plus 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

Interview reports that mention this question

  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        // Write your code here.
    }
}
Checking account…