Distance to the Nearest Taxi on a City Grid

Asked at Google · Coding Questions · Difficulty: Medium

A ride-hailing service models a city as a grid of blocks. Some blocks hold an idle taxi, some are buildings that cannot be driven through, and the rest are open street. For dispatch, the service needs to know, for every block, how many moves the closest taxi needs to reach it. Compute that distance for the whole grid at once.

Loading the problem…