Best solutions for Microsoft interview tasks. Max Network Rank.

Description:

Solution:

It seems in this task we just need to count connected to each pair of given cities and that is all.

Lets visualize the example. Table of the connected cities should looks like:

1 – 2

2 – 3

3 – 1

3 – 4

We can build a graph by this table. It will looks like:

It’s easy to see that pair 2 – 3 has the biggest number of connections to the other cities and number of these connections is 4.

C++ code:

int solution(const vector<int>&A, const vector<int>&B, int N){
    int roads_num = A.size(); // M
    vector<int> cities(N + 1, 0);

    // count number of roads to the pair of cities
    for(int i = 0; i < roads_num; ++i) {
        cities[A[i]]++;
        cities[B[i]]++;
    }
    int result = INT_MIN;

    // Find maximum number of roads connected to the pair
    // of cities except the road between these two cities
    // because it was counted twice for each city.
    for(int i = 0; i < roads_num; ++i) {
        result = max(result, cities[A[i]] + cities[B[i]] - 1);
    }

    return result;
}

Full project you can find here: https://github.com/jolly-fellow/microsoft/tree/master/max_network_rank

Return to the table of contents.