Valid Lineup: Validate a Sports Lineup Against Position and Eligibility Constraints

Question

## Problem

A fantasy sports team has a lineup of `n` slots, each requiring a specific position (e.g., PG, SG, SF, PF, C, FLEX). Each player has one or more eligible positions. Determine whether a given player-to-slot assignment is valid, and if not, find if a valid assignment exists (using backtracking or bipartite matching).

```python
def is_valid_lineup(lineup: dict[str, str], players: dict[str, list[str]]) -> bool:
    # lineup = {slot: player_name}
    # players = {player_name: [eligible_positions]}
    # Each player used at most once; each slot filled exactly once
    pass

def find_valid_lineup(slots: list[str], players: dict[str, list[str]]) -> dict | None:
    # Return a valid assignment or None if impossible
    pass
```

**Example:**
```
slots = ["PG", "SG", "FLEX"]
players = {"CurryS": ["PG"], "ThompsonK": ["SG"], "PooleJ": ["SG","FLEX"]}
find_valid_lineup(slots, players)
-> {"PG": "CurryS", "SG": "ThompsonK", "FLEX": "PooleJ"}
```

## Follow-ups

1. This is a bipartite matching problem — describe the Hopcroft-Karp algorithm and its complexity.
2. If a slot can be filled by any of 3 position types (FLEX), how do you model that in the bipartite graph?
3. How does the problem change if you want to maximize total projected points across all valid lineups?
4. How would you use constraint propagation to prune the search space early?

Valid Lineup: Validate a Sports Lineup Against Position and Eligibility Constraints

Interview Experience

Full Details

About This Question

Topics

More Draftkings Interview Questions