Question

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

Answer 1

Images of ques

Answer 2

BFS at each of the hospital?

 

 public static void main(String[] args) {
        int n = 6;
        int[] a = new int[]{0, 1, 1, 3, 0};
        int[] b = new int[]{1, 2, 3, 4, 5};
        int[] h = new int[]{2, 4};
        System.out.println(findMaxReachingTime(n, a, b, h));
    }

    private static int findMaxReachingTime(int n, int[] a, int[] b, int[] h) {
        int size = a.length;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < size; i++) {
            graph.computeIfAbsent(a[i], k -> new ArrayList<>()).add(b[i]);
            graph.computeIfAbsent(b[i], k -> new ArrayList<>()).add(a[i]);
        }

        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);

        for (int hostpital : h) {
            bfs(graph, hostpital, distances);
        }

        int maxTime = Integer.MIN_VALUE;
        for (int distance : distances) {
            maxTime = Math.max(maxTime, distance);
        }

        return maxTime == Integer.MAX_VALUE ? -1 : maxTime;
    }

    private static void bfs(Map<Integer, List<Integer>> graph, int hostpital, int[] distances) {
        Queue<Integer> q = new LinkedList<>();
        q.add(hostpital);
        int level = 0;
        Set<Integer> visited = new HashSet<>();
        while (!q.isEmpty()) {
            int currentSize = q.size();
            while (currentSize > 0) {
                int point = q.poll();
                visited.add(point);
                currentSize--;

                if (distances[point] > level) distances[point] = level;

                // visit neighbors
                List<Integer> connectDistricts = graph.get(point);
                if (!connectDistricts.isEmpty()) {
                    for (int district : connectDistricts) {
                        if (!visited.contains(district)) q.add(district);
                    }
                }
            }
            level++;
        }
    }

Answer 3

public class topologocal {
static List<List> g = new ArrayList<>();
static Stack st = new Stack<>();

public topologocal(int i) {
}


static void topologocalsort(List<List<Integer>> g, boolean vis[], int index) {
    List<Integer> list = g.get(index);
    vis[index] = true;
    for (int neigh : list) {
        if (vis[neigh] == false) {
            vis[index] = true;
            topologocalsort(g, vis, neigh);
        }
    }
    st.push(index);

}

static void add(int[] a, int b[]) {
    for (int i = 0; i < 6; i++) {
        g.add(new ArrayList<>());
    }
    for (int i = 0; i < a.length; i++) {
        g.get(a[i]).add(b[i]);
    }
}

static void buildGraph(int n) {
    boolean[] vis = new boolean[n];
    for (int i = 0; i < n; i++) {
        topologocalsort(g, vis, i);
    }
    while (!st.isEmpty()) {
        System.out.print(st.pop() + " ");
    }


}

public static void main(String[] args) {
    int n = 6;

    int[] a = new int[]{5, 5, 4, 4, 2, 3};
    int[] b = new int[]{2, 0, 0, 1, 3, 1};

    add(a, b);
    buildGraph(n);
}
}