Facebook Interview Question: Given a bipartite graph, sepa... | Glassdoor

Interview Question

Software Engineer Intern Interview(Student Candidate)

Given a bipartite graph, separate the vertices into two


Interview Answer

1 Answer


im assume given an adjacency list
and non-directed graph

func bipGraph(adjList) {
 if(adjList.size == 0) return
  frontier = {adjList[0]}
  copyfrontier = frontier
  set1 ={curr}
  set2 = {}
  curr = [set1, set2]
  i = 1;
  while(frontier.size > 0 ) {
     for(item in copyfrontier) {
       for(neighbors in item) {
       delete item from adjList
       delete item from frontier
     copyfrontier = frontier
     i = (i+1)%2


//typed this up really fast, lemme know what errors and how to optimize this.... seems ridic slow

John on Oct 24, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.