## Problem You are hosting a party and have `n` potential guests numbered `1` to `n`. You are given a list of conflict pairs — two people who refuse to attend if the other is present. Find the maximum number of guests you can invite such that no conflict pair is both present. ```python def max_party_guests(n: int, conflicts: list[tuple[int, int]]) -> int: pass ``` ``` Input: n = 4, conflicts = [(1,2), (1,3), (2,4)] Output: 2 # e.g., invite {2,3} -> conflict (1,3)? No, 1 not invited. (2,4)? 4 not invited. # Actually {2,3} has no conflict -> valid, size 2 # Can we get 3? {1,4}: conflict (1,2)? 2 not there. (1,3)? 3 not there. -> valid! size 2+? # {1,4} = 2 guests; {2,3} = 2 guests; {3,4} = 2. Answer = 2 here? Check {1,4}: size 2. # If no constraints, answer is n. Input: n = 3, conflicts = [] Output: 3 ``` ## Follow-ups 1. Is this equivalent to Maximum Independent Set? What does that imply about complexity in general graphs? 2. If the conflict graph is bipartite, how can you find the exact answer efficiently? 3. For a general graph, what approximation strategies exist? 4. How would you extend this to weighted guests where you maximize total "importance" instead of count?

InterviewDB Experience

Party Invite: Maximum Guests Satisfying Friendship Constraints

phone

Interview Experience

Problem You are hosting a party and have n potential guests numbered 1 to n. You are given a list of conflict pairs — two people who refuse to attend if the other is present. Find the maximum number of guests you can invite such that no conflict pair is both present. Follow-ups Is this equivalent to Maximum Independent Set? What does that imply about complexity in general graphs? If the conflict graph is bipartite, how can you find the exact answer efficiently? For a general graph, what approxim…

Full Details

🔒

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

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

Topics

Coding Graph Phone Onsite

Party Invite: Maximum Guests Satisfying Friendship Constraints

Interview Experience

Full Details

About This Question

Topics

More Ziphq Interview Questions