Как учесть дублированные точки при проверке симметрии?

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

Умеете ли вы уточнить условие до того, как писать код. Классическая постановка: дан набор точек, нужно понять, есть ли вертикальная прямая, относительно которой он симметричен. Дубликаты здесь не мелочь, а развилка в условии, и следом обычно спрашивают про точки, лежащие на самой оси, и про сложность.

Как отвечать

Начните с вопроса интервьюеру: точки это множество или мультимножество? От ответа зависит решение.

• ось: если симметрия есть, прямая проходит через середину между крайними точками, x = (min_x + max_x) / 2. Дубликаты на минимум и максимум не влияют;
• без дробей: храните не саму ось, а s = min_x + max_x. Отражение точки (x, y) это (s-x, y), всё остаётся в целых числах;
• семантика множества: если повтор точки ничего не значит, сделайте set(points) и проверьте, что отражение каждой точки есть в множестве;
• семантика мультимножества: если каждая копия требует пары, сравните Counter(points) с Counter отражённых точек. Точка на оси отражается сама в себя и проходит проверку без особых веток;
• сложность: O(n) по времени и памяти против O(n log n) у варианта с сортировкой.

Разницу стоит показать на примере: для [(1, 1), (1, 1), (3, 1)] множество скажет «симметрично относительно x = 2», а подсчёт вхождений скажет «нет», потому что у второй копии (1, 1) пары нет. Если симметрия задана относительно диагонали y = x, логика та же, меняется только функция отражения: (y, x).

Для data-ml позиции уместно добавить, что в реальных данных координаты вещественные, и сравнивать их нужно после округления до допустимой точности, иначе шум измерений сломает любую проверку.

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

Молча делают set и не говорят, что тем самым выбрали трактовку задачи. Интервьюер часто ждёт именно этого уточнения.

Решают сортировкой и двумя указателями без предварительной обработки повторов. На дубликатах и на точках, лежащих на оси, указатели расходятся, и код выдаёт ложный ответ.

Считают ось делением пополам и сравнивают float напрямую. При дробных координатах отражение даёт хвосты вроде 0.30000000000000004, и точка не находится в множестве, хотя по смыслу она там есть.