Katkat
Back

Rank Teams from Ballot Preferences

NetappSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manage multi-level sorting criteria by implementing custom comparison logic for an array of preference rankings.

Rank Teams from Ballot Preferences

Given a list of ballots where each ballot is a list of team IDs representing a voter's ranked preference (from most preferred to least preferred), rank all teams based on the following criteria:

  1. Rank Frequency: A team is ranked higher if they appear in more ballots at the 1st position. If tied, compare the counts at the 2nd position, then the 3rd, and so on.
  2. Lexicographical Tie-break: If two teams have identical counts across all ranking positions, the team with the lexicographically smaller ID wins.

Function Signature

def rank_teams(ballots: List[List[str]]) -> List[str]

Constraints

  • Each ballot contains the same set of N unique teams.
  • The number of teams N is between 1 and 26.
  • The number of ballots is between 1 and 1000.

Examples

Example 1: Input: ballots = [["A", "B", "C"], ["A", "C", "B"], ["B", "A", "C"]] Output: ["A", "B", "C"] Explanation:

  • Team A: 2 first-place votes, 1 second-place vote.
  • Team B: 1 first-place vote, 1 second-place vote, 1 third-place vote.
  • Team C: 0 first-place votes, 1 second-place vote, 2 third-place votes.
  • A beats B, B beats C.

Example 2: Input: ballots = [["Z", "X"], ["X", "Z"]] Output: ["X", "Z"] Explanation: Both teams have one 1st-place vote and one 2nd-place vote. "X" comes before "Z" alphabetically.

Edge Cases

  • Single ballot.
  • All teams having identical preference distributions across all ranks.

Hints

Hint 1

Create a frequency table (like a dictionary or map) where the key is the team ID and the value is an array of size N representing the count of votes at each rank index.

Hint 2

When sorting the list of team IDs, use a custom comparator that iterates through the rank frequency arrays to determine order.

Hint 3

If the frequency arrays are identical for two teams, fallback to comparing the string IDs directly.

Follow-up questions

  • How would you modify your approach if some ballots are incomplete (i.e., not every ballot contains all teams)?
  • What is the time complexity of your solution in terms of B (number of ballots) and N (number of teams)?
  • If the number of teams N was very large (e.g., 10,000), how would you optimize the memory usage for storing rank counts?