This is Google interview question I have faced.

Find the 3 closest police offices to each office in a city. You have a list of office lats & lons.
Follow up question, what if the list of offices growth up to millions.
Need to provide Time / Space complexity explanation