## Linkedin Interview Question for Software Engineer / Developers

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

We can do this by marking each node with 0 or 1.The first one we mark with 1, then a node in his list of neighbours with 0, then a neighbour of the neighbour with 1 and so until we mark all the nodes(and return true) or we arrive in a node that is 0 and we want to mark it with 1 or viceversa (and we return false).

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

biparty graph = two coloring problem

DFS + coloring customization to implement it

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

public Boolean bipartite() {
Boolean flag = true;
for (Node u : graph.getNodes)
if(u.state == 0)
BDFS(u,1);// first vertex node
return flag;
}
public void Boolean BDFS(Node u,int c) {
u.state = c;
if (v.state == 0)
BDFS(v,-c);
else if(v.state == c) return false;

}

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

2 coloring..which is essentially the same solution mentioned by bog dan.cebere

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

geeksforgeeks.org/bipartite-graph/

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

This can be done using DFS. I'm not sure though if its the most efficient way.

``````// source: google
for all v in V do visited(v) = 0
for all v in V do if (visited(v)==0) DFS(v,0)

DFS(v,p) {
visited(v) = 1
part(v) = p
for all w in adj(v) do {
if (visited(w)==0) {
DFS(w,1-p)
} else {
if (part(v) == part(w)) print "graph not bipartite"
}
}
}``````

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.