Construct a Possible Bipartition
Reported by candidates from Airbnb's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Airbnb OA from March 2021 hands you a graph problem in disguise. People are nodes, dislike pairs are edges, and you have to 2-color the whole thing. The twist is the output format. You don't just say yes or no, you build both groups and print them in a fixed string. If you're taking this in the next day or two, expect an adjacency list, a color array, and a traversal. StealthCoder sits invisibly on your screen as a safety net if the string formatting or the traversal logic goes blank mid-assessment.
The problem
There are n people numbered from 1 through n. Each pair [a, b] in dislikes means that people a and b must be placed in different groups. Construct two groups that contain every person exactly once and satisfy every dislike pair. Process people in increasing order. Whenever the next person is still unassigned, place that person in group 1 and color the entire connected component consistently. Sort both completed groups in increasing order. If a valid partition exists, return group1|group2, where each group is its comma-separated list of person IDs. An empty group is represented by an empty string. If no valid partition exists, return IMPOSSIBLE. Function bipartitionGroups(n: int, dislikes: int[][]) → String Examples Example 1 n = 4 dislikes = [[1,2],[1,3],[2,4]] return = "1,4|2,3" Starting from person 1 puts people 2 and 3 in the opposite group. Person 4 must then share group 1 with person 1. Example 2 n = 3 dislikes = [[1,2],[2,3],[1,3]] return = "IMPOSSIBLE" The three edges form an odd cycle, so two colors cannot satisfy every dislike pair. Example 3 n = 5 dislikes = [[1,2],[3,4]] return = "1,3,5|2,4" People 1, 3, and isolated person 5 seed their components in group 1; their constrained neighbors go to group 2. Constraints 1 <= n <= 2000. 0 <= dislikes.length <= 10000. Every pair contains two distinct values in [1, n]. No dislike pair is repeated.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The hinge is an adjacency list plus a color array, with BFS or DFS to color each component. Loop i from 1 to n. If i is uncolored, put it in group 1 and traverse, giving every neighbor the opposite color. If a neighbor already has the same color as the current node, return IMPOSSIBLE right away. That catches odd cycles. The spec fixes the seeding rule, so the output is deterministic: each component's smallest person lands in group 1. Don't improvise a different seeding order. Pitfalls: forgetting isolated people (they go to group 1), using recursion on 2000 nodes in a language with a shallow stack, and botching the format. Collect IDs by iterating 1 to n, so groups are already sorted. Join with commas, then add the pipe. An empty group is just an empty string. If you blank on any of it, StealthCoder is the hedge during the live OA.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Construct a Possible Bipartition cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as possible bipartition. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Airbnb's OA.
Airbnb reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Construct a Possible Bipartition FAQ
What's the trick in the Airbnb bipartition problem?+
It's bipartite graph coloring. Build an adjacency list from the dislikes, then BFS or DFS each unvisited person, alternating colors. If you ever hit a neighbor with the same color as the current node, the answer is IMPOSSIBLE. Otherwise you have your two groups.
How hard is this really?+
Medium. The algorithm is standard, and most candidates who've seen graph coloring solve it quickly. The friction is the output string: pipe separator, sorted IDs, empty group as an empty string, and the exact seeding rule that puts each new component's start in group 1.
Do I need to handle disconnected components?+
Yes. Loop over all people from 1 to n and start a fresh traversal whenever someone is uncolored. Isolated people with no dislikes also get seeded into group 1, which is why example 3 puts person 5 with 1 and 3.
BFS or DFS, which should I use?+
Either works. With n up to 2000, recursive DFS is usually fine, but BFS with a queue avoids any stack depth worry. Both run in O(n + edges), which is easily fast enough for 10000 dislike pairs.
How do I prepare for this in 48 hours?+
Write the bipartite check from scratch twice, once with BFS and once with DFS. Then practice the output formatting: build two lists in id order, join with commas, join groups with a pipe, and return IMPOSSIBLE on any conflict. Test an empty dislikes list and an odd cycle.