Mentor Graphics Interview Question for MTSs


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.

- anujkaliaiitd July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

plz xplain iitd !!!

- softy July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anujkaliaiitd July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

unsolvable. have you heard of 4 color problem?

- Anonymous July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you sure ???

- softy July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 16, 2012 | Flag
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.

- eugene.yarovoi July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 !

- softy July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vifi October 18, 2014 | Flag
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 ???

- cobra July 15, 2012 | Flag Reply
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)

- Hayato July 15, 2012 | Flag Reply
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;
}

- Aashish July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi July 17, 2012 | Flag
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

- singhsourabh90 July 18, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More