最近找工作的事告一段落，發一些之前整理但未發表的文章。鑒于各個公司一般要求将所做筆試題和面試題保密，并要求在試卷上簽署了相關協定，是以本人不會在後續博文中提及并分析，見諒。
歸納并證明下面函數的輸出：
<a></a>
解答：
事實上increment(y)=y+1。
證明：
(1)（歸納法）y=0時輸出1。
(2)
y為偶數時，輸出y+1；
y為奇數時，不妨令y=2m+1，那麼2*increment((2m+1)/2) = 2*increment(m)。由于m<y且increment(m)=m+1 （歸納假設），那麼輸出為2*(m+1) = y+1。
得證。
用下面的方式實作動态數組：首先配置設定大小為1的連續空間，當需要填入第2個元素時，配置設定大小為2個連續空間，把原來的1個元素複制進新空間，再把新元素填入，銷毀原空間；依次類推，動态數組的容量變化過程為1->2->4->8->...。當數組中一共有n個元素時，一共被複制了幾次？
為簡化分析，n此時是2的幂且剛好把數組填滿。可以看出，其中1/2的元素沒有被複制過，另外1/2在上次擴充時複制了一次。即，上次擴充時複制了n*(1/2)個元素。一共擴充了logn次，是以複制的總次數為：
其中2^logn = n。由極限知識可知，當n→∞時，和為2n。是以n個元素的複制次數不超過2n次，保持了O(n)的時間複雜度。
附注：
Nginx封裝的資料結構ngx_array_t就是一種動态數組，采用了類似的記憶體配置設定政策。
對一個數組實作的n個元素的最小堆和給定的實數x，判斷堆中第k小元素是否大于等于x？（0<k<n）要求算法最壞時間複雜度為O(k)。（提示：沒必要找出第k小元素的具體值）
最直接的兩種解法：從堆中選取最小元素k次，時間複雜度O(klogn)；檢查堆中前k層所有元素，時間複雜度O(n,2^k)。這兩種解法都不符合時間複雜度的要求。
實際上是從根開始周遊所有值小于x的結點：
如果根大于等于x，那麼其餘所有元素都不可能小于x，第k小的元素必然大于等于x。這時傳回值為k>0。（若k=1，那麼第1小的元素就是根，結果不變）
如果根小于x，需要對根的兩個後繼進行周遊。如果你沒有看明白這段程式的含義，下面以幾個例子來幫助了解這個函數在遞歸調用時發生了什麼。假定k=3，x=3，即判斷第3小的元素是否大于等于3。簡單起見，結點以下标代替，根為1（與原書一緻）。
執行個體1：第k小的元素大于等于x。
執行個體2：第k小的元素大于等于x。原圖交換順序。
執行個體3：第k小的元素小于x。
從上面三個例子可以看出：
每找到一個小于x的元素都會消耗一個count，如果消耗完了k個，表示至少前k個都小于x。那麼第k個必然小于x，後面不必再進行查找，傳回值為0。
反之，如果周遊所有小于k的元素時未消耗完k個count，表示小于x的元素不足k個，那麼第k個必然大于等于x，傳回值為正值。
原代碼中令人迷惑的地方在于count的使用，理清上面的兩個關系就好了解了。雖然看上去這個函數對于一個結點的兩個後繼的處理地位不同，但實際上沒有影響。
至于時間複雜度，由于我們隻周遊了所有小于x的結點以及它們的後繼，而且周遊時不超過k個（用完k個就return 0），是以大約是3k個結點，時間複雜度隻有O(k)，符合要求。
這道題曾在Amazon的面試中出現。
本文轉自五嶽部落格園部落格，原文連結：http://www.cnblogs.com/wuyuegb2312/p/3257408.html，如需轉載請自行聯系原作者