Practice/LinkedIn/Design an Algorithm to Elect a Restaurant for a Team Outing

Design an Algorithm to Elect a Restaurant for a Team Outing

CodingOptional

Problem

You're organizing a team outing and need to select a restaurant democratically. The team uses an instant runoff voting system where each member ranks all restaurant options in order of preference.

The algorithm works as follows:

1. Count how many ballots have each restaurant as their current top choice
2. If any restaurant has more than 50% of the first-choice votes, that restaurant wins
3. If no restaurant has a majority, identify the restaurant(s) with the fewest first-choice votes
4. Remove the restaurant with the lowest vote count from all ballots (if there's a tie for lowest, remove the one that comes first alphabetically)
5. Repeat the process with the updated ballots until a winner emerges

Your task is to implement this voting algorithm and return the winning restaurant.

Requirements

1. Process ballots using instant runoff voting methodology
2. Count first-choice votes in each round
3. Eliminate candidates with the fewest votes when no majority exists
4. Handle tie-breaking for elimination (choose alphabetically first candidate)
5. Return the restaurant that achieves more than 50% of votes

Constraints

• 1 ≤ number of ballots ≤ 1000
• 2 ≤ number of restaurants ≤ 50
• Each ballot contains all restaurants in ranked order (no duplicates)
• Restaurant names are non-empty strings
• There will always be a winner (at least one ballot exists)
• Time complexity: O(n * m²) where n is ballots and m is restaurants
• Space complexity: O(n * m)

Examples

Example 1:

Input: ballots = [['A', 'B', 'C'], ['A', 'B', 'C'], ['B', 'C', 'A'], ['B', 'A', 'C'], ['C', 'A', 'B']] Output: "A" Explanation: Round 1 - First choices: A=2, B=2, C=1 C has the fewest votes and is eliminated. Round 2 - Updated ballots after removing C: Ballot 1: [A, B], Ballot 2: [A, B], Ballot 3: [B, A], Ballot 4: [B, A], Ballot 5: [A, B] First choices: A=3, B=2 A has 3/5 = 60% of votes, which exceeds 50%. A wins!

Example 2:

Input: ballots = [['X', 'Y'], ['Y', 'X'], ['X', 'Y']] Output: "X" Explanation: Round 1 - First choices: X=2, Y=1 X has 2/3 = 66.7% of votes, which exceeds 50%. X wins immediately!

Example 3:

Input: ballots = [['P', 'Q', 'R'], ['Q', 'R', 'P'], ['R', 'P', 'Q']] Output: "P" Explanation: Round 1 - First choices: P=1, Q=1, R=1 No majority. P is eliminated (alphabetically first among tied). Round 2 - First choices: Q=1, R=2 R has 2/3 = 66.7%. However, we continue... Actually, R doesn't have majority yet. Q eliminated. Round 3 - Only R remains with all votes.