Question

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

Answer 1

Problem

 

There are n locations ( vertices ) in a city, which are connected through streets of length 1 ( edge length = 1 ). Some of the locations have petrol stations ( colored vertex ) while others don't. People at locations with no petrol stations, go to their closest petrol station. What is the maximum distance one may have to travel to find a petrol station?
Constraints: 1 <= no of location <= 10^5

 

My solution
I have been able to come up with a BFS approach, where I initialize the maximum distance for the non-petrol location to maxint, then I do a BFS from every petrol location and keep updating the distances of the non-petrol location.
However, I feel like there must be a more optimal solution to this problem.

 

I will really appreciate if you can share a better approach.

Answer 2

Put all (petrol pumps, distance) in queue where distance is 0
Also maintain a visited dict
Now while queue is not empty
You do do bfs one level only i.e. you mark node directly connected to petrol pump as distance 1 and add ((adjacent, 1)) to queue if not already visisted
Now you get queue of all nodes distance 1
You do it iterativelty, if there are n location you visit every node only once so it will be o(n)

Answer 3

For this graph problem:
1. may contain cycle
2. undirected
3. uniform edge weight 1

BF:
for every node:
    find the distance of nearest police station --- BFS
time: O(|V| * (|V|+|E|))
space: O(|V|)

Let's instead use BFS to start from police stations to label the level of all other nodes in the graph

BFS: multiple starting points v.s. traverse all nodes
remember to mark visited when generate a node (using edge) to queue
and return the final level to traverse all node

     p1                p2           P3
   /              \   /               /
  a              b                    c
   \               \ \                    \                     \
b(visited)   a c (visited)    b(visited)         d

example here, return 2

Time: O(|V| + |E|)
space: O(|V|) all nodes will be generated and put into our queue only once