## Problem You are given a list of `2n` players each with a skill rating. Split them into two teams of exactly `n` players such that the absolute difference in total skill between the two teams is minimized. Return the minimum possible difference. ```python def min_team_difference(ratings: list[int]) -> int: """len(ratings) is always even. Return min |sum(team1) - sum(team2)|.""" pass ``` ``` Input: ratings = [3, 1, 4, 2] Output: 0 # Team1=[3,2]=5, Team2=[1,4]=5 -> diff=0 Input: ratings = [1, 2, 3, 4, 5, 6] Output: 1 # Total=21, need each team close to 10.5 # Team1=[1,4,6]=11, Team2=[2,3,5]=10 -> diff=1 Input: ratings = [10, 1, 1, 1] Output: 7 # Team1=[10,1]=11, Team2=[1,1]=2 -> diff=9 # Team1=[1,1]=2, Team2=[10,1]=11 -> diff=9 # Optimal: same. ``` ## Follow-ups 1. Is this NP-hard in general? What constraint makes a DP solution tractable here? 2. Describe the DP state and transition for solving this exactly. 3. If teams don't have to be equal size, how does the problem simplify or change? 4. Extend: each player has two attributes (skill, cost) and you want to minimize skill difference subject to total cost <= budget.

InterviewDB Experience · Los Angeles

Team Split: Divide Players into Two Balanced Teams

Onsite

Interview Experience

Problem You are given a list of 2n players each with a skill rating. Split them into two teams of exactly n players such that the absolute difference in total skill between the two teams is minimized. Return the minimum possible difference. Follow-ups Is this NP-hard in general? What constraint makes a DP solution tractable here? Describe the DP state and transition for solving this exactly. If teams don't have to be equal size, how does the problem simplify or change? Extend: each player has tw…

Full Details

🔒

Unlock all Zoox questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a candidate experience report from a zoox interview during the onsite round.

It covers the following topics: Coding, Onsite, Dynamic Programming .

Topics

Coding Onsite Dynamic Programming

Team Split: Divide Players into Two Balanced Teams

Interview Experience

Full Details

About This Question

Topics

More Zoox Interview Questions