Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Is Graph Bipartite? (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 3 years ago

The solutions explanation would lead you to believe that you need only check if the two nodes connected by the edge belong to the same subset. If they do, the graph is not bipartite.

This is not correct though, as the code that matches this description fails. Then, looking at the solution code in python, you see some tricky stuff is happening with the first neighbor in the set of neighbors for each node. This is not explained at all in the solution. It's not clear how or why this code succeeds at detecting whether or not the graph is bipartite.

Show 2 replies

Reading Progress

0%

Vote for new content