Question

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

Answer 1

There are N cities. Cities are connected by roads .(Basically given a graph). K of the cities has a hospital(Given an array of size K). Time taken to reach a hospital from a city is no of edges to the nearest city which contains a hospital. Find the maximum time taken to reach a hospital from all the N cities.

Answer 2

This seems to be correct based on my tests. Multi-source BFS.

 

from collections import deque

# graph is an adjacency list, where graph[i] = set([j, k]) means
# that there's a road between i and j, i and k
# assumes that cities are labeled from [0, n - 1], and that
# if j is in graph[i], then i is in graph[j] as well.
def nearestCityWithHospital(graph, hospitalCities):
    n = len(graph)
    bfs = deque((i, 0) for i in hospitalCities)
    ret = [-1 for _ in range(n)]
    while bfs:
        city, distance = bfs.popleft()
        if ret[city] != -1:
            continue
        ret[city] = distance

        for conn in graph.get(city, set()):
            bfs.append((conn, distance + 1))

    return ret


### tests
m = {0: set([1, 2]), \
     1: set([0]), \
     2: set([0, 3]), \
     3: set([2])}
print(nearestCityWithHospital(m, [0]))
print(nearestCityWithHospital(m, [2,3]))
print(nearestCityWithHospital(m, [1,3]))
print(nearestCityWithHospital(m, [0,1,2,3]))

Answer 3

C++ BFS

 

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

void solution(int n, int m, int l, vector<int> &A, vector<int> &B, vector<int> &H) {
    // 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);
    vector<int> reqTime(n, -1);
    queue<int> q;
    for (int &h : H) {
        q.push(h);
        reqTime[h] = 0;
        vis[h] = 1;
    }
    int ti = 0;
    while (!q.empty()) {
        int si = q.size();
        for (int i = 0; i < si; i++) {
            int f = q.front();
            q.pop();

            for (int x : g[f]) {
                if (!vis[x]) {
                    vis[x] = 1;
                    reqTime[x] = ti + 1;
                    q.push(x);
                }
            }
        }
        ti++;
    }

    for (int &i : reqTime) cout << i << ' ';
}

int32_t main() {
    int t = 1;
    cin >> t;
    while (t--) {
        // numNodes numEdges numHospitals
        int n, m, l;
        cin >> n >> m >> l;
        vector<int> A(m), B(m), H(l);
        for (int i = 0; i < m; i++)
            cin >> A[i];
        for (int i = 0; i < m; i++)
            cin >> B[i];
        for (int i = 0; i < l; i++)
            cin >> H[i];
        solution(n, m, l, A, B, H) ;
    }
    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

*/