techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

An interesting puzzle

Suppose there are n processors. at least half of them are not faulty and others are faulty. U can ask each processor a single question that whether another processor is faulty or not faulty. If it is faulty, it will give wrong answer (describe a correct one as incorrect and vice-versa) else a correct answer. Can you, asking (n-2) questions, find out a processor which is not faulty?

With the method I did it, it appears that if n is even, (n-2) questions are enough but if n is odd we need to ask (n-1) questions.

I am looking forward to a solution or a comment on the question.
sagsriv Send private email
Saturday, September 20, 2008
 
 
Hint: the processor that is known to be correct after n-2 questions might not have been involved in any question.
d
Saturday, September 20, 2008
 
 
Also, a note to others reading this problem: a /strict/ majority of non-faulty processors is required to obtain a correct answer, no matter how many questions are asked.
d
Saturday, September 20, 2008
 
 
d, it seems that you know the puzzle. can you just tell me that should n be even to get the answer in (n-2) questions?
sagsriv Send private email
Sunday, September 21, 2008
 
 
I can find a good processor among 3 by asking 1 question

I have serious problems finding a good processor among 4 by asking 2 questions without assumption, that there is a strict majority of good processors.
Maciek
Sunday, September 21, 2008
 
 
sagsriv,

Only (n-2) questions are required, regardless of n.
d
Sunday, September 21, 2008
 
 
Actually, (n-3) questions suffice when n is even. Working out examples where n is small gives a lot of insight into the question.
d
Sunday, September 21, 2008
 
 
>Actually, (n-3) questions suffice when n is even. Working out examples where n is small gives a lot of insight into the question.

unless n = 2 :)
Brian
Monday, September 22, 2008
 
 
n=2 is ruled out by the statement "more than half are not faulty"
NutCase
Monday, September 22, 2008
 
 
Brian ... can you explain how to find out the right processor in group of four (n = 4) after asking only one question (as you mention if N is even then N-3 question are sufficient) ???
gUn0m
Tuesday, September 23, 2008
 
 
Not quite nutcase if less than half are faulty that doesn't rule out 1 or 2 as numbers of chips as obviously none are faulty meaning n-2 questions is valid in the case of n=2(easy all good) but not if n=1 because you can't ask a negative number of questions.

gUn0m I was quoting Mr. D above me. So far I have only been able to get as far as the original poster. n-1 for odd n-2 for even.

take the case where n = 3 after one question you end up with
state of chip asked, state of chip asked about, and answer given
0 0 1
0 1 0
1 0 0
1 1 1

