Question

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

Answer 1

 

Sample tests:
Input 1:
int[] A = {0,0,0,1,1,1,9,9,9};
int[] B = {7,8,1,2,3,9,4,5,6};

 

Output 1:
10

 

Input 2:
int[] A = {0,1,1}
int[] B = {1,2,3}

 

Output2:
3

Answer 2

You don't need to build tree. Just have an adjacency list and traverse in dfs fashion.

 

    pair<int,int> dfs(unordered_map<int,vector<int>>& al, int pos) {
        auto alv=al.find(pos);
        if(alv==al.end()) return make_pair(1,1); // leaf node
        
        pair<int,int> ret;
        int totalPeople=0;
        vector<int>& paths=alv->second;
        for(int i=0;i<paths.size();i++) {
            ret=dfs(al,paths[i]);
            int car=ret.first;
            int person=ret.second;
            totalCar+=car;
            totalPeople+=person;
        }
        int newPeople=totalPeople+1;
        int carRequired;
        if(newPeople/5==0) carRequired=1;
        else  carRequired=(newPeople/5)+(newPeople%5!=0);
        return make_pair(carRequired,newPeople);
    }
    
    int minCost(vector<int>&A, vector<int>&B) {
        unordered_map<int,vector<int>> al;
        for(int i=0;i<A.size();i++) {
            int u=A[i];
            int v=B[i];
            if(al.find(u)!=al.end()) {
                ((al.find(u))->second).push_back(v);
            } else {
                al.insert({u,{v}});
            }
        }
        
        dfs(al,0);
        return totalCar;
    }
private:
    int totalCar=0;

Answer 3

Solution -
Iterate list A, for each new value, create Node. While the value in this array remains the same, get the value from the second array at the same index and assign it as a child.
{000},{789} -> Node 0, children: 7, 8, 9

 

We get an N-inary graph.
Now, use post-order traveling (children first and then node) -

 

let totalGalones  = 0; // galones here means cars
function solution(root)  {
if(root == null) return 0;
let cars= 0;
for(let ch of root.children)
 cars+= solution(ch);
totalCars += Math.floor((cars / 5)) //only 5 passengers can fit in one car, thus we add to the total galones the amount of cars that rode out from the current node
return 1 + galons; //return to parent the total amount of passengers. It won't suffice to return "2 cars" as a result because if the current root returns 6 or 8 it makes big difference for the parent root 

 

TC: building graph O(n) + DFS O(n)
SC: If we work with lists (root -> children) then O(n)

Answer 4

1. make an array of size of n+1 storing the no. of child it has of int data type, use dfs for it, then bfs or dfs and update ans += (V[adj]-1)/5+1 return ans

 

import java.util.;
import java.io.;
import java.util.LinkedList;

 

class Pair{
int first;
int second;

 

Pair(int first,int second){
    this.first=first;
    this.second=second;
}

 

}

 

class C{

 

private int v;
private ArrayList<ArrayList<Integer>> adjList;

void makeGraph(int v){
    this.v=v;
    adjList=new ArrayList<>();
    for(int i=0;i<v;i++){
        adjList.add(new ArrayList<>());
    }
}

void add(int u,int v){
    adjList.get(u).add(v);
    adjList.get(v).add(u);
}

int dfs(int node,boolean vis[],int V[]){
    vis[node]=true;
    int val=1;
    for(int tn:adjList.get(node)){
        if(!vis[tn]){
            val+=dfs(tn,vis,V);
        }
    }
    V[node]=val;
    return val;
}
int solve(int n,int A[][]){
    makeGraph(n+1);

    for(int g[]:A)
        add(g[0],g[1]);

    int V[]=new int[v];
    int Indegree[]=new int[v];

    // Arrays.fill(V,1);

    boolean vis[]=new boolean[v];
    dfs(0,vis,V);

    System.out.println(Arrays.toString(V));
    vis=new boolean[v];
    Queue<Integer> q=new LinkedList<>();

    int ans=0;
    q.add(0);
    vis[0]=true;

    while(!q.isEmpty()){
        int node=q.poll();
        for(int tn:adjList.get(node)){
            if(!vis[tn]){
                ans+=(V[tn]-1)/5 + 1;
                q.add(tn);
                vis[tn]=true;
            }
        }
    }
    return ans;
}
public static void main(String[] args) {
    Scanner s=new Scanner(System.in);
    int n=s.nextInt();
    int e=s.nextInt();
    int A[][]=new int[e][2];
    for(int i=0;i<n;i++){
        A[i][0]=s.nextInt();
        A[i][1]=s.nextInt();
    }
    int ans=new C().solve(n,A);System.out.println(ans);
}

 

}