How should I practice Instant-Runoff Voting Winner?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Wise onsite interview problems in FastPrep.

Is Instant-Runoff Voting Winner associated with Wise?

FastPrep tags this as a Wise onsite interview coding practice problem when the problem catalog has that company and stage context.

Instant-Runoff Voting Winner

Wise● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Source note: The task was to find the instant-runoff winner from ranked ballots, meaning the candidate who remains after the one with the fewest votes is dropped in each round. Follow-ups asked about a tie rule, keeping the ballots unchanged, representing candidates as an enum, and how the method scales when a very large file holds millions of ballots for 3 to 15 candidates.

The report does not give the tie rule, say whether every ballot ranks every candidate, or give limits. Here, a tie for the fewest votes removes the candidate listed last, every ballot ranks every candidate, a candidate with no votes counts as 0 and can be removed, and there are 1 to 6 candidates and 1 to 500 ballots. The enum, not-changing-the-ballots and scaling follow-ups are in the statement and editorial but are not judged.

The judged task matches the report at about 90%.

An election uses instant-runoff voting. You are given the list of candidates and a list of ballots. Each ballot ranks the candidates from most preferred to least preferred.

The count runs in rounds while more than one candidate is still in the race:

Each ballot gives one vote to its highest-ranked candidate who is still in the race.
The candidate with the fewest votes is removed. A candidate with no votes counts as having 0 votes.
If several candidates tie for the fewest votes, remove the one that appears last in candidates.

Return the name of the last candidate left.

Interviewer Follow-ups

Model the candidates as an enum.
Do not change the ballots while counting.
How would you scale this to 3 to 15 candidates and millions of ballots stored in a huge file that does not fit in memory?

These follow-ups are for discussion. The tests check only the returned winner.

Function

findRunoffWinner(candidates: String[], ballots: String[][]) → String

Examples

Example 1

candidates = ["Mickey","Donald","Pluto"]ballots = [["Mickey","Donald","Pluto"],["Mickey","Pluto","Donald"],["Donald","Mickey","Pluto"],["Donald","Pluto","Mickey"],["Pluto","Mickey","Donald"]]return = "Mickey"

Round 1 counts first choices: Mickey 2, Donald 2, Pluto 1. Pluto has the fewest votes and is removed. Round 2: the ballot that ranked Pluto first now counts for its next choice, Mickey. Mickey has 3 votes and Donald has 2, so Donald is removed. Mickey is the winner.

Example 2

candidates = ["Ann","Bob","Cy"]ballots = [["Ann","Bob","Cy"],["Bob","Ann","Cy"],["Cy","Ann","Bob"],["Cy","Bob","Ann"]]return = "Ann"

Round 1: Ann 1, Bob 1, Cy 2. Ann and Bob tie for the fewest votes. Bob is listed later in candidates, so Bob is removed. Round 2: Bob's ballot moves to its next choice, Ann. Ann 2, Cy 2. They tie again, and Cy is listed later, so Cy is removed. Ann wins.

Example 3

candidates = ["Ada","Eve"]ballots = [["Eve","Ada"]]return = "Eve"

Ada gets no first-choice votes, which is fewer than Eve's 1 vote, so Ada is removed and Eve wins. A candidate with zero votes still takes part in the count.

Constraints

1 <= candidates.length <= 6
Candidate names are different from each other. Each name is 1 to 8 English letters: an uppercase letter followed by lowercase letters.
1 <= ballots.length <= 500
Every ballot lists every candidate exactly once.