Google Interview Question — LeetCode 1366

In this post, we are going to discuss leetcode 1366 — Rank Teams by Votes, which is recently asked in Google interviews.

Problem Analysis

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"] 
Output: "ACB" 
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team. Team B was ranked second by 2 voters and was ranked third by 3 voters. Team C was ranked second by 3 voters and was ranked third by 2 voters. As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"] 
Output: "XWYZ" 
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position.

This is an array problem, we simply need to define the sorting function to sort the array.

My Thinking Process

This is an array sorting problem, where we need to identify the sorting function.

According to the requirements, we need to sort base on the number of positions in each ranking first, then sort base on the name alphabetically.

What we can do is, we can create an array for each team. For example, assume we have 3 teams. For team A, we can have an array [2, 3, 0], which means team A got the first position 2 times, and the second positions 3 times. So we can sort the teams base on this array values.

Since we also need to sort alphabetically if two teams have identical rankings, then we can simply append the team name to the array to get [2, 3, 0, A], and we can compare the teams base on this array to sort.

Code Implementation

Base on the analysis above, below is my implementation of the problem.