Maximal Network Rank

MediumGraphshashing

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

There are n cities labeled 0 to n - 1 and a list roads, where roads[i] = [a, b] is a two-way road between cities a and b. There is at most one road between any pair of cities and no road connects a city to itself. The **network rank** of two different cities is the number of distinct roads that touch at least one of them. A road that joins the two cities directly is counted once, not twice. Return the maximum network rank over all pairs of different cities.

Examples

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Cities `0` and `1` touch roads `[0,1]`, `[0,3]`, `[1,2]`, `[1,3]`: four distinct roads, with `[0,1]` counted once.
Input: n = 5, roads = [[0,1],[1,2],[3,4]]
Output: 3
Pair `(1,3)` touches `[0,1]`, `[1,2]`, and `[3,4]` for a rank of 3. Pair `(0,1)` only reaches 2 because their shared road is counted once.

Constraints

  • 2 <= n <= 100
  • 0 <= roads.length <= n * (n - 1) / 2
  • `roads[i].length == 2`, `a != b`
  • Each pair of cities has at most one road

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.

More hashing problems