## Spotify Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````#!/usr/bin/python
"""
Solution is incorrect, just realized, if it branches two ways, it follow one path to it's end, and end... (I'm more awake now)

A Lazy Breadth Search approach, retests Nodes it came from. I think it can be improved a bit, just tired to review it A.T.M.
First time I've done anything graph related in python
"""

graph_true = {'A': ['B','D'],
'B': ['A','C'],
'C': ['B','D'],
'D': ['A','C','E'],
'E': ['F','B']}
def bipartite(graph = None,start = ''):
if not start:
return False
visited = {}
color = True
to_visit = list(start)
for i in xrange(len(graph)):
for node in to_visit:
if node in visited:
if visited[node] != color:
return False
else:
visited[node] = color
to_visit[:] = []
color = not color
to_visit.extend(graph[node])
if len(visited) < len(graph):
return False
return True

print bipartite(graph_true,'A')``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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.``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.