The Bipartite Test

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Citadel

Problem

A scheduling conflict graph arrives as adj_list, where entry i lists the nodes that clash with node i, and the graph may be split into several unconnected pieces. Return whether the nodes can be divided into two groups so that no clash falls inside a group.

Can this crowd be split into two perfectly separated groups?

Example 1

Input:

adj_list = [[1,3],[0,2],[1,3],[0,2]]

Output:

true

Example 2

Input:

adj_list = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output:

false

Worked solution and explanation

What this really is

This is two-coloring dressed up as seating people who clash at opposite tables. Everyone gets the part where a neighbor goes on the other side. What separates candidates is remembering the graph can arrive in pieces: run one traversal from node 0, return its answer, and a triangle sitting in the second piece sails through as splittable. The one real conflict in the data gets approved.

Why nothing simpler works: whether node 7 may sit on side 0 depends on every node reachable from it. You cannot decide it from its own neighbor list, from degree counts, or from checking pairs. The sides have to be pushed outward through the graph until an edge closes a loop and either agrees or contradicts.

Building it

Step 1: Treat every unplaced node as a new piece

Keep a side dict that holds a node only once it has been placed. Walk every node index; if it is already in side, an earlier piece reached it, so continue. Otherwise it starts a new piece: place it on 0 and put the pair (start, 0) in a deque.

Step 2: Give each new neighbor the opposite side

Pop a (node, node_side) pair and compute opposite = 1 - node_side once, which flips 0 to 1 and 1 to 0. Every unplaced neighbor lands on opposite and joins the queue carrying that side with it. The discoverer decides, and the queue remembers what it decided.

Step 3: Fail on the first same-side edge

A neighbor that is already placed on node_side means an edge inside one group. Return False right there; nothing later can undo it. A self-loop lands in this branch on its first look, because the node is its own already-placed neighbor.

Queue-driven two-coloring over every piece
from collections import deque


def is_bipartite(adj_list: list) -> bool:
    side = {}
    for start in range(len(adj_list)):
        if start in side:
            continue
        side[start] = 0
        queue = deque([(start, 0)])
        while queue:
            node, node_side = queue.popleft()
            opposite = 1 - node_side
            for neighbor in adj_list[node]:
                if neighbor not in side:
                    side[neighbor] = opposite
                    queue.append((neighbor, opposite))
                elif side[neighbor] == node_side:
                    return False
    return True

side doubles as the visited set: a node is placed exactly once.

Single traversal from node 0
On [[1], [0], [3, 4], [2, 4], [2, 3]] it places nodes 0 and 1, never touches the triangle 2-3-4, and returns True.
Traversal from every unplaced node
The outer loop reaches node 2 still missing from side, starts a new piece, and the triangle forces a same-side edge: False.

Common follow-up questions