Spotify Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Algorithm:
• Run BFS search and colour all nodes in odd layers red, others blue
• Go through all edges in adjacency list and
check if each of them has two different
colours at its ends colours at its ends -if so then if so then G
is bipartite, otherwise it is not
You can implement it using BFS with an additional array colour[], When we add a node to layer L, than set colour[L]=red if L is even else set colour[L] = blue.
At the end of BFS, just scan all edges, if any edge has same colour than graph is bi-partite.
bool isbipartite(vector<vector<int>>& v) { // adjacency list
// suppose G is connected... :P
int n = v.size();
//vector<bool> visited(n, false);
vector<int> color(n, -1); // -1: not visted, valid colors: 0, 1
color[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()) { // invariant:bfs+ all the nodes were colored before putting them into the queue
int curr = q.front(); q.pop();
for (int j=0;j<v[curr].size();j++) {
if (color[v[curr][j]] == -1) {
color[v[curr][j]] = 1-color[curr];
q.push(v[curr][j]);
} else if (color[v[curr][j]] == color[curr]) {
return false;
}
}
}
return true;
}
- wingles.angel4 June 03, 2014