Microsoft OA 17-02-2025

Round 1

Questions:

1. Given N, A[], B[] and H[]

   • A[] = from/to district
   • B[] = from/to district
   • H[] = hospital district

   We have to return the max time it takes to reach the farthest district from any hospital; it takes 1 minute to cross one district. If a district is unreachable, then return -1.

   Example 1:

   N = 6
   A[] = [1,1,0,1,3]
   B[] = [2,0,5,3,4]
   H[] = [2,4]

   Output = 4 (since from 2 or 4, the farthest is 5 which has max distance as 4)

   

   Example 2:

   N = 6
   A[] = [1,1,2,3,3,5]
   B[] = [6,2,3,4,5,6]
   H[] = [1,4]

   Output = 2 (since from 1 or 4, the farthest is 5 which has max distance as 2)

   

   Example 3:

   N = 6
   A[] = [1,2,3,3]
   B[] = [2,3,4,5]
   H[] = [1,4]

   Output = -1 (since from any hospital we cannot reach 6)

   

   Example 4:

   N = 3
   A[] = [1]
   B[] = [2]
   H[] = [1,2,3]

   Output = 0 (since every district is a hospital)

   

2. Given 2 strings

   s1 = ".xxx...x"
   s2 = "..x.xxxx"

   The string represents a road with "." as smooth and "x" as potholes. We have to fix the potholes so we need to block some part of the road. But the road must be open in such a way that passengers can pass from left to right.

   Example 1:

   s1 = "..xx.x."
   s2 = "x.x.x..."

   Output = 4 (since if we use the shown path then 4 potholes can be fixed)

   

   Example 2:

   s1 = ".xxx...x"
   s2 = "..x.xxxx"

   Output = 6 (since if we use the shown path then 6 potholes can be fixed)

   

   Example 3:

   s1 = "xxxxx"
   s2 = "..x.."

   Output = 5 (since if we use the shown path then 5 potholes can be fixed)

   

I was able to solve both, but the verdict is yet to come.