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.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Coursera.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coursera during technical interviews.

Implement plurality and majority voting | Coursera Interview Question

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.

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)

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)

Implement plurality and majority voting

Quick Overview

1) Plurality vote

2) Majority vote (Boyer–Moore)

Input/Output

Constraints

Examples

Comments (0)

Implement plurality and majority voting

Quick Overview

1) Plurality vote

2) Majority vote (Boyer–Moore)

Input/Output

Constraints

Examples

Comments (0)