Bridges in an Undirected Graph
Updated
Problem statement
An undirected graph has n nodes, numbered 0 to n - 1, and the edges in edges, where edges[i] = [a, b] joins nodes a and b. The graph does not have to be connected.
An edge is a bridge if removing it leaves its two end nodes with no path between them. Return all bridges. Write each bridge as [u, v] with u < v, and sort the list by u, then by v. If there is no bridge, return an empty list.
Function
findBridges(n: int, edges: int[][]) → int[][]Examples
Example 1
n = 7edges = [[0,1],[1,2],[2,0],[1,4],[3,4],[4,5],[5,6],[6,3]]return = [[1,4]]Nodes 0, 1, 2 form a triangle and nodes 3, 4, 5, 6 form a loop of four. Every edge inside them lies on a cycle. The edge between 1 and 4 is the only link between the two groups, so it is the only bridge.
Example 2
n = 5edges = [[0,1],[1,2],[1,3],[3,4]]return = [[0,1],[1,2],[1,3],[3,4]]The graph is a tree (no cycles), so removing any edge splits it. All four edges are bridges, listed in sorted order.
Example 3
n = 6edges = [[3,0],[1,2],[2,3],[0,1],[5,4]]return = [[4,5]]Nodes 0 to 3 form a loop, so none of its edges is a bridge. Nodes 4 and 5 are joined by one edge only, which is a bridge, written as [4,5] with the smaller node first.
Constraints
1 <= n <= 10001 <= edges.length <= 3000edges[i].length == 2and0 <= edges[i][0], edges[i][1] < n- No edge joins a node to itself, and no two edges join the same pair of nodes.
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Minimum Boards to Cover Roof HolesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Visit Desired Attractions Without Reusing a TrailDuolingo · PHONE SCREENDuolingo interview questions
- Attraction Route Without Reusing TrailsWhatNot · PHONE SCREENWhatNot interview questions
- Spreadsheet With Dependent CellsCharacter.AI · PHONE SCREEN
- Course Order and CycleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Evaluate Live Spreadsheet ExpressionsStrala · PHONE SCREEN
- Enumerate Directed Paths and CyclesByteDance · PHONE SCREENByteDance interview questions
- Process Graph Rule ValidationHadrian · PHONE SCREENHadrian interview questions
- Spreadsheet Formula EvaluatorPika · PHONE SCREEN
- Group Training Overdue RollupVanta · PHONE SCREEN
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)