Хватит бояться собеседований в Яндекс - разнос алгосекции. Ось симметрии и множества.

Сегодня мы разберем классическую задачу с собеседования в Яндекс на позицию аналитика/ML-инженера. Мне ее давали и в Яндекс, и в несколько других компаний. Короче, задача смак - пугает незнающих и не пугает знающих. Поехали!

Условие задачи

Дано n точек на плоскости с целыми координатами, по модулю не превосходящие 10^9. Необходимо проверить, существует ли у данных точек вертикальная ось симметрии.

Например, у набора точек (0, 0), (2, 0), (-1, 3), (3, 3), (1, 1) такая ось есть, в x=1, что можно заметить по картинке.

Красивая картинка

Идея 1: кандидат на ось симметрии

Что мы точно знаем про вертикальную ось симметрии?

Очевидно, что самая левая точка (на картинке - C) и самая правая точка (на картинке - D) будут относительно этой оси по координате x симметричны.

Тогда мы можем точно найти ось симметрии, если она есть - взять среднее арифметическое x координат крайних точек.

Код на python с нахождением кандидата за 1 проход

Идея 2: проверка симметрии

Теперь, когда у нас есть кандидат на ось симметрии, достаточно проверить что все точки находят себе пару.

Мы можем отзеркалить все точки справа от оси симметрии, и они должны идеально наложиться на точки слева.

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

Идея 3: структуры данных - наш друг

Есть ли какая-то структура данных, которая помогла бы нам ускорить проверку? Да, есть! Это множества (set) либо же словари (dict, map в зависимости от используемого языка).

Для этих структур данных проверка вхождения элемента осуществляется за константное время, добавление элемента - также за константное время в среднем.

Важно на собеседовании сказать, что это время в среднем, так как иногда множеству необходимо расширять свое внутреннее хранилище и перехешировать все хранящиеся в нем ключи, но так как это происходит достаточно редко, в среднем каждое добавление дает константное время.

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

Простейшая реализация - ничего лишнего.

Полный код

За это вам дадут миска риса и один робот-доставщик жена

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