Meta Interview Question
given the utitlies getFriend(User u) and areFriends(User u1, User u2), write the function which takes as parameter the array of users and return a bool saying if you can divide the users in 2 groups s.t. if u1 and u2 both belong to a certain group, they are not friends.
Interview Answers
I guess the more relevant question then becomes how do you construct the bipartite graph given this information efficiently..?
First you build an undirected graph in which users are vertex and friendships are edges.
After that you just have to say if the graph is bipartite.
Is quite easy actually, a graph is bipartite if and only if it has not odd length cycles.
http://en.wikipedia.org/wiki/Bipartite_graph
A bibartite graph is something else. It means that every edge connects a vertex from group a with a vertex from group b. I think the problem here is far more simple. I would solve it by just using BFS or DFS checking if every vertex is reachable from any start vertex.
http://en.wikipedia.org/wiki/Connected_graph