Google Interview Question Software Engineer / Developers
here's the explanation of the example given in the question
A-->B means A accuses B
here we go
Step--->Tom--->Gal|
^ ^^--------|
| |
Geo---->Iss
now take 2 colors eg)red,green
color any node as green eg)Step as Green
color the graph such that no neighbor of 'x' has same color as 'x'...so Tom is red,Gal is green,Geo is red,Iss is green...totally 3 greens and 2 reds
U should always be able to bicolor the graph cos the question says "everyone seems to be either unfailingly honest or compulsively deceptive"
Is it really a question taken on phone/onsite google interview? It looks like some programming contest (UVA, topcoder etc) question? Or, some written exam?
Would u mind to give reference to this question? Thanks.
public static String getLiarLiar()
{
HashSet<String> setOne = new HashSet<String>();
HashSet<String> setTwo = new HashSet<String>();
try
{
Scanner scan = new Scanner(new FileInputStream("liarliar.txt"));
int number = scan.nextInt();
for (int i =0; i<number;i++)
{
boolean snitchInSetOne = false;
boolean snitchInSetTwo = false;
String name = scan.next();
int tellNum = scan.nextInt();
HashSet<String> tellSet = new HashSet<String>(1);
tellSet.add(name);
if (setOne.contains(name)) // if teller is in setOne
{
snitchInSetTwo = true;
}
else if (setTwo.contains(name)) // if teller is in setTwo
{
snitchInSetOne = true;
}
HashSet<String> snitchSet = new HashSet<String>(tellNum);
for(int j=0;j<tellNum;j++)
{
String snitch = scan.next();
snitchSet.add(snitch);
if (setOne.contains(snitch))
{
snitchInSetOne = true;
}
else if (setTwo.contains(snitch))
{
snitchInSetTwo = true;
}
}
if (snitchInSetOne)
{
setOne.addAll(snitchSet);
setTwo.addAll(tellSet);
}
else if (snitchInSetTwo)
{
setOne.addAll(tellSet);
setTwo.addAll(snitchSet);
}
else // if it's all empty
{
setOne.addAll(tellSet);
setTwo.addAll(snitchSet);
}
}
}
catch (FileNotFoundException e)
{
e.printStackTrace();
}
return (setOne.size()>setTwo.size()) ? setOne.size()+" "+ setTwo.size():setTwo.size() +" "+setOne.size();
}
Draw a directed graph and bicolor it.members of same color hv same attitude
- Anonymous June 28, 2011