How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard 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 Runoff Voting | Coursera Coding Question

Quick Overview

This question evaluates understanding of voting algorithms, tie-breaking rules, ballot processing, and correctness under edge cases such as incomplete or exhausted ballots, and is commonly asked to assess algorithmic implementation, state simulation, and careful handling of corner cases in interview settings.

Implement Plurality and Runoff Voting

Company: Coursera

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a list of ballots for an election. Each ballot is an ordered list of distinct candidate names, from highest preference to lowest preference. Ballots may rank all candidates or only a subset of them. Implement logic for the following two tasks: 1. **Simple plurality winner** - Count only the first-ranked candidate on each non-empty ballot. - Return the candidate with the highest number of such votes. - If multiple candidates are tied for the highest count, return the lexicographically smallest candidate name. 2. **Instant-runoff winner** - Start with all candidates active. - In each round, every ballot contributes one vote to its highest-ranked candidate who is still active. - If a ballot has no remaining active candidate, it contributes no vote in that round. - If any candidate receives strictly more than 50% of the votes from non-exhausted ballots in the current round, that candidate wins. - Otherwise, eliminate the candidate with the fewest votes in that round. - If multiple candidates are tied for the fewest votes, eliminate the lexicographically largest candidate among them. - Repeat until a winner is found or only one active candidate remains. Pay close attention to edge cases such as complete ties in a round, repeated ties across multiple rounds, incomplete ballots, and ballots that must skip over several eliminated candidates before contributing a vote.

Quick Answer: This question evaluates understanding of voting algorithms, tie-breaking rules, ballot processing, and correctness under edge cases such as incomplete or exhausted ballots, and is commonly asked to assess algorithmic implementation, state simulation, and careful handling of corner cases in interview settings.

Part 1: Simple Plurality Winner

You are given election ballots. Each ballot is an ordered list of distinct candidate names from highest preference to lowest preference, and a ballot may be empty or may rank only some candidates. For this task, only the first-ranked candidate on each non-empty ballot matters. Count those first-place votes and return the candidate with the highest total. If multiple candidates are tied for the highest count, return the lexicographically smallest candidate name. If there are no non-empty ballots, return an empty string.

Constraints

0 <= len(ballots) <= 10^4
Each ballot contains distinct candidate names.
Candidate names are non-empty strings and are compared using normal lexicographic string order.
Ballots may rank all candidates or only a subset.

Examples

Input: [['Alice', 'Bob'], ['Bob', 'Alice'], ['Alice'], []]

Expected Output: "Alice"

Explanation: Only first choices count: Alice gets 2 votes, Bob gets 1.

Input: [['Bob'], ['Alice'], ['Bob', 'Carol'], ['Alice', 'Bob']]

Expected Output: "Alice"

Explanation: Alice and Bob each get 2 first-place votes, so return the lexicographically smaller name.

Input: [[], [], []]

Expected Output: ""

Explanation: No non-empty ballot contributes a vote.

Input: [['Zoe', 'Yan', 'Xena']]

Expected Output: "Zoe"

Explanation: A single non-empty ballot gives Zoe the win.

Hints

You only need to inspect ballot[0] for each non-empty ballot.
After counting first-place votes, find the maximum count and break ties with the lexicographically smallest name.

Part 2: Instant-Runoff Winner

You are given election ballots. Each ballot is an ordered list of distinct candidate names from highest preference to lowest preference, and a ballot may be empty or may rank only some candidates. Compute the winner using instant-runoff voting. Start with all candidates that appear anywhere on any ballot as active. In each round, every ballot contributes one vote to its highest-ranked active candidate. If a ballot has no active candidate left, it is exhausted and contributes no vote that round. If any candidate receives strictly more than 50% of the votes from non-exhausted ballots, that candidate wins immediately. Otherwise, eliminate the active candidate with the fewest votes in that round. If several candidates are tied for the fewest votes, eliminate the lexicographically largest candidate among them. Repeat until a winner is found or only one active candidate remains. If no candidate appears on any ballot, return an empty string.

Constraints

0 <= len(ballots) <= 2000
The total number of ranked names across all ballots is at most 20000.
Each ballot contains distinct candidate names.
Candidate names are non-empty strings and are compared using normal lexicographic string order.

Examples

Input: [['Alice', 'Bob', 'Carol'], ['Bob', 'Carol', 'Alice'], ['Carol', 'Alice', 'Bob'], ['Carol', 'Bob', 'Alice']]

Expected Output: "Carol"

Explanation: Round 1: Alice 1, Bob 1, Carol 2. Bob is eliminated by the tie rule with Alice. Round 2: Carol receives 3 of 4 active votes and wins.

Input: [['Ann'], ['Bob'], ['Cal']]

Expected Output: "Ann"

Explanation: All three tie in round 1, so eliminate the lexicographically largest: Cal. Then Ann and Bob tie, so eliminate Bob. Ann is the last active candidate.

Input: [['A', 'C'], ['B'], ['C', 'A'], ['C'], []]

Expected Output: "C"

Explanation: Round 1: A 1, B 1, C 2. B is eliminated. In round 2, B's ballot is exhausted, and C gets 2 of 3 non-exhausted votes, which is a strict majority.

Input: [[], []]

Expected Output: ""

Explanation: No candidate appears on any ballot.

Input: [['D', 'C', 'B', 'A'], ['C', 'A'], ['B', 'A'], ['A']]

Expected Output: "A"

Explanation: This case forces ballots to skip over several eliminated candidates across multiple rounds before a winner remains.

Hints

In each round, scan each ballot from left to right until you find the first candidate who is still active.
Be careful that the majority threshold is based only on non-exhausted ballots, and candidates with 0 votes can still be eliminated.

Quick Overview