Google Interview Question: Given a graph as input, write... |

Interview Question

Software Engineer Interview New Haven, CT (US)

Given a graph as input, write a java method returning

  boolean true if the graph is bipartitie, else false.

Interview Answer

1 Answer


iterate through all vertices, coloring each vertex one color, all of its neighbors an alternate color, and all the neighbors of those neighbors the initial color. upon completion, re-iterate through the graph and return false if any vertex has a neighbor of the same color. if re-iteration goes to completion, return true.

Interview Candidate on 29 Sep 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.