三道GOOGL的笔试题 请教这里的大牛们

Dillon

回复 15# Elène85

其实严格的讲，上面给出的方法的时间复杂度虽然表面上看最低, 空间复杂读也是最低，但是两者实际都不是真正的最优。

从时间上来说，虽然上面的方法已经非常简单了, 但是因为需要不断的倒序访问内存, 会导致很多的cache miss。使用prefetch可以避免绝大多数的cache miss，但是还会有剩余的cache miss。

从空间上来说，使用的空间复杂度是O(2^N)，表面上看来不可能再少了，因为输出的是2^N个元素，但是实际上远远不是最优。
比如如果少循环一次，后一半的输出结果直接计算生成，那么空间复杂度下降到O(2^N / 2)

但是实际上最优的空间复杂度是O(0)，也就是说所有结果直接计算得出，不需要任何register之外的存储. 对应的时间复杂度也很低，虽然计算复杂一些, 但是没有任何cache miss。

因此如果能够快速计算出任何一个数列元素，不需要任何存储, 才是真正的最优解。
其实这样的方法是存在的，而且很简单。
如果你观察元素index和元素值的关系如下：

i = 0000, Si = 0000
i = 0001, Si = 0001
i = 0010, Si = 0011
i = 0011, Si = 0010
i = 0100, Si = 0110
i = 0101, Si = 0111
i = 0110, Si = 0101
i = 0111, Si = 0100
i = 1000, Si = 1100
i = 1001, Si = 1101
i = 1010, Si = 1111
i = 1011, Si = 1110
i = 1100, Si = 1010
i = 1101, Si = 1011
i = 1110, Si = 1001
i = 1111, Si = 1000
i=10000,Si =11000
i=10001,Si =11001
i=10010,Si =11011
i=10011,Si =11010
i=10100,Si =11110
i=10101,Si =11111
i=10110,Si =11101
发现什*么规律?
规律是i 和 Si 的第一个非零位相同；
最后一位的规律是LSB no.1 = ( i & 2 ) ^ ( i & 1 )，也就是说 i 最后两位的异或。
其实其他所有位也遵循这个规律.  对于结果的任何一位,其实都是index对应位和index对应的前一位的异或. 也就是说, Result = Index ^ ( Index >> 1 ).

Pseudo code:

OutputSerial( int n )
{
      for( unsigned int i = 0; i < pow(2, n); i ++ )
           printf("%x,",  i ^ ( i >> 1 ) );
}

结果是时间复杂度O(2^N),  代码如上非常简单, 也不可能更简单了.
空间复杂度O(0), 不使用任何内存, 也不可能更节省内存了.

伶俜

为啥要做这种题~~~
欺负应届生用的~

Elène85

回复  Elène85

其实严格的讲，上面给出的方法的时间复杂度虽然表面上看最低, 空间复杂读也是最低，但是 ...
Dillon 发表于 2010-2-19 23:31

    有劳DD政委了, 您太有心了 ,受教了!

Elène85

为啥要做这种题~~~
欺负应届生用的~
伶俜 发表于 2010-2-19 23:40

    问:为啥要做这种题?
    答:欺负应届生用的.

futuredream

Dillon 发表于 2010-2-18 11:14
The idea is to store the current min value or its index for each push.
And the push could be at O ...

仰慕大牛