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

該算法基於的問題是「我們可以移除芯片嗎？」所以，對於每個芯片要刪除，我們只是從我們的鏈表中刪除它，就地（或者說，根本沒有地方）。