面試經驗談 - C 語言篇

年紀一把還要被人確認 C 語言程度實在蠻冏的，不過兩個月沒 coding，程度真的有點下降(拜某幸福企業所賜)，只好再進牛棚熱身一下

這邊揀選的題目，是這1、2個月碰到出現率偏高的題目。這些題目相信很多人都看過了，但這邊不但列出所有的解法，而且還附上大量參考資料，夠有誠意吧？

問題 1: 無號整數裡位元 == 1 的個數

解法 1

最基本的解法，沒什麼可以多說的，除非你對 C 語言位移運算很生疏

int bitcount(unsigned int x)
{
    int count, i;
    
    for(i = 0, count = 0; i < 32; ++i)
        if((1<<i) & x)
            ++count;
        
    return count;
}

解法 2

int bitcount(unsigned int x)
{
    int count;

    for(count = 0; x != 0; x &= x - 1)
        ++count;

    return count;
}

解法 2 出自 The C Abswer Book 2nd，也就是 K&R C 2nd 習題 2-9 的解答。這個解法的原理利用最右邊的 bit - 1 時產生的位元變化。首先我們知道：

x = (x - 1) + 1

這邊假設 x 是個只有 4bits 長度的無號整數，x = 1010b：

這代表 x - 1 後，最右端為 0 的位元 0 變 1，最右端為 1 的位元變成 0，則

x &= x - 1 -> x = 1010 & 1001 = 1000

可以清除 x  最右端為 1 的位元。由上面的例子得到 x &= x - 1 得到
x = 1000b，這時候再進行一次 x &= x - 1 效果會更明顯：

按照這個路數，worst case 就是 x 的位元全部等於 1 的情形，但平均起來還是快過解法 1。

解法 3

解法 3 的思路是這樣，首先，假設我們有一個 32bits unsigned int x，x 內容以二進制表示如下：

然後我們把位元倆倆一組，也就是除以 2 分成 16 組，每一組有 2 bits，如果把這兩個 bit 相加，那就可以得到這一組 bit = 1 的個數。我們知道兩個 bit = 1，相加的極大值就是 2，這個和剛好可以放在這 2 bits 裡：

以這個思路再繼續下去，這次分成 8 組(16 / 2 = 8)，每一組有 4 bits，每一組左半部與右半部相加極大值為 4，也就是需要用 3 bits 表示，但每一組空間有 4bits，可見得綽綽有餘：

以此類推，最後 x 就會等於 x 中 bit = 1 的個數，需要的運算的次數為 log(32) = 5，說穿了這個技巧就是 divide and conquer。C 語言範例如下：

int bitcount(unsigned int x)
{
    x = (x & 0x55555555) + ((x>>1) & 0x55555555);
    x = (x & 0x33333333) + ((x>>2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x>>4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x>>8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x>>16) & 0x0000FFFF);
    return x;
}

甚至還可以再進一步簡化：

int bitcount(unsigned int x)
{
    x = x - ((x>>1) & 0x55555555);
    x = (x & 0x33333333) + ((x>>2) & 0x33333333);
    x = (x + (x>>4)) & 0x0F0F0F0F;
    x = x + (x>>8);
    x = x + (x>>16);
    return (x & 0x0000003F);
}

Line#3 運用了下列公式的前兩項：

其餘部份則是應用了進行位移之後與原數相加會不會造成 每組發生 overflow？以 Line#5 來說，4bits 與 4bits 相加，每個 4bits 裡最大為 4，相加最大為 8，所以不會造成 overflow，可以放心進行省略。

解法 3 取自 Hacker's Delight Chapter 5，事實上筆者不建議面試時用這種解法，因為如此炫技的解法，八成會讓不少主管窮追猛打，正所謂作人張揚，木秀於林風必摧之。建議先用解法 1，如果主管追問有沒有更好的作法再慢慢秀出 2 跟 3，敵不動我不動，積蓄力量，後發制人。

如何檢查 linked list 是否存在循環？

筆者最早是在 Expert C Programming 附錄 A 看到這個題目，有興趣的朋友請可以找這本書來看，這邊整理出一些摘要分享給大家：

解法 1

對訪問過的每個元素做標記，直到碰到已經被標記過的元素代表存在循環。

解法 2

把每個訪問過的元素位址存在一個陣列中，每次訪問下一個元素就檢查是否出現在這個陣列中。

解法 3

如果面試官說沒有足夠空間放解法 2 的陣列，那訪問第 n 個元素時就往前檢查 n - 1  個元素。

旋轉一維陣列

簡單來說，就是把陣列分為 a b 兩個部份，a 與 b 交換，得到 b a：

對這一題解法有興趣的朋友可以參考 Programmng Pearls 2nd 專欄 2，大概沒有人可以解釋的比 Jon Bentley 更好了。筆者 n 年前也寫過一篇相關文章，這邊就不重複了。

陷阱題

丟出一段有問題的程式碼，要你把問題找出來。不為何讓我想起有人說過上個世紀是把人訓練成機器，這個世紀是把機器訓練成人，當然你不可以寫  "Do you know cppcheck/oclint/pc-lint/valgrind?"，這樣是不會有分數的。

在已經停刊的 RUN!PC 裡有一期王國榮先生有專門做過這個主題。還有一本 WRITING SOLID CODE(中文版: 如何撰寫零錯誤程式，已絕版)也可以找來看看。

這邊推薦一本小冊子 The C Puzzle Book，這本書每一章都是針對 C 某個語法列出一些題目，然後問你輸出是什麼？或者是調整程式的結構，解答非常詳盡。個人認為這本練完也算有小成了，裡面的題目 C 語言初學者來說頗有難度。如果你很想很想去某間必考 C 語言的公司上班，你沒學過 C 語言，這本苦練半個月應該可以提高錄取的機率，不過講到這裡筆者不禁想起最近常讀的一本書「康乃爾最經典的邏輯思考課(HOW WE KNOW WHAT ISN'T SO)」，裡面有提到一則「錯誤共識效應」，指高估他人跟自己具有相同認知與喜好的程度，所以也別過度想像，LinkedIn 老闆講過，員工最好把上班當成軍隊服役。

另類想法

「人多的地方不要去」，或許脫穎而出的方式就是去學一門比較沒那麼熱門的語言，比方說 Go，事實上有些公司正苦於找不到會 Go 的人退而求其次找 C/C++，如果您年紀尚輕可以壓寶看看，也許是片新藍海喔！