CareerCup

Construct a graph and see whether it is bipartite or not.

Let us say u represent a developer node by red color and tester by green color, walls as edges . If no two adjacent nodes have same color then Answer to the manager question is YES or else it is a NO

How it is yes in your example ? You cannot sit anybody in cubicle 2 as every cubicle is adjacent to it, then how will place them in cubicle 2 ?

this is typical two colors problem. You can start at any office with for example tester in it, then check all directly connect offices, if there is one that has tester, then report no. Otherwise, assign all the neighbor offices with mark developer, so on and forth. Time complexity is O(E), space complexity is O(V).

This is simply a 2 coloring theorem. A graph is 2 colorable if and only if it has no circuit of odd length. Finally if it is a tree it is obviously 2 colorable.

This is can be done in two ways:
1. Check if there is odd number of cycle. If it is then it is NO
2. If it is even number of cycle the print yes
3.If it doesn't contain cycle print yes.

-This is a bi-partite graph.

Second method:
DFS
Check if there is an edge from child to parent. If it is then check whether the parent is "Tester or Developer". If it is same as child then Print NO. Otherwise "Yes".

I don't know how to solve this, can anyone share the code and approach they used, Thanks.

can anyone share the code for this ?

Do we know how many offices is reserved for developers and testers?