大約從2011年開始，一些比較大的IT公司開始在面試中加上技術/技能測試，比如Amazon，Facebook，等公司，這種現象所反映出的問題大概是對美國現有大學教育質量的一種不信任。從我的理解而言，大學應該是為社會培養並選拔人才的地方，當一個人完成了四年的學業之後，其所在的大學有義務對該學生進行一番客觀的鑑定，對其才能和特長應該加以歸類，評估，以便交給未來的用人單位，如此可以減少用僱傭時的失誤。畢竟一個公司面試最多也就是6個小時左右，它比一個人化四年的時間讀大學要少的多。但現在的美國大學除了賺錢就是賺錢，其社會功效與社會義務基本降低到零。這就促使用人單位不得不自己出考題，以考察應試者的技術水平，這對整個一個國家的教育體系而言，真是一個莫大的諷刺。下面就是一道Facebook的面試題，是通過Skpye對應試者進行測試的。如果你的小孩恰好在學計算機專業，不妨讓他們也感受一下，這是一道什麼樣水平的題？

-----------------------------------

首先對26個英文字母進行如下的編碼：

0-A, 1-B, 2-C, 3-D, 4-E, 5-F, 6-G, 7-H, 8-I, 9-J, 10-K,

11-L, 12-M,13-N, 14-O, 15-P, 16-Q, 17-R, 18-S, 19-T,

20-U, 21-V, 22-W, 23-X, 24-Y, 25-Z.

然後隨便給你一個有限的數字串，舉個例子：12320562345610，現在讓你設計一個算法，計算一下，如果把這個數字串轉化為英文字母串，能有多少種轉化方法？

------------------------------------

解決這道題的關鍵是要想出一個能夠遍歷的方法。就拿上面的那串數字串來說，如果採用單數字編碼，那麼它可以轉化為：BCDCAFGCDEFGBA.當然也可以採用一部分的雙數字編碼。但要遍歷全部各種可能性，就要找到一種次序，沿着它可以找到全部的字母串。

------------------------------------

一個比較簡單的辦法是要把遍歷的次序與自然數建立一個一一的對應關係，由於給定的數字串是由有限的數字所構成，因此可以設想，一旦建立起與自然數的某種對應關係之後，通過遍歷自然數的一個子集，就可以找到它的全部字母串。如此就不會遺漏某個字母串。

自然數從0開始，即：0, 1, 2, 3, 4, ....; 然後把這個自然數用2進制表示，即：0, 1, 10, 11, 100, 101, ....;

然後構造一個像圖靈機一樣的自動機，它要把這些2進制數讀進來，每次只讀一個。比如說在開始的時候，第1次它讀進來的數是0，然後按照0這個指令，對上述的數字串進行轉化，把之轉化為字母串，其指令規則如下，

0 = 0000000000...；每個0對應相應的數字串的位置，如果都是0，那自動機就把給定數值串按照一位進行轉換，換句話說，就是每個數字轉化為一個字母。如此得到第一個字母串。

1 = 100000000....; 自動機要把數字串最左端的兩位數字合併在一起轉化為一個字母，而其餘的都是一位數字轉化為一個字母。總結一下，其轉換規則為：（2位）（1位）（1位）....

2 = 010000000...; 其轉換規則為：(1位）（2位）（1位）（1位）....;

3 = 110000000,...;其轉換規則為：（2位）（2位）（1位）（1位）,...;

4 = 001000000,...;其轉換規則為：(1位）（1位）（2位）（1位），...;

5 = 101000000,...;其轉換規則為：（2位）（1位）（2位）（1位）,...;

....

按照上述的次序，自動機每讀進一個自然數，先把它化為2進制數，根據其相應的0與1的位置，對給定的數字串進行轉換，如果那一位是0，就把單個數字轉化為字母，如果那位是1，就把相應的2個數字轉化為字母。如此得到遍歷。

當然這裡邊還有個小問題：並不是任何兩個數字的編碼都有相應的字母向對應的，比方說，如果機器遇到像30這樣的兩位數，那它就無法轉換為字母。為了解決這個問題，你可以設計一個計數變量，存儲着到目前為止的全部轉換成功的字母串的個數。如果遇到中間含有30這樣的無效編碼，自動機可以讀下一個自然數，就把這個數給跳過去了，當然那個計數變量並沒有改變，因為你讀了一個無效的編碼指令。

---------------------

上面的這種方法有一定的普遍性，比方說我給你一個漢字編碼表如下：

0 - 啊

1 - 阿

2 - 呵

...;

一共給你3000個，然後隨便給你一個數字串，讓你把它轉化為漢字串，問能有多少種轉換方法？

這個問題涉及到：1位數字編碼，2位數字編碼，3位數字編碼，和4位數字編碼。因此，你要把自然數先轉化為4進制數，那麼整個自然數就是由0，1，2，3所組成，當自動機讀進一個自然數並把它轉化為一個4進制數以後，然後把這個4進制數當成一個指令串，遇到0，就取1位編碼，遇到1就取2位編碼，遇到2就去3位編碼，以此類推，這樣可以覆蓋整個可能轉換的漢字串。