Twitter: Dodgeball Team and Bipartite Graph

Problem:

Given an adjacency list of students and their enemies, write an algorithm that finds a satisfactory pair of teams, or returns False if none exists.

For example, given the following enemy graph you should return the teams {0, 1, 4, 5} and {2, 3}.

students = { 
0: [3],
1: [2],
2: [1, 4],
3: [0, 4, 5],
4: [2, 3],
5: [3]
}

On the other hand, given the input below, you should return False.

students = { 
0: [3],
1: [2],
2: [1, 3, 4],
3: [0, 2, 4, 5],
4: [2, 3], 5: [3]
}

Solution:

According to Wikipedia,

bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V.

Moreover, a standard theorem regarding bipartite graphs gives an immediate algorithm for bipartite-partitioning the graph, and also for finding whether such a partition exists

a bipartite graph is a graph that does not contain any odd-length cycles.

Note that the example 1 in the problem statement has no odd-length cycle, while example 2 has a single odd-length cycle: 2->3->4.

Here is one scheme for finding an odd-length cycle:

  1. Start with an arbitrary vertex, u. Randomly assign Team 1 to it.
  2. For every assigned vertex of the graph, iterate over its neighbors
  3. If a neighbor v of u is already assigned, and has opposite team number, keep it.
  4. If v has the same team number, we have found an odd-length cycle. Return False
  5. Otherwise, place v in the opposite team of u.

In this post, we are going to provide three implementations of this iterative strategy

  1. Using Breadth First Search (BFS)
  2. Using Depth First Search (DFS) implemented recursively
  3. Using Depth First Search (DFS) implemented iteratively

Preliminaries:

Breadth First Search (BFS):

  1. At every iteration, it pops a student-team pair from the front of the queue.
  2. For every neighbor of the popped student, it tries to assign the opposite team, and simply returns false if the assignment ends up in conflict.

Depth First Search (DFS) (recursive):

  1. We need an additional map discovered to update when we first visit the student_id.
  2. We always assign a color to a vertex before

Depth First Search (DFS) (iterative)

  1. A stack of Assignment structs which keep track of team assignments
  2. A stack to keep track of the current offset in the neighbor list of the current student.

Complexity:

Testing:

  1. No students
  2. A single pair of students, both enemies of each other
  3. All empty enemy lists
  4. Complex enemy lists (with or without odd length cycles

Originally published at https://cppcodingzen.com on September 13, 2020.

Solutions to programming interview questions at some of the top companies in the world: cppcodingzen.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store