Как эффективно реализовать проверку симметрии без сортировки?

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

Обычно это продолжение задачи о симметрии набора точек относительно вертикальной прямой: первое решение сортирует точки и сравнивает края, а интервьюер просит уйти от O(n log n). Проверяют, догадаетесь ли вы найти ось заранее и заменить сортировку множеством. Следом спрашивают про дубли и про дробную ось.

Как отвечать

Сначала уточните, что именно должно быть симметричным. Если речь о палиндроме в массиве, сортировка там не нужна вовсе, хватает двух указателей с концов. Если о бинарном дереве, сравнивайте left одного поддерева с right другого; рекурсия в Python упирается в лимит глубины около 1000, поэтому на вырожденном дереве лучше итеративный обход с очередью.

Для точек ось находится за один проход: она обязана лежать посередине между крайними точками, (min_x + max_x) / 2. Чтобы не связываться с дробями, работайте с удвоенной осью s = min_x + max_x: зеркало точки (x, y) это (s-x, y).

def is_reflected(points):
    if not points:
        return True
    s = min(x for x, _ in points) + max(x for x, _ in points)
    seen = set(map(tuple, points))
    return all((s-x, y) in seen for x, y in seen)

Время O(n), память O(n). Проход идёт по seen, а не по исходному списку, чтобы повторяющиеся точки не проверялись заново. Если по условию дубли должны иметь пару в том же количестве, замените set на Counter и сравнивайте счётчики.

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

Решают не ту задачу. Не уточнив условие, пишут проверку симметричного дерева, хотя спрашивали про точки или массив, и тратят половину времени впустую.

Ищут ось как среднее всех x. Оно совпадает с осью, только если у каждой точки ровно одна пара: дубли сдвигают среднее, и симметричный набор объявляется несимметричным.

Делят сумму на 2 и переходят во float там, где координаты целые. На очень больших значениях float теряет точность, и проверка in seen начинает промахиваться; удвоенная ось держит всё в целых числах.