Геометрия на собеседовании

Инженер Uber рассказал, что задача "найти ближайшего водителя" решается не поиском по всей БД, а Geohash lookup за O(1)-это геометрия, которая экономит миллисекунды для миллионов запросов в секунду.

• **Uber/Lyft:** Geohash или H3 для matching пассажир-водитель в реальном времени
• **Google Maps:** R-tree + Geohash для POI search, routing, area queries
• **LeetCode Hard:** задачи 84, 85, 218 (skyline), 149-геометрия обязательна
• **System Design:** Yelp/Foursquare nearby search-классический spatial index вопрос

Предварительные знания

• Geometry in Computer Science

Классические геометрические задачи

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

**Closest Pair of Points O(n log n):** - Divide & Conquer: делим на две половины, рекурсивно находим d_L и d_R - Полоса шириной 2·min(d_L, d_R): проверяем ≤7 соседей для каждой точки **Max Rectangle in Histogram O(n):** - Monotonic stack: для каждого столбца находим левую и правую границу **Minimum Enclosing Circle:** - Welzl O(n) рандомизированный-ожидаемое линейное время

Геопространственная индексация

Geohash, S2, H3-три системы пространственной индексации, которые используются в Uber, Google Maps, Airbnb. Понимание их устройства-обязательное требование для System Design интервью.

Geohash prefix = географический регион. Запрос "все рестораны в радиусе 1 км" = запрос по 8-9 соседних geohash ячеек в Redis/Elasticsearch.

Геометрия в System Design

В задачах System Design геометрические структуры данных решают проблемы масштабируемости: поиск ближайших объектов, геозоны, routing-всё это spatial queries.

**Типичные spatial queries:** - **Nearest neighbor:** k ближайших ресторанов/водителей - **Range query:** все объекты в радиусе R - **Geofence:** точка входит/выходит из зоны **Структуры данных:** - **R-tree:** стандарт в PostGIS, MySQL Spatial - **k-d tree:** эффективен для низких размерностей (2D, 3D) - **Quad-tree / Geohash:** иерархическое разбиение плоскости

Как думать геометрически на интервью

На FAANG-интервью ценится не знание формул, а умение свести задачу к геометрическому инсайту и объяснить его интервьюеру.

**Паттерны геометрических задач:** 1. **Сортировка + sweep line:** задачи на пересечения, площади 2. **Stack + монотонность:** max rectangle, largest rectangle in 2D 3. **Divide & Conquer:** closest pair, многоугольные запросы 4. **Hash по координатам:** задачи на решётку, collinear points **Вопросы при виде задачи:** - Есть ли монотонность? → stack/deque - Есть ли симметрия? → rotate/reflect - Можно ли свести к проекции? → 1D задача

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

• **Closest pair O(n log n):** D&C + полоса с ≤7 соседями-геометрический pigeonhole
• **Max rectangle O(n):** monotonic stack-инсайт из геометрии монотонных структур
• **Geohash/S2/H3:** строковый ключ пространственной ячейки → O(1) lookup
• **Паттерны интервью:** монотонность → stack; проекция → 1D; симметрия → rotate/reflect

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

Интервью геометрия объединяет все ранее изученные концепции:

• Геометрия в CS — Convex hull, Voronoi-алгоритмы из этого урока применяются в интервью
• Координатная геометрия — Slope hashing (LeetCode 149)-прямые в системе координат
• Площади и периметры — Shoelace для polygon area-классика алгоритмических задач

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

• Как объяснить алгоритм Closest Pair интервьюеру за 2 минуты, не теряя математической строгости?
• Какой тип spatial index выбрать для системы: много updates (водители двигаются) vs много reads (поиск ресторанов)?
• Как сформулировать задачу "найти все пересекающиеся прямоугольники" через sweep line + interval tree?

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

• la-04-lines-planes