Implement plurality and majority voting

Q: Implement plurality and majority voting

This question evaluates skills in frequency-based selection and majority detection, including handling tie-breaking rules and applying linear-time, constant-space algorithms such as the Boyer–Moore majority vote.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an array votes of length n, where each element is a candidate identifier (string or integer).

Implement two voting systems:

1) Plurality vote

Return the candidate with the highest number of votes.

If multiple candidates are tied for the highest count, return the lexicographically smallest candidate (if identifiers are strings) or the smallest numeric id (if integers).

2) Majority vote (Boyer–Moore)

Return the candidate who has strictly more than n/2 votes.

If no such candidate exists, return null (or None ).
This must be done in O(n) time and O(1) extra space (aside from the input), i.e., using the Boyer–Moore majority vote technique.

Input/Output

Input: votes: List[Candidate]
Output:
- pluralityWinner(votes) -> Candidate
- majorityWinner(votes) -> Candidate | null

Constraints

1 <= n <= 10^6
Candidate identifiers are comparable for tie-breaking.

Examples

votes = ["A", "B", "A", "C", "B", "A"]
- plurality winner: "A" (3 votes)
- majority winner: null (3 is not > 6/2)
votes = [2, 2, 1, 2]
- plurality winner: 2
- majority winner: 2 (3 > 4/2)