Interview Question

Software Engineer Intern Interview(Student Candidate)

Given a bipartite graph, separate the vertices into two

  sets.
Answer

Interview Answer

1 Answer

0

im assume given an adjacency list
and non-directed graph
pseudocode:

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) {
        curr[i].add(neighbor)
        frontier.add(neighbor)
       }
       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.