Question

Microsoft SDE Role | On Campus | OA Coding Questions and Solutions | Set - 18 | 2022

Answer 1

images of ques

Answer 2

C++ solution with comments both test cases passed
Simple dfs solution keeping the count of number of cars and number of people and merging max possible number of people (5) in same car.
Let me if anyone has a test case that gives WA.

 

// snippet by shubham7811
#include<bits/stdc++.h>
using namespace std;

pair<int, int> dfs(int curr, vector<vector<int>> &g, vector<int> &vis, int &ans) {
    vis[curr] = 1;
    int people = 1;
    for (int x : g[curr]) {
        if (vis[x]) continue;
        pair<int, int> res = dfs(x, g, vis, ans);
        // adding number of people to combine them in same cars
        people += res.first;
        // adding number of cars that came to this point as each car will take 1ltr fuel
        ans += res.second;
    }
    int cars = (people + 4) / 5;  // number of 5 seater cars required
    return {people, cars};
}


int solution(vector<int> &A, vector<int> &B) {
    int n = A.size() + 1; // number of nodes
    // creating adjacency list
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int a = A[i];
        int b = B[i];
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> vis(n);
    int ans = 0; // ans -> will pass in dfs function by reference
    dfs(0, g, vis, ans);
    return ans;
}

int32_t main() {
    int t = 1;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> A(n), B(n);
        for (int i = 0; i < n; i++)
            cin >> A[i];
        for (int i = 0; i < n; i++)
            cin >> B[i];
        cout << solution(A, B) << endl;
    }
    return 0;
}

/*
INPUT
2
3
0 1 1
1 2 3
9
1 1 1 9 9 9 9 7 8
2 0 3 1 6 5 4 0 0

*/

Answer 3

Suppose the graph(tree) as rooted in node 0. We make a dfs on node 0 and dfs call on a node return two things, 1)number of nodes under its subtree(including itself) and 2)minimum fuel spent for all people under its subtree to come to this node.

 

import math


def solution(A, B):
    n = len(A)
    adj = [[] for _ in range(n + 1)]
    for u, v in zip(A, B):
        adj[u].append(v)
        adj[v].append(u)

    visited = set()

    def dfs(node):
        visited.add(node)

        subtree_nodes_count = 1
        subtree_fuel_spent = 0
        for neighbor in adj[node]:
            if neighbor not in visited:
                nodes_count, fuel_spent = dfs(neighbor)
                subtree_nodes_count += nodes_count
                subtree_fuel_spent += (fuel_spent + math.ceil(nodes_count / 5))

        return subtree_nodes_count, subtree_fuel_spent

    return dfs(0)[1]


print(
    solution(
        [1, 1, 1, 9, 9, 9, 9, 7, 8],
        [2, 0, 3, 1, 6, 5, 4, 0, 0]
    )
)

Answer 4

Simple DFS solution.

 

int ans;
public int minFuel(int[] a, int[] b, int n) {
 List<Integer>[] outs = new List[n+1];
 for(int i=0; i<a.length; i++) {
  if(outs[a[i]]==null) outs[a[i]] = new ArrayList<>();
  outs[a[i]].add(b[i]);
  if(outs[b[i]]==null) outs[b[i]] = new ArrayList<>();
  outs[b[i]].add(a[i]);
 }
 ans = 0;
 boolean[] visited = new boolean[n+1];
 dfs(0, outs, visited);
 return ans;
}

private int dfs(int node, List<Integer>[] outs, boolean[] visited) {
 visited[node] = true;
 int passengers = 0;
 for(int neighbor : outs[node]) {
  if(visited[neighbor]) continue;
  passengers+=dfs(neighbor, outs, visited);
 }
 passengers++;
 if(node!=0) ans+=(passengers-1)/5+1;
 return passengers;
}