Distance from every cell to the nearest taxi
A grid marks the cells where taxis are parked. Return, for every cell, the distance to the nearest taxi (moving up, down, left or right). Use a multi-source BFS and say why it beats a search from each cell.
Follow-up: taxis come online and go offline over time. How would you keep nearest-taxi answers current without recomputing everything, and how would that become a lookup service?
GoogleTechnical phone screenNo answer yet. Write the first one; the best answer gets endorsed.