Vc
Это вопрос к Диме а не ко мне )
Size: a a a
2020 October 01
НП
for research purposes ofc
НП
Это вопрос к Диме а не ко мне )
продолжайте вести наблюдение...
om
Николай Панов
В яндекс не в такси случайно?
П росему Вы спрашиваете?
D
я приходил на собеседование в яндекс
решил им все задачи
а они мне мол "вы неправильно решили. Нужно было решать 1 в 1 как в олимпиадных задачках"
решил им все задачи
а они мне мол "вы неправильно решили. Нужно было решать 1 в 1 как в олимпиадных задачках"
ор
D
типа, берем 2 крайние точки по горизонтали
находим середину между ними
делаем второе множество точек, отраженных относительно этой оси
а потом что-то типа удаляем по две одинаковые точки из обоих множеств
находим середину между ними
делаем второе множество точек, отраженных относительно этой оси
а потом что-то типа удаляем по две одинаковые точки из обоих множеств
первая мысль была такая
IL
я приходил на собеседование в яндекс
решил им все задачи
а они мне мол "вы неправильно решили. Нужно было решать 1 в 1 как в олимпиадных задачках"
решил им все задачи
а они мне мол "вы неправильно решили. Нужно было решать 1 в 1 как в олимпиадных задачках"
а мне говорили я не аккуратно оформлял решение на листочке
IL
решили все, но не понравилось как вы писали код
IL
много зачеркиваний
IL
надо было сразу идеально
O
даётся множество точек на плоскости, нужно понять есть ли у него симметрия относительно какой-то вертикальной оси
Можно через хешмапу быстрее сортировки сделать
O
Посчитать середину по горизонтали, и добавлять точки x_y в таблицу. Но перед каждым добавлением проверять, есть ли в таблице (mid*2-x)_y, если есть - удалить и не добавлять. Если в конце не останется элементов, то отвечаем да
D
найти крайние точки
посчитать середину
сумму слева и справа
посчитать середину
сумму слева и справа
D
если совпадает, то проверить по высоте
D
хотя...
можно попутно отсортировать по удалённости от середины и потом убирать с одинаковой высотой, как зеркальные
можно попутно отсортировать по удалённости от середины и потом убирать с одинаковой высотой, как зеркальные
O
найти крайние точки
посчитать середину
сумму слева и справа
посчитать середину
сумму слева и справа
Крайние точки может быть дольше считать, среднее - это сумма всех деленая на количество, ну то бишь сложение в основном. А минимумы максимумы уже 2 ифа требуют
O
Сортировка - O(n*logn), в некоторых сортировках O(n^2) в худшем случае
Через хешмапы в среднем - O(n), в худшем случае - O(n^2)
Через хешмапы в среднем - O(n), в худшем случае - O(n^2)
2020 October 02
ЕЗ
Вот только константа хэшмап раз в 100 больше
DD
больше чего?
Vc
Больше константы не хэшмапы очевидно