Как тип данных координаты оси симметрии влияет на решение?

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

Это уточнение к задаче вида «есть ли у набора точек вертикальная ось симметрии». Интервьюер проверяет, заметите ли вы, что ось может лежать между целыми точками, и как уйдёте от дробей и сравнения чисел с плавающей точкой. Следом спрашивают, что изменится, если координаты придут дробными.

Как отвечать

Ось, если она есть, проходит посередине между крайними точками: x = (min_x + max_x) / 2. Для точек 1 и 4 это 2.5, то есть в целочисленной задаче появляется дробь.

• целые координаты: делить не нужно. Возьмите s = min_x + max_x и проверьте, что для каждой точки (x, y) в множестве есть (s - x, y). Всё остаётся в int, сравнение точное, решение за O(n) через set;
• переполнение: в Python его нет, int произвольной длины. В Java или C++ сумма двух больших int переполняется, там берут long, и это стоит сказать, если разговор про решение в общем виде;
• что даёт float: в Python 3 оператор / всегда возвращает float. На малых числах это сработает, 4.0 == 4 и хеши у них равны, но после 2**53 не все целые представимы точно, и проверка начинает врать;
• дробные координаты на входе: сравнивать через == и искать в set нельзя, 0.1 + 0.2 != 0.3. Варианты: math.isclose с допуском и сортировка вместо хеш-множества, приведение к сетке известной точности (умножить на 10**k и перейти к int) или fractions.Fraction для точной арифметики;
• Decimal: точен для десятичных данных, если создан из строки. Decimal(0.1) уже несёт двоичную погрешность, и работает он заметно медленнее.

Проговорите крайние случаи: повторяющиеся точки, точки на самой оси (отражаются в себя), одна точка или пустой набор.

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

Считают ось через /, а потом сравнивают float на равенство. На примерах из интервью проходит, на больших или дробных данных ломается.

Предлагают Decimal как универсальное средство. Он не спасает, если на вход уже пришёл float, и не заменяет правильную постановку.

Говорят, что int в Python заметно быстрее float. В CPython оба являются объектами, разница мала, а время съедают операции с множеством, а не арифметика.