Microsoft Online Assessment (OA) - Max Network Rank

An infrastructure consisting of N cities from l to N, and M bidirectional roads between them are given. Roads do not intersect apart from at their start and endpoints (they can pass through underground tunnels to avoid collisions).

For each pair of cities directly connected by a road, let’s define their network rank as the total number of roads that are connected to either of the two cities.

Write a function, given two arrays A, B consisting of M integers each and an integer N, where A[i] and B[i] are cities at the two ends of the i-th road, returns the maximal network rank in the whole infrastructure.

Example:

Input:

A = [1, 2, 3, 3]
B = [2, 3, 1, 4]
N = 4

Output:

4

Explanation:

The chosen cities may be 2 and 3, and the four roads connected to them are: (2,1), (2,3), (3,1), (3,4).

Try it yourself

1
1
from typing import List
2
2
3
3
def maxNetworkRank(A: List[int], B: List[int], N: int) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
4
+
      adj = [0] * (N + 1)
5
5
6
6
7
+
      for a, b in zip(A, B):
8
+
          adj[a] += 1
9
+
          adj[b] += 1
10
+
11
+
      max_rank = 0
12
+
13
+
      for a, b in zip(A, B):
14
+
          max_rank = max(max_rank, adj[a] + adj[b] - 1)
15
+
16
+
      return max_rank
17
+
7
18
if __name__ == '__main__':
8
19
    a = [int(x) for x in input().split()]
9
20
    b = [int(y) for y in input().split()]
10
21
    n = int(input())
Expand 2 lines ...