Question

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

Answer 1

What is the best way to do these question?

 

Answer 2

Q1:

 

public int solution(int[] V, int[] A, int[] B) {
 int n = V.length;
 Set<Integer>[] outs = new Set[n];
 int[] ins = new int[n];
 int m = A.length;
 for(int i=0; i<m; i++) {
  if(outs[A[i]]==null) outs[A[i]] = new HashSet<>();
  outs[A[i]].add(B[i]);
  ins[B[i]]++;
 }
 Deque<Integer> dq = new ArrayDeque<>();
 PriorityQueue<Integer> pq = new PriorityQueue<>();
 for(int i=0; i<n; i++) {
  if(ins[i]>0) continue;
  dq.offer(i);
  pq.offer(V[i]);
  if(pq.size()>2) pq.poll();
 }
 int ans = pq.poll() + pq.poll();
 while(!dq.isEmpty()) {
  int poll = dq.poll();
  if(outs[poll]==null) continue;
  for(int out : outs[poll]) {
   ins[out]--;
   if(ins[out]==0) {
    pq.offer(V[out]+V[poll]);
    if(pq.size()>1) pq.poll();
   }
   ins[out]++;
  } 
 }
 ans = pq.isEmpty()? ans : Math.max(ans, pq.poll());
 return ans;
}

 

Q2: Multisource bfs. O(n)

 

For q2, start with a set of ambulance locations, let's call S. current_max = 0

 

1. for all locations is S, add their unvisited neighbours to temp_S. Mark those neighbours as visited. current_max += 1
2. S = temp_S
   Repeat step 1 and 2 until there are no unvisited nodes left(i.e, S becomes empty)
   return current_max

 

Complexity should be O(V+E)