CLSR芯片测试问题

Question

Finding ONE good VLSI chip in a population of good and bad ones, by using the 
pair test.  
     Chip A  Chip B  Conclusion 
     -------  -------  ---------- 
     B is good A is good both are good or both are bad 
     B is good A is bad at least one is bad 
     B is bad A is good at least one is bad 
     B is bad A is bad at least one is bad 


    Assumption : number of goods > number of bads 
    We can solve this in O(n) time complexity by splitting the population in half 
    every time and collecting one element of the GOOD, GOOD pair. 
    T(n) = T(n/2) + n/2 
    But to collect the pairs we need n/2 memory separately. 
    Can we do this in-place without using extra memory ?? 

Answer 1

该算法基于的问题是“我们可以移除芯片吗？”所以，对于每个芯片要删除，我们只是从我们的链表中删除它，就地（或者说，根本没有地方）。