Micro-questions over the leader/majority module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The problem

1. What is a leader (majority element)?

Answer

A value appearing strictly more than times — an election candidate winning over 50%.

2. How many leaders can a sequence have, and why?

Answer

At most one. If two values each appeared more than half the time, their combined count would exceed 100% of the array length.

3. Name three real applications.

Answer

Distributed consensus (Raft leader election), data-stream majority detection without buffering, and sensor fusion consensus.


B. Brute force and sorting

4. Describe the brute force, and its cost.

Answer

For every candidate value, scan the whole array and count. candidates × elements = .

5. Where must a leader sit in the sorted array?

Answer

At the middle index A[n // 2] — a value occupying more than positions must cover the midpoint once values are packed together.

6. What is the cost of the sorting approach?

Answer

time, extra if you sort in place (or if you copy to avoid mutating the input).


C. Boyer-Moore voting

7. State the core insight.

Answer

If you remove any pair of two different values, the leader remains the leader of what is left. A matched pair contains at most one leader occurrence, so the leader’s proportion only grows.

8. Describe phase 1.

Answer

Keep a candidate and a count. If the count is 0, adopt the current value with count 1. If the value matches the candidate, increment. Otherwise decrement — cancelling one occurrence.

9. What is the cost?

Answer

time and space — one pass, two variables.

10. Trace it on [A,B,A,A,C,A,B,A,A].

Answer

Counts: 1, 0, 1, 2, 1, 2, 1, 2, 3. Candidate ends as A with count 3 — confirmed at 6/9 > 4.

11. What is phase 2, and is it optional?

Answer

Verification — a second pass counting the candidate’s actual occurrences. It is not optional.

12. Why is it mandatory?

Answer

Boyer-Moore always produces a candidate even when no majority element exists. Without the check you return a confident wrong answer.


D. Comparison

13. Give the three approaches with time and space.

Answer
ApproachTimeSpaceIdea
Brute forcerescan per candidate
Sort + middleleader lands at midpoint
Boyer-Moorepairwise cancellation

14. Why not just use a hash map counter?

Answer

It is also time but space. Boyer-Moore’s whole distinction is achieving it in constant space — which is what makes it viable on a stream.


E. Traps

15. Distinguish leader from mode.

Answer

A leader requires a strict majority (> 50%). The mode — most common element — might appear only 30% of the time and is not a leader.

16. Does Boyer-Moore only work on integers?

Answer

No — it works for any comparable type; it only ever tests equality.

17. Summarise the algorithm in one sentence.

Answer

Cancel unequal pairs as you sweep and whatever survives is the only possible majority — then verify it, because something always survives.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Algorithms