Microsoft Online Assessment (OA) 2021 - Max Network Rank | Codility

An infrastructure consisting of n cities from l to n and m bidirectional roads between them is given. Roads do not intersect except 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 starts, ends consisting of m integers each and an integer n, where starts[i] and ends[i] are cities at the two ends of the i-th road, returns the maximal network rank in the whole infrastructure.

Example:

Input:

starts = [1, 2, 3, 3]
ends = [2, 3, 1, 4]
n = 4

Output:

Explanation:

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

Try it yourself

1def max_network_rank(starts: list[int], ends: list[int], n: int) -> int:
2    adj = [0] * (n + 1)
3
4    for a, b in zip(starts, ends):
5        adj[a] += 1
6        adj[b] += 1
7
8    max_rank = 0
9
10    for a, b in zip(starts, ends):
11        max_rank = max(max_rank, adj[a] + adj[b] - 1)
12
13    return max_rank
14
15if __name__ == "__main__":
16    starts = [int(x) for x in input().split()]
17    ends = [int(x) for x in input().split()]
18    n = int(input())
19    res = max_network_rank(starts, ends, n)
20    print(res)
21

1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int maxNetworkRank(List<Integer> starts, List<Integer> ends, int n) {
8        int[] edgeCount = new int[n];
9        int m = starts.size();
10        int maxRank = Integer.MIN_VALUE;
11
12        for (int i = 0; i < m; i++) {
13            edgeCount[starts.get(i) - 1]++;
14            edgeCount[ends.get(i) - 1]++;
15        }
16
17        for (int i = 0; i < m; i++) {
18            int rank = edgeCount[starts.get(i) - 1] + edgeCount[ends.get(i) - 1] - 1;
19            if (rank > maxRank) {
20                maxRank = rank;
21            }
22        }
23
24        return maxRank;
25    }
26
27    public static List<String> splitWords(String s) {
28        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
29    }
30
31    public static void main(String[] args) {
32        Scanner scanner = new Scanner(System.in);
33        List<Integer> starts = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
34        List<Integer> ends = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
35        int n = Integer.parseInt(scanner.nextLine());
36        scanner.close();
37        int res = maxNetworkRank(starts, ends, n);
38        System.out.println(res);
39    }
40}
41

1"use strict";
2
3function maxNetworkRank(starts, ends, n) {
4    const edgeCount = {};
5    let maxRank = 0;
6    const m = starts.length;
7
8    for (let i = 0; i < m; i++) {
9        edgeCount[starts[i]] = (edgeCount[starts[i]] ? edgeCount[starts[i]] : 0) + 1;
10        edgeCount[ends[i]] = (edgeCount[ends[i]] ? edgeCount[ends[i]] : 0) + 1;
11    }
12
13    for (let j = 0; j < m; j++) {
14        const rank = edgeCount[starts[j]] + edgeCount[ends[j]] - 1;
15        if (rank > maxRank) {
16            maxRank = rank;
17        }
18    }
19
20    return maxRank;
21}
22
23function splitWords(s) {
24    return s === "" ? [] : s.split(" ");
25}
26
27function* main() {
28    const starts = splitWords(yield).map((v) => parseInt(v));
29    const ends = splitWords(yield).map((v) => parseInt(v));
30    const n = parseInt(yield);
31    const res = maxNetworkRank(starts, ends, n);
32    console.log(res);
33}
34
35class EOFError extends Error {}
36{
37    const gen = main();
38    const next = (line) => gen.next(line).done && process.exit();
39    let buf = "";
40    next();
41    process.stdin.setEncoding("utf8");
42    process.stdin.on("data", (data) => {
43        const lines = (buf + data).split("\n");
44        buf = lines.pop();
45        lines.forEach(next);
46    });
47    process.stdin.on("end", () => {
48        buf && next(buf);
49        gen.throw(new EOFError());
50    });
51}
52

1function maxNetworkRank(starts: number[], ends: number[], n: number): number {
2    const edgeCount: Record<number, number> = {};
3    let maxRank = 0;
4    const m = starts.length;
5
6    for (let i = 0; i < m; i++) {
7        edgeCount[starts[i]] = (edgeCount[starts[i]] ? edgeCount[starts[i]] : 0) + 1;
8        edgeCount[ends[i]] = (edgeCount[ends[i]] ? edgeCount[ends[i]] : 0) + 1;
9    }
10
11    for (let j = 0; j < m; j++) {
12        const rank = edgeCount[starts[j]] + edgeCount[ends[j]] - 1;
13        if (rank > maxRank) {
14            maxRank = rank;
15        }
16    }
17
18    return maxRank;
19}
20
21function splitWords(s: string): string[] {
22    return s === "" ? [] : s.split(" ");
23}
24
25function* main() {
26    const starts = splitWords(yield).map((v) => parseInt(v));
27    const ends = splitWords(yield).map((v) => parseInt(v));
28    const n = parseInt(yield);
29    const res = maxNetworkRank(starts, ends, n);
30    console.log(res);
31}
32
33class EOFError extends Error {}
34{
35    const gen = main();
36    const next = (line?: string) => gen.next(line ?? "").done && process.exit();
37    let buf = "";
38    next();
39    process.stdin.setEncoding("utf8");
40    process.stdin.on("data", (data) => {
41        const lines = (buf + data).split("\n");
42        buf = lines.pop() ?? "";
43        lines.forEach(next);
44    });
45    process.stdin.on("end", () => {
46        buf && next(buf);
47        gen.throw(new EOFError());
48    });
49}
50