Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Why do we need to check, paper marked as 1. rather than that i guess one has to check the paper marked 2 has X written on the back.
We have to check the 1 to make sure it doesn't have an X on the other side (as that would invalidate all X's having even numbers on the back). We don't have to check the 2, because it's an even number, so we either find an X and it still holds, or we find a Y and we don't learn anything.
The question is ambiguous. "To prove that a paper with the letter x contains an even number on the other side" could mean either to prove that one such paper exists, or to prove that all papers with an 'x' have an even number on the other side.
Actually I think you can check 2. If it contains Y on the back then 1 MUST contain X.
I think the minimum to prove is 1 because if you check 2 first and you get X then you got lucky and proved X has an even number. Likewise if you had checked X first and it had 2 on the back.
The question is to check if X has even numbers, not even numbers have X. so we should check if All X doesn't contain odd number. So X's and odd numbers, hence 2
I think it should be only 1.
check for X only , If it is written 2 then then condition is true . If any other numbe ris written then condition is false.
One need to check two conditions :
1) We first need to check whether the opposite of two is X only.
2) Then we need to make sure that on other side of 2 is X only.
We cant reduce it to one check since after either of above one condition we cant be sure of other conditions getting true automatically because that is not provided in the question
Think about it as if you are getting handed papers with only one side up showing...
You must iterate through all papers with either
1) a X facing up, so make sure 2 is on the other side; OR
2) a 1 facing up, so make sure the X is NOT on the other side
That would be fully sufficient because no other case invalidates the statement:
Ex. 2,Y-Don't care(Because we only care about Xs having 2s) Y-(2/1) Don't Care
Lets say the paper are lying in front of you in the following order :
- nivethavadivelu February 23, 2015X Y 1 2
You know that X,Y have some number written at the back and 1,2 have a letter.
You need to check a minimum of 2 conditions :
1) Check whether paper X has even number written on the back.
2) Check whether the paper marked 1 has Y written on the back.
With these cases, you can conclude that paper with X will have even number on the back.