Skip to content
Get started

What the majority vote returns when there is no majority

The Boyer-Moore majority vote keeps a candidate and a count: for each element, if count == 0 it sets candidate to that element and count = 1; otherwise it increments count when the element equals candidate and decrements it when it does not. It returns candidate without a second verification pass. Run it on

[4, 4, 1, 1, 6, 4, 6, 6, 1, 4, 8, 8, 3, 8, 8, 4, 4, 1, 3, 3]

(20 elements). Which value does it return?

Show hints (3)+
  1. Each decrement cancels one occurrence of the candidate against one different element.
  2. Whenever count hits 00 the next element becomes the candidate, whatever its overall frequency.
  3. Without a majority, the guarantee is void - just trace it.

Answer

Reveal answer →

3

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions