Team Tournament
Updated
Problem statement
A tournament has n fighters labeled 1 to n. The organizer has a list of fights: fights[i] = [a, b] means fighter a fights fighter b. The fights must happen in the order they are listed. The same two fighters may fight more than once.
Before the first fight, every fighter is put on team RED or team BLUE. An assignment is good if every fight that takes place is between two fighters from different teams.
The fights go ahead in order for as long as possible. If adding the next fight would leave no good assignment for all the fights so far, the tournament stops before that fight.
Return the number of fights that take place. In other words, return the largest k such that some good assignment works for the first k fights.
Function
maxFights(n: int, fights: int[][]) → intExamples
Example 1
n = 3fights = [[1,2],[2,3],[3,1]]return = 2The first two fights can happen: put fighter 2 on RED and fighters 1 and 3 on BLUE.
The third fight is between 3 and 1. After the first two fights, 1 and 3 must both be on the team opposite to 2, so they are always on the same team. No good assignment allows all three fights, so the answer is 2.
Example 2
n = 4fights = [[1,2],[2,3],[3,4]]return = 3All three fights can happen: put fighters 1 and 3 on RED and fighters 2 and 4 on BLUE. The answer is 3.
Example 3
n = 6fights = [[1,2],[3,4],[1,3],[2,4],[5,6],[4,5],[6,1]]return = 6The first six fights can happen with RED = {1, 4, 6} and BLUE = {2, 3, 5}. Fights 1 to 4 form the loop 1 - 2 - 4 - 3 - 1, which has 4 fights; a loop with an even number of fights is fine.
The seventh fight is between 6 and 1. It would close the loop 1 - 3 - 4 - 5 - 6 - 1, which has 5 fights. Going around a loop the teams must alternate, and with an odd number of fights that is impossible. So the answer is 6.
Constraints
1 <= n <= 10^51 <= fights.length <= 5 * 10^4fights[i].length == 21 <= fights[i][0], fights[i][1] <= nfights[i][0] != fights[i][1]
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Visible Profiles CountMicrosoft · OAMicrosoft interview questions
- Get Node To RemoveSalesforce · OASalesforce interview questions
- Malware SpreadFlexport · OAFlexport interview questions
- Connected GroupsVisa · OAVisa interview questions
- Visible Profiles CountIBM · OAIBM interview questions
- Record Linkage Part 3 - Full Connected ComponentStripe · PHONE SCREENStripe interview questions
- Evaluate DivisionApple · PHONE SCREENApple interview questions
- Count Friend CirclesOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Count Connected Point ClustersGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Count the Number of Complete ComponentsAmazon · PHONE SCREEN