Critical Connections in a Network

HardGraphstarjan

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A network has n servers labeled 0 to n - 1 joined by undirected links connections[i] = [a, b]. Every server can reach every other server. A link is **critical** if removing it disconnects some pair of servers (a bridge in graph terms). Return all critical links. Write each link as [u, v] with u < v, and sort the list in ascending order by u, then by v. Return an empty list if there are none. Aim for O(n + connections.length) time.

Examples

Input: n = 6, connections = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5],[5,3]]
Output: [[2,3]]
The link 2-3 is the only connection between the triangles {0,1,2} and {3,4,5}.
Input: n = 2, connections = [[0,1]]
Output: [[0,1]]
Removing the only link separates the two servers.

Constraints

  • 2 <= n <= 10^4
  • n - 1 <= connections.length <= 2 * 10^4
  • 0 <= a, b < n and a != b
  • No link appears twice
  • The network is connected

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.