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
| Approach | Time | Space | Idea |
|---|---|---|---|
| Brute force | rescan per candidate | ||
| Sort + middle | leader lands at midpoint | ||
| Boyer-Moore | pairwise 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
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- The Leader Algorithm — the module
- Max Slice Algorithms — Question Bank — the other one-pass classic
Software engineering
Infrastructure & security
Computer science
Hardware & engineering