Day 292

[vaskoz]

Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

A teacher must divide a class of students into two teams to play dodgeball. Unfortunately, not all the kids get along, and several refuse to be put on the same team as that of their enemies.

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]
}

[vaskoz]

My solution requires a connected graph. Otherwise, a deterministic answer isn't possible.

Take for example the following test case:

map[int]map[int]struct{}{
            0: {1: struct{}{}},
            1: {0: struct{}{}},
            3: {4: struct{}{}},
            4: {3: struct{}{}},
        },

There are 2 valid solutions: team1: [0, 3] team2: [1, 4] OR team1: [0, 4] team2: [1, 3] when deterministically sorting by the first ID. team1[0] < team2[0]