Computational Geometry на собеседовании

В Tesla на собеседовании на self-driving engineer L5 за час нужно решить 3 задачи: построить convex hull для bounding LiDAR-сканов, найти ближайшую машину в потоке точек, спроектировать point-in-polygon для определения текущего города. Знание sweep line, hull-алгоритмов и R-tree - это не академический декор, а ежедневный инструмент в robotics, GIS и computational geometry в проде.

• **Tesla Autopilot** строит выпуклую оболочку обнаруженных препятствий 30 раз в секунду для обхода ESC-системой управления
• **Uber H3** - геопространственный индекс для матчинга водителей и пассажиров; 1M запросов/сек на point-in-region
• **Google Maps** использует R-tree поверх 100M+ полигонов административных границ; запрос 'какой город' решается за миллисекунды

Sweep line на собеседовании

Интервью в Yandex Maps: 'Дано N отрезков на плоскости, найти все пересечения за O((N+K)log N), где K - число пересечений'. Кандидат без знания **sweep line** напишет наивный O(N^2). Кандидат с знанием за 10 минут опишет алгоритм Bentley-Ottmann: вертикальная линия движется слева направо, status-структура хранит активные отрезки, отсортированные по y; события - старт, конец, пересечение.

Sweep line - это **универсальный шаблон** для геометрических задач: 'обрабатывать события в порядке координаты, поддерживать структуру активных объектов'. Применяется к пересечению отрезков, нахождению ближайшей пары точек, построению Voronoi-диаграммы (Fortune), полигональной триангуляции.

**Шаблон ответа на собеседовании**: (1) Распознать паттерн 'все пары' / 'обрабатывать слева направо'. (2) Назвать алгоритм по имени (Bentley-Ottmann, Fortune). (3) Описать события и status-структуру. (4) Указать сложность с обоснованием.

Выпуклая оболочка

На собеседовании в Tesla на роль self-driving engineer задают: 'Дано облако точек LiDAR-сканера за один frame; постройте выпуклую оболочку, чтобы определить минимальную bounding область для obstacle avoidance'. **Convex hull** - один из самых частых вопросов в robotics, ML (Support Vector Machines), компьютерной графике (collision detection).

Два классических алгоритма за O(N log N): **Graham scan** (сортировка точек по углу относительно нижней точки, стек-проход с проверкой поворота) и **Andrew's monotone chain** (сортировка по x, проход в двух направлениях). Для output-sensitive вариантов есть **Chan's algorithm** за O(N log h), где h - число точек на оболочке.

**Cross product = ориентация поворота**: знак `cross(O, A, B)` определяет, поворачивает ли ломаная O-A-B налево (>0), направо (<0) или это коллинеарные точки (=0). Это фундамент почти любого 2D-алгоритма.

Ближайшая пара точек

На собеседовании в Facebook Friend Suggestions: 'Дано N локаций пользователей, найти ближайшую пару для уведомления о геолокации'. Наивно O(N^2). Классический ответ: **divide and conquer за O(N log N)**, описан Shamos и Hoey в 1975. Кандидат, который вспоминает этот алгоритм - сильный сигнал на senior+.

Алгоритм: (1) Отсортировать точки по x. (2) Разделить на половины. (3) Рекурсивно найти минимум в каждой половине = `d`. (4) Проверить полосу шириной `2d` вокруг разделяющей линии. Ключевое свойство: в полосе любая точка имеет не более 7 кандидатов на ближайшего соседа. (5) Объединить результаты.

**Альтернатива через KD-tree**: для динамического случая (точки добавляются/удаляются) KD-tree даёт O(log N) на nearest neighbor query, что лучше пересчёта divide-and-conquer. На собеседовании важно уметь выбирать структуру под use case.

Дизайн геометрического алгоритма

Финальный вопрос на собеседовании senior+: 'Спроектируйте систему, которая определяет, находится ли точка внутри полигона города. N полигонов (городов = 10^5), запросов - 10^6 в секунду.' Это не алгоритмический вопрос (knowing is half), а **дизайнерский**: выбор структуры данных, балансирование preprocessing vs query, учёт workload и SLO.

Подход: (1) Уточнить SLO - latency? throughput? точность? (2) Оценить data характеристики - простые многоугольники vs сложные? сколько вершин в среднем? (3) Выбрать индекс - R-tree для bbox-prefilter, потом point-in-polygon (ray casting за O(V) на полигон с V вершинами). (4) Обсудить shard-стратегию для распараллеливания.

**Ловушка собеседования**: не сразу выбирать алгоритм, а сначала задать вопросы про bounds. 'Какая средняя сложность полигонов? Распределены ли запросы равномерно? Нужна ли стрита точность или достаточно 99.9%?'.

Ключевые идеи

• **Sweep line** - универсальный шаблон для геометрии: события + status-структура, применим к 80% задач с парами / пересечениями
• **Convex hull** за O(N log N) через Graham scan или Andrew's monotone chain; cross product - основа всех проверок ориентации
• **Closest pair** через divide-and-conquer за O(N log N); ключевое свойство - 7 кандидатов в полосе шириной 2d
• **KD-tree / R-tree** для динамических NN-запросов: O(log N) query вместо пересчёта O(N log N)
• **Дизайн на собеседовании = задать вопросы про SLO/workload перед выбором алгоритма**; это главный senior-сигнал

Связанные темы

Возвращаясь к Tesla-интервью: знание sweep, hull и NN-алгоритмов - база, но senior-уровень про инженерный подход к выбору структуры под workload. Эта тема связана с:

• Геопространственные индексы (R-tree, geohash, H3) — В реальной системе геометрические алгоритмы оборачиваются в индекс; без него O(N log N) бесполезно при N=10^6
• Распределённое хранение — Geo-индексы шардятся по регионам для масштабирования; ключевое решение в системах типа Uber/Google Maps

Вопросы для размышления

• Sweep line за O(N log N) красив на доске, но кэш-неэффективен из-за random access в status. Когда наивный O(N^2) выигрывает на реальных данных из-за лучшей локальности?
• На собеседовании за 45 минут редко успевают реально написать sweep line с пересечениями. Что важнее: написать корректный код или объяснить архитектуру и trade-offs?
• ML-подходы (DeepHull, neural sorting networks) дают approximate convex hull быстрее классики на GPU. Меняет ли это набор обязательных знаний для интервью через 3-5 лет?

Связанные уроки

• cgeom-06 — Пересечение отрезков и выпуклая оболочка - топ задач на геом. интервью
• cgeom-11 — Триангуляция часто встречается как финальный вопрос на senior-позиции
• alg-22-backtracking — Некоторые геометрические задачи решаются через backtracking + pruning
• alg-01-big-o — Геометрические алгоритмы часто имеют нетривиальные временные сложности O(n log n)