Question

Microsoft | OA Coding Questions and Solutions | Set - 61 | 2022

Answer 1

I was asked this question in a Microsoft Online Assessment test.

 

 

 

Comments: 7

Answer 2

Assumptions or given : total nodes will N always.
We can only use the value if that node has an Edge
we want the height value.
Intuitively I think:
1.Find out rank of each node by counting each node in both arrays. iterator and keep counting both vertex in a map.
2. Now to maximize pick the node's from heighest degree to lowest. -> good thing is nodes which are not connected to anything other will have a zero degree hence won't be present in the map.
3. Put all counters in priority queue to sort by count in decreasing order.
4. Start value from N and loop over pq for each sum+= (N*pq.pop().degree);N--;
5. return sum;

Answer 3

Assign the values in order of the degree of each node (no. of edges each node has). O(n) solution.

 

int maxGraph(vector<int> &A, vector<int> &B, int N) {
    vector<pair<int,int>> freq(N, {0, 0});
    vector<int> assign(N, 0);
    int sm=0;
    for(int i=0; i<N; i++)
        freq[i].second = i;
    for(int i=0; i<A.size(); i++)
        freq[A[i]-1].first++;
    for(int i=0; i<B.size(); i++)
        freq[B[i]-1].first++;
    sort(freq.begin(), freq.end());
    for(int i=freq.size()-1; i>-1; i--)
        assign[freq[i].second] = i+1;
    for(int i=0; i<A.size(); i++)
    sm += assign[A[i]-1];
    for(int i=0; i<B.size(); i++)
    sm += assign[B[i]-1];
    return sm;
}