## Mentor Graphics Interview Question for MTSs

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 4 vote

This is the problem of determining whether a graph is Bipartite or not and can be done using BFS on the graph.

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

plz xplain iitd !!!

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

There are 2 things to explain:

1) How is it equivalent to checking whether the graph is bipartite.
2) How to check if a graph is Bipartite.

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

unsolvable. have you heard of 4 color problem?

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

you sure ???

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

yes. color a K5, a complete graph with 5 vertices using only two colors such that no two neighbors share the same color?

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

There seems to be some confusion here. The 4-color theorem is about coloring of contiguous regions on a planar map and is not about coloring a vertex graph with arbitrary edges.

Graph coloring is not unsolvable, but NP-complete. However, it seems that this question is asking for a coloring *given* that the graph can be colored with only 2 colors. That is not NP-complete, and can be done with a simple BFS.

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

I dont know but interviewer asked me to tell first whether this is possible or not.
May be this is related to some well known Graph Theorem.I am all nill in that !

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

It is about a well-known theorem in graph theory. The theorem is that graph coloring is NP-complete. That doesn't mean it's impossible. It just means, in very rough and oversimplified terms, that no exact algorithms for solving this problem are known that are substantially more efficient than brute-force search. That doesn't even mean such algorithms don't exist, only that none are known right now.

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

I used the word unsolvable in the sense that not any graph can be colored using 2 colors only and since the question didn't mention that graph is bipartite I assumed the input can have any graph for example a complete graph with 1000 vertices.

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

Forget K5 or bipartite graphs, what about a single triangle.

Can we color it using two colors only such that no two adjacent nodes are same color ? :) :)

Minimum number of different colors to color a graph is known as Chromatic number problem. Minium is 4 in my opinion.

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

Now consider a three vertices... A , B , C

A --- > B
B ----> C
A -----> C

Now no cycle is formed.. how will you color it ?

Do we have to use Minimum spanning tree mechanism and then color the vertices ???

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

BFS with Node has 2 members: bool isVisited & enum Color (red or green)

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

0 represents RED & 1 represents GREEN;

c representc color. color[i]==0 indicates ith vertex is colored RED.

``````int colorGraph(G[][],int c,int source,int color[])
{
color[source]=c;

for each V adj to source
{
if(isColored(V)==c)
return 0;
if(colorGraph(G,1-c,V,color)==0) return 0;
}
return 1;
}``````

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

You're not checking for whether you're going down a path you've already colored.

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

we can color the graph using BFS and stop at any point if we find it's 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.