Алгоритмы и структуры данных46Симметрия точек относительно вертикальной прямой

Прогресс0/166

01Массивы и слайсы

02Основы Go: типы, строки, структуры, generics

03Ошибки, defer, panic/recover

04Map

05Каналы и select

06Синхронизация: sync, atomic, data race

07Context

08Алгоритмы и структуры данных

09Паттерны конкурентности и лайвкодинг

10NoSQL и кеширование

11Архитектура, ООП, SOLID, паттерны

12Брокеры сообщений: Kafka, RabbitMQ, NATS

13Сеть и API: HTTP, gRPC, REST

Тренажёр166 задач⌘↵

Перейти к редактору ↓

Симметрия точек относительно вертикальной прямой

Дан набор точек с целочисленными координатами (x, y). Определите, существует ли вертикальная прямая x = c, относительно которой набор симметричен: каждой точке соответствует её зеркальное отражение.

Точки могут повторяться, и повторы считаются: если точка (5, 0) есть дважды, то и её отражение должно быть дважды. Точка на самой прямой — сама себе отражение.

// IsReflected сообщает, симметричен ли набор точек относительно
// некоторой вертикальной прямой.
func IsReflected(points [][2]int) bool

Примеры

[[5,0],[5,0],[6,1],[7,2],[8,1],[9,0],[9,0]] → true   (прямая x = 7)
[[5,0],[5,0],[6,1],[7,2],[8,1],[9,0]]       → false  ((5,0) дважды, (9,0) один раз)
[]                                          → true
[[6,0]]                                     → true
[[5,0],[16,1]]                              → false
[[5,0],[6,0],[8,0]]                         → false

Ограничения

0 ≤ len(points) ≤ 2·10⁵, |x|, |y| ≤ 10⁹. Прямая может проходить через полуцелую координату (x = 6.5).
Ожидается O(n) в среднем. Проверка каждой точки перебором всех остальных — O(n²) — не проходит.

Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.

Подсказки0/3

Сначала попробуй сам — подсказки не дают готовый ответ.

go test -race

solution.go

Загрузка редактора…

go test -race ./...Готов к запуску

Запусти тесты, чтобы увидеть вывод

Запусти тесты, чтобы увидеть вывод · ⌘↵

График