Как посчитать выборку банкоматов с минимальным расстоянием, если ближайших может быть больше пяти

Что проверяют

Заметите ли вы подвох в формулировке: «пять ближайших» не определено, если на пятом месте стоят несколько банкоматов с одинаковым расстоянием. Второй слой: как считать расстояние на сфере и как не сортировать всю таблицу. Следом спрашивают, что делать, если банкоматов миллион.

Как отвечать

Сначала уточните требование: вернуть ровно пять с детерминированным разрывом ничьих (например, по id) или всех, чьё расстояние не больше расстояния пятого. Обычно имеют в виду второе.

Решение для списка в памяти:

• расстояние: координаты это широта и долгота, поэтому евклидова формула по градусам врёт. Нужна формула гаверсинусов, а на небольшой территории хватит плоского приближения с поправкой cos(lat) для долготы;
• отбор: вместо полной сортировки за O(n log n) держите PriorityQueue на пять элементов с максимумом в голове, это O(n log k);
• ничьи: после отбора возьмите расстояние пятого d5 и добавьте всех, у кого оно равно d5. Сравнивать double лучше после округления до метров, иначе «равные» точки разойдутся в последнем знаке;
• не портите вход: list.sort() меняет исходный список, а subList возвращает представление, а не копию.

В базе решение другое: PostgreSQL с PostGIS, индекс GiST и ORDER BY geom <-> point LIMIT 5, которое идёт по индексу. Ничьи закрываются через RANK() OVER (ORDER BY distance) и условие rank <= 5: RANK даёт равным строкам один номер, поэтому все ничьи на пятом месте попадут в выборку, а ROW_NUMBER отрезал бы их произвольно. Для огромных объёмов в памяти подойдут geohash или k-d дерево.

Где спотыкаются

Берут LIMIT 5 или subList(0, 5) и не замечают, что шестой банкомат на том же расстоянии отброшен случайно.

Считают Math.sqrt от разности градусов. Градус долготы в Москве почти вдвое короче градуса широты, и порядок ближайших меняется.

Считают расстояние внутри компаратора, пересчитывая его при каждом сравнении. Лучше посчитать один раз для каждого банкомата и сортировать пары.