Katkat
Back

Implement Plurality and Runoff Voting

CourseraSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.
  1. 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.