Очень популярная и простая задача с собеседования в Google

Задача. Дан массив длинны N, нужно найти элемент, который встречается больше чем N/2 раз. Он гарантированно есть.

Например: Для [2,2,1,1,1,2,2] это 2.

Решений у этой задачи очень много. Самое оптимальное - за O(N) по времени и за O(1) по памяти.