so if the chip you ask says it is faulty then you know one of the chips is faulty but you don't know which one it is and must ask another chip to narrow it down.
Brian
Tuesday, September 23, 2008
 
 
(The problem is to find a processor that's not faulty, not to diagnose the fault.)
d
Tuesday, September 23, 2008
 
 
Ah I see what you are saying since we only have to find a non faulty processor after the first question in n = 3 you either have two good processors or you know the third processor is good.
Brian
Wednesday, September 24, 2008
 
 
When n is even, it's impossible. See n=2, you must ask no question to find the correct one.
ghy Send private email
Saturday, September 27, 2008
 
 
When n=2, both processors are good, since 1 is not a strict majority. Therefore any choice is valid and no questions are required.
d
Saturday, September 27, 2008
 
 
1. If a strict majority is not required then a non-faulty processor cannot (always) be identified with certainty, no matter how many queries are made.  To see this, suppose exactly half of the processors are faulty, yet a putative algorithm identifies a non-faulty processor x.  Now suppose the roles of all processors are reversed (i.e., faulty become non-faulty and vice versa).  Then half of the processors are again faulty, and at the same time the answers the algorithm's queries are exactly the same as before.  So again the algorithm identifies x.  But now x is faulty.

2. If a strict majority of the processors are known to be non-faulty then a non-faulty processor can be identified in at most
f(n) := n - #1(n) - #LSB0(n)
queries, where #1(n) is the number of 1s in the binary representation of n, and #LSB0(n) is the number of 0s to the right of the rightmost 1 in the binary representation of n.  (This number may be 0.)  For example:

n = 1 (1);  #1(1) = 1;  #LSB0(1) = 0;  f(1) = 0
n = 6 (110);  #1(6) = 2;  #LSB0(6) = 1;  f(6) = 3
n = 12 (1100);  #1(12) = 2;  #LSB0(12) = 2;  f(12) = 8
n = 13 (1101);  #1(13) = 3;  #LSB0(13) = 0;  f(12) = 10
n = 16 (10000);  #1(16) = 1;  #LSB0(16) = 4;  f(16) = 11

Remarks.
For odd n, #LSB0(n) is always 0, so the formula for f(n) reduces to
f(n) = n - #1(n)
In the worst case #1(n) = 1 and we get f(n) = n-1.  In the best case (n = power of 2 minus 1) all binary digits are 1 and we get f(n) = n - log n.
For even n, #LSB0(n) >= 1.  In the worst case #LSB0(n) = 1 and #1(n) = 1 (this is the case n=2), and we get f(n) = n-2.  In all other cases we get less than n-2.  In the best case (n is the sum of a consecutive positive powers of two, e.g., 2, 6, 16, 56) f(n) = n - log n.

3.  I believe the bound in 2 is tight, but so far I haven't been able to prove it.  If and when I do (or manage to find a better upper bound) I will report back.


Here is how to achieve the f(n) bound.  The algorithm is recursive.

Base case: n = 1.
The single processor must be non-faulty, and no queries are required.


General case: n > 1.

Case A: n is even.
Then 'strict majority' implies that the non-faulty processors outnumber the faulty ones by at least 2.  So simply ignore one of the processors (leaving a strict majority of non-faulty processors among the remaining n-1 processors) and recursively run the algorithm on the remaining n-1 processors.  To see that the number of queries is at most f(n), note that #LSB0(n-1)=0 and #1(n-1)=#1(n)+#LSB0(n)-1.  (To verify this look what happens to the binary representation of an even number when you subtract 1 from it.)  So f(n-1) = f(n), as desired.

Case B: n is odd.
Denote the processors p1, p2, ..., pn.  Query p1 about p2, p3 about p4, p5 about p6, ..., p(n-2) about p(n-1).

Subcase B1:  All answers are 'non-faulty.'
Then each of the pairs contains either two non-faulty processors or two faulty ones.  Therefore we can ignore one processor from each pair and there will still be a strict majority of non-faulty processors among the remaining (n+1)/2 processors.  Invoke the algorithm recursively on these processors.
By the inductive hypothesis the number of queries in the recursive invocation is at most f((n+1)/2), so altogether the number of queries is at most
(n-1)/2 + f((n+1)/2) =
(n-1)/2 + (n+1)/2 - #1((n+1)/2) - #LSB0((n+1)/2) =
n - #1((n+1)/2) - #LSB0((n+1)/2).
It can be easily verified that
#1((n+1)/2) + #LSB0((n+1)/2) = #1(n) + #LSB0(n),
so the previous expression evaluates to
n - #1(n) - #LSB0(n) =
f(n).

Subcase B2:  Some of the answers are 'faulty.'
Then each of the corresponding pairs of processors contains one faulty processor and one non-faulty processor.  So if we ignore all such pairs there will still be a majority of non-faulty processors among the remaining ones.  Apply Subcase B1 to the remaining processors.
For the analysis, let t denote the number of 'faulty' answers (t >= 1).  Then by the inductive hypothesis the number of queries is at most
(n-1)/2 + f((n+1)/2 - t)
It is easy to verify that f(n) is monotone (just look at what happens to the binary representation of n when it increases by 1; treat the two cases odd n and even n separately).  Thus f((n+1)/2 - t) <= f((n+1)/2), so the number of queries is at most
(n-1)/2 + f((n+1)/2)
which, as we have already seen, is equal to f(n).
A.F.
Sunday, September 28, 2008
 
 
When writing down the solution I managed to convince myself that in Subcase B1 the parity of the number of pairs didn't matter.  In fact, two cases need to be considered separately.  If the number of pairs is even, proceed as indicated in my previous post.  However, if the number of pairs is odd, then it might be the case that processor pn is faulty while the number of non-faulty pairs is greater by exactly one than the number of faulty pairs.  In this case ignoring one processor in each pair will yield a half-half distribution of faulty/non-faulty among the remaining processors.  To overcome this potential problem, ignore one processor in each pair, as well as processor pn.  Now it is guaranteed that there will be a strict majority of non-faulty processors in the remaining set, and we can invoke the algorithm recursively on them.
The number of queries in this case is at most
(n-1)/2 + f((n-1)/2) = (n-1)/2 + f((n+1)/2) = f(n),
where the first equality is justified by the observation in case A (that f(n)=f(n+1) for odd n) and the second equality was shown in Subcase B1 of my previous post.

Monday, September 29, 2008
 
 
So far no luck on proving the lower bound.  I did, however, write a small computer program to search the entire space (with appropriate pruning so it won't take forever to run).  It verified that the upper bound is indeed tight up to n=41 (the highest I tried).
A.F.
Tuesday, October 28, 2008
 
 
A.F., I admire your dedication to this problem.
d Send private email
Tuesday, October 28, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz