Одна задача
На днях услышал задачу из категории задач с собеседований.
Возникло ощущение, что где-то решал, но не могу вспомнить, где. Помню, что не решил. Когда услышал решение, понял, что нельзя просто так взять и придумать его.
Запишу сюда, может кому полезно будет. Ну и себе на заметку.
Задача в стиле Facebook/Google/Amazon/etc. Кажется, они любят подобные вещи спрашивать.
Дан массив из N чисел. Известно, что в нем строго больше половины элементов одинаковые. Надо найти, чему именно они равны за один проход по массиву с использованием дополнительной памяти константного размера.
Возникло ощущение, что где-то решал, но не могу вспомнить, где. Помню, что не решил. Когда услышал решение, понял, что нельзя просто так взять и придумать его.
Запишу сюда, может кому полезно будет. Ну и себе на заметку.
Задача в стиле Facebook/Google/Amazon/etc. Кажется, они любят подобные вещи спрашивать.
Дан массив из N чисел. Известно, что в нем строго больше половины элементов одинаковые. Надо найти, чему именно они равны за один проход по массиву с использованием дополнительной памяти константного размера.