## Problem Given a list of participants and an exclusion list (pairs who should not be matched, e.g., couples or family members), generate a valid Secret Santa assignment where every person gives to exactly one other person, receives from exactly one person, and no exclusion is violated. ```python from typing import Optional def secret_santa( participants: list[str], exclusions: list[tuple[str, str]] # (a, b) means a must not give to b ) -> Optional[dict[str, str]]: # {giver: receiver} or None if impossible pass ``` **Example:** ``` participants = ["Alice", "Bob", "Carol", "Dave"] exclusions = [("Alice", "Bob"), ("Bob", "Alice")] # couple secret_santa(participants, exclusions) # Valid: {"Alice": "Carol", "Bob": "Dave", "Carol": "Bob", "Dave": "Alice"} ``` ## Follow-ups 1. How do you model this as a graph problem (directed Hamilton cycle with forbidden edges)? 2. When is a valid assignment impossible? Give a minimal example. 3. How would you ensure the assignment is uniformly random among all valid assignments? 4. How would you scale this to 500 participants with complex exclusion rules?

InterviewDB Experience

Secret Santa: Assign Secret Santa Pairs with Exclusion Constraints Using Graph Matching

phone

Interview Experience

Problem Given a list of participants and an exclusion list (pairs who should not be matched, e.g., couples or family members), generate a valid Secret Santa assignment where every person gives to exactly one other person, receives from exactly one person, and no exclusion is violated. Example: Follow-ups How do you model this as a graph problem (directed Hamilton cycle with forbidden edges)? When is a valid assignment impossible? Give a minimal example. How would you ensure the assignment is uni…

Full Details

🔒

Unlock all Nextdoor 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 nextdoor interview during the phone round.

It covers the following topics: Coding, Graph, Phone, Onsite .

Topics

Coding Graph Phone Onsite

Secret Santa: Assign Secret Santa Pairs with Exclusion Constraints Using Graph Matching

Interview Experience

Full Details

About This Question

Topics

More Nextdoor Interview Questions