Preference List Majority Winner
Bloomberg LP● MediumNEW GRADPHONE SCREENProblem statement
Each row of preferences represents one voter and lists that voter's acceptable candidates from most preferred to least preferred.
Consider complete vote assignments in depth-first order: process voters from left to right, and for each voter try the candidates in that voter's listed order. A candidate wins an assignment when they receive strictly more than half of all votes.
Return the winner of the first assignment in this order that has a majority. Return -1 if no assignment can produce a majority.
Function
rankedChoiceWinner(preferences: int[][]) → intExamples
Example 1
preferences = [[1],[1],[2]]return = 1The only assignment gives candidate 1 two of the three votes, which is a strict majority.
Example 2
preferences = [[1],[1],[2],[2],[3,1]]return = 1The all-first-choice assignment has no majority. Trying the fifth voter's next choice gives candidate 1 three of five votes.
Example 3
preferences = [[1,2],[1,2],[2,1],[2,3],[3,1]]return = 1The first choices split 2-2-1. The earliest winning assignment keeps the first four choices and uses candidate 1 as the fifth voter's second choice.
Constraints
1 <= preferences.length <= 201 <= preferences[i].length <= 81 <= preferences[i][j] <= 1000000- Each voter's preference list contains distinct candidates.
- The product of all preference-list lengths is at most
1000000.