Maximal Network Rank Solution Microsoft OA 2023

Maximal Network Rank Solution Microsoft OA 2023

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi. The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once. The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities. Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2:

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.

Example 3:

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Constraints:

• 2 <= n <= 100
• 0 <= roads.length <= n * (n – 1) / 2
• roads[i].length == 2
• 0 <= ai, bi <= n-1
• ai != bi
• Each pair of cities has at most one road connecting them.

Also See: Amazon OA Online Assessment 2023 Questions and Answers

SOLUTION

Program: Maximal Network Rank Solution in C++

1. Create Adjacency Matrix for the graph
2. Create degree of all the nodes and insert into max heap.
3. Pop first max element from the heap
4. Pop second element from the heap
5. Keep finding element in heap utill it is equal to second max.
6. If first and second are not same , find if there exists are pair of popped out element with no path between first max and the all of the second maxs (return f+s) otherwise (return f+s-1)
7. If first and second element are same find if there exists a pair in all the first maxs with no path between them (return f+s) otherwise (f+s-1)

class Solution {
public:
int maximalNetworkRank(int n, vector<vector>& roads) {
vector<vector> grid;
grid.resize(n);
for(int i=0;i<n;i++)
{
grid[i].resize(n);
}
    for(int i=0;i<roads.size();i++)
    {
        grid[roads[i][0]][roads[i][1]]=1;
        grid[roads[i][1]][roads[i][0]]=1;
    }
    
    priority_queue<pair<int,int>, vector<pair<int,int>> > pq;
    for(int i=0;i<n;i++)
    {
        int sum=0;
        for(int j=0;j<n;j++)
        {
            sum+=grid[i][j];
        }
        
        pq.push(make_pair(sum,i));
    }
    
    vector<int> v;
    pair<int,int> a= pq.top();
    int x=a.first;
    v.push_back(a.second);
    pq.pop();
    pair<int,int> b=pq.top();
    int y=b.first;
    v.push_back(b.second);
    pq.pop();
    
    while(pq.size()!=0 && pq.top().first==b.first)
    {
        v.push_back(pq.top().second);
        pq.pop();
    }
        if(x!=y)
        {
            for(int i=1;i<v.size();i++)
            {
                if(grid[v[0]][v[i]]==0)
                {
                    return x+y;
                }
            }
            return x+y-1;
        }
    
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<v.size();j++)
        {
            if(i!=j && grid[v[i]][v[j]]==0)
            {   return x+y;
             break;
            }
        }
    }
    return x+y-1;
}};

Program: Maximal Network Rank Solution in Python

Solve this problem we need to :

• Find all candidates for most connected city
  • If there’s only 1 candidate for most connected city (let’s call it city1):
    • Find all candidates for second most connected city (let’s call it city2/cities2)
    • Loop through all cities in cities2
      • If any city2 has no connections to city1, return the sum of their (city1, and city2) connections
      • Otherwise return the sum of their connections -1 (to account for the common connection)
  • Otherwise loop through all possible combination of candidates:
    • If in any combination there’s no common edge, return the sum of their connections.
    • Otherwise return the sum of their number of connections -1.

from collections import defaultdict
class Solution:
    def computeConnections(self, roads):
        res = defaultdict(list)
        for road in roads:
            a, b = road
            res[a].append(b)
            res[b].append(a)
        return res
    
    def rankingConnections(self, connections):
        res = defaultdict(list)
        sortedRank = set()
        for city in connections:
            nOfConnections = len(connections[city])
            res[nOfConnections].append(city)
            sortedRank.add(nOfConnections)
        return res, sorted(list(sortedRank))
    
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        if not roads:
            return 0
        connections = self.computeConnections(roads)
        citiesWithNConnections, possibleNumberOfConnections = self.rankingConnections(connections)
        highestNumberOfConnections = possibleNumberOfConnections[-1]
        
        if len(citiesWithNConnections[highestNumberOfConnections]) == 1:
            # we loop through all the cities with the second highest number of connections
            # O(n) for n being the number of cities
            secondHighestNumberOfConnections = possibleNumberOfConnections[-2]
            city1 = citiesWithNConnections[highestNumberOfConnections][0]
            for city2 in citiesWithNConnections[secondHighestNumberOfConnections]:
                if city2 not in connections[city1]:
                    return highestNumberOfConnections+secondHighestNumberOfConnections
            return highestNumberOfConnections+secondHighestNumberOfConnections - 1
        else:
            # we loop through all the possible combination of cities that has
            # the highest number of connections
            # O(n^2) for n being the number of cities
            for i in range(len(citiesWithNConnections[highestNumberOfConnections])):
                for j in range(i+1, len(citiesWithNConnections[highestNumberOfConnections])):
                    city1 = citiesWithNConnections[highestNumberOfConnections][i]
                    city2 = citiesWithNConnections[highestNumberOfConnections][j]
                    if city2 not in connections[city1]:
                        return 2*highestNumberOfConnections
            return 2*highestNumberOfConnections-1

Also See: AMCAT Study Materials, Preparation Guide

Program: Maximal Network Rank Solution in Java

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] count=new int[n];
        int[][] direct=new int[n][n];
        
        for(int[] r:roads)
        {
            count[r[0]]++;
            count[r[1]]++;
            direct[r[0]][r[1]]=1;
            direct[r[1]][r[0]]=1;
        }
        
        int rank=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                rank=Math.max(rank,count[i]+count[j]-direct[i][j]);
            }
        }
        
        return rank;
    }
}

Microsoft Online Assessment 2023 Questions List

• Maximal Network Rank Solution
• Min Deletions To Obtain String in Right Format
• Day of week that is K days later Solution
• Minimum Adjacent Swaps to Make Palindrome Solution
• Lexicographically Smallest String
• Longest Substring Without Two Contiguous Occurrences of Letter
• String Without 3 Identical Consecutive Letters
• Microsoft OA Longest Semi-Alternating Substring
• Microsoft OA Min Steps to Make Piles Equal Height
• Max Inserts to Obtain String Without 3 Consecutive ‘a’
• Concatenated String Length with unique Characters
• Largest K such that both K and -K exist in array
• Microsoft OA Min Adj Swaps to Group Red Balls
• Maximum Length of a Concatenated String with Unique Characters
• Microsoft OA Unique Integers That Sum Up To 0
• Find N Unique Integers Sum up to Zero
• Microsoft OA Particle Velocity Solution
• Microsoft OA Arithmetic Slices Solution
• Microsoft OA Widest Path Without Trees Solution
• Microsoft OA Jump Game Solution
• Microsoft OA Fair Indexes Solution