Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have the following problem:

Given n chips [note: these are VLSI chips] out of which majority of chips are good, we need to find one good chip. The only test that we can apply is on a pair of chips that answers if both chips are good or both are bad. The second part is to find a good chip if some tests might produce a wrong result. Also, the results are systematic meaning that if a pair gives wrong result, it will always give the wrong result.

I have solved the first problem using divide and conquer approach where I reduce the problem set to at least half every time. This can be done by simply performing tests on n/2 distinct pairs every time and keeping those pairs that answer a YES (i.e. both good or bad). I am unable to solve the second part of the problem.

A wrong result means that even if two chips are good or bad, the test might answer a NO. Also note that the percentage of wrong tests is very low.

How can I go about solving this problem?

share|improve this question

migrated from stackoverflow.com Dec 3 '11 at 20:44

This question came from our site for professional and enthusiast programmers.

2  
What have you tried? –  talnicolas Dec 3 '11 at 19:07
    
@talnicolas I am still trying to figure out a good starting point for the second part. –  Anna Dec 3 '11 at 19:28
    
@Anna: Can you throw more light on the second part? what do you mean by a wrong result? ie, what will be the output if I test with one good chip and one bad chip ? –  bragboy Dec 3 '11 at 19:29
    
@Bragboy I have updated the problem statement. –  Anna Dec 3 '11 at 19:33
    
What can we assume about the error rate? –  templatetypedef Dec 3 '11 at 19:43

5 Answers 5

up vote 2 down vote accepted

I think this is a clustering problem: you have two clusters - the good chips and the bad chips. Your test tells you if two chips belong in the same cluster or not - at least under my interpetation of the question you have asked. The reference provided in the answer by Woot4Moo suggests a different question to this.

For the first part of the test, pick one chip and test every other chip against it. You get two clusters of chips - those that are of the same kind as the first chip, and those that are different. The good chips are in the larger cluster, so pick one at random.

For the second part, use n chips for testing, so that for each chip you have an n-bit pattern, saying whether it was in the same cluster as each of the n test chips. Expect to see mostly two sorts of patterns, each the inverse of the other. You can use this to sort the chips into two clusters as before, and hope that the larger cluster is composed of good chips.

share|improve this answer
    
No hope is necessary. As long as the difference between good chips and bad chips is much larger than the error rate, the larger pile will have the good chips. –  William Shakespeare Dec 4 '11 at 13:45

To find the wrong results, I would compare each chip to multiple other chips. If chips 1 and 2 give a wrong result, the likelihood that comparing 1 to 3, 4, 5, and 6 all also giving wrong results in those four comparisons is greatly diminished. Since you know the percentage of wrong results, it's probably possible to do some math to calculate how many comparisons you need to do to completely eliminate the wrong results, or at least reduce it to an acceptable rate. In the real world you'd sure want to do that, and then some -- perhaps balancing the cost of each comparison, the cost of using/shipping bad chips, and needlessly tossing good chips.

You also don't clearly say what happens when you compare good vs. bad (good test and wrong result). A wrong result with bad vs. bad would be YES, wouldn't it? Make sure you cover all scenarios.

share|improve this answer
    
A good vs bad test and a wrong result will produce a YES. A bad vs bad OR good vs good and a wrong result will produce NO. –  Anna Dec 5 '11 at 18:06
    
Thank you for clarifying. I don't think that changes the approach I recommend...I'm leaving those fine details for you. Multiple tests of a chip to several others is the only way to detect wrong results. –  minnow Dec 5 '11 at 21:04

For the first problem I don't think divide and conquer is the best approach. You would just want to walk the list until you found a good pair. An explanation may help here:

Starting size = 100  
First split = 50/50  
Second split = 25,25 / 25,25  
Third split = 12,13,12,13/ 12,13,12,13  
Fourth split = 6,6,6,7,6,6,6,7/ 6,6,6,7,6,6,6,7
Fifth split = 3,3,3,3,3,3,3,4,3,3,3,3,3,3,3,4/3,3,3,3,3,3,3,4,3,3,3,3,3,3,3,4  
etc.    

Then we start working on each of those pairs until we find a good one. This is far less efficient than just walking a list for a good pair.

In terms of the second problem this is a general manufacturing problem so solving it is not as straight forward as one would think. The reason why it is hard is that it means that the testing program is inheritently incorrect. It is why when you buy a new laptop it can pass system test and fail to function when you get it home and turn it on. There is not yet a practical answer for this in the real world, so solving it makes you rich (essentially). The following page provides some analysis on the chip problem: chips

share|improve this answer
    
Thanks for the solution. But I am trying to find a good approximation for the second part. Or an exact solution if it exists (for a very low error rate) –  Anna Dec 3 '11 at 19:45
    
@Anna the exact solution has not yet been released to the public, as far as i know. The link I provided supplies a little bit of analysis on it. –  Woot4Moo Dec 3 '11 at 19:48
    
How do you know which is 'a good pair'? You can only know that a pair is 'same' or 'different'. –  William Shakespeare Dec 4 '11 at 13:51
    
@Caleb it is implied by the question we can only tell if both chips are good or bad. Meaning that there will be no result in the event that there is one of each. Therefore when both are good the machine returns good and when both are bad the machine returns bad. –  Woot4Moo Dec 4 '11 at 17:20
    
I understand it differently: it seems to me that the test returns YES if two chips are the same (either both good or both bad) and NO if the chips are different. –  William Shakespeare Dec 4 '11 at 17:32

The test for sameness lets you divide the chips into two piles. Select any chip and test all the others against it, putting the chips into 'same' and 'different' piles (the selected chip goes into the 'same' pile). It doesn't matter whether the selected chip is good or bad -- you have no way to know that until the testing is done. Then use your knowledge about the distribution of good and bad chips to figure out which pile is which.

For part two, realize that your confidence in a given chip increases as it tests 'same' against other chips thought to be good.

share|improve this answer

Here's a very broad overview:

Data structures:

  • Have a table of comparison results: uncompared, good, bad. If memory is a concern, you can use two bits for each entry and pack multiple, à la bit vectors (but in two dimensions, rather than one). If memory is really a concern, you can use the fact that the table is symmetric (compare[a][b] = compare[b][a]) to create a triangular table, where row n has n entries (requiring ceil(n/4) bytes).

Basic algorithm:

  • Perform an initial round of comparisons. If two chips compare as good, the algorithm can stop.
  • As long as no good chips are found, repeat comparison round, using table to ensure you don't compare the same two chips a second time.

If you're clever, you can design a comparison schedule that won't often pick previously compared chips (for the first few rounds, at any rate). Simple random picking should perform fairly well, as there will be a k/(n-1) chance in round k of picking previously compared chips.

If you need to find more than one good chip, keep two collections: good and suspect. Initially, all chips are suspect. When you find good chips, move them from "suspect" to "good". Preferentially use good chips for comparisons.

share|improve this answer
    
How do you find which chips are good in the first place? –  Anna Dec 5 '11 at 18:12
    
@Anna: this answer was due to a misreading of the problem. I'll update this answer when I've had a chance to think over it. –  outis Dec 5 '11 at 23:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.