書名：來自程式的試鍊：專為程式開發人員所寫的技術面試完全攻略
原書名：Cracking the Coding Interview, 5/e : 150 Programming Questions and Solutions
作者：Gayle Laakmann McDowell
譯者：我
出版社：悅知
頁數：560
很高興能夠接下這本書的翻譯工作，原書在Amazon獲得了五顆星的評價，希望我翻出來的譯文能讓大家滿意。
顧名思義，這本書的主題就是"面試"，而且是關於軟體設計、寫程式、、演算法資料結構、電腦網路、資料庫這方面工作的技術面試，前面約75頁介紹了面試前與面試後、面試流程與幕後、等等注意事項（不過這部份不是我翻譯的），接下來的篇幅就都是考題與解題技巧了，詳細列出常出會考的、重要的、該注意的考題，並且有詳細的解答、題目分析、以及該如何在面試中回答出讓面試官滿意的回答。
好書一本，希望我翻譯的成果也能讓你說好。
底下是這本書的目錄：
PART 1 面試流程
PART 2 幕後真相
PART 3 特殊情況
PART 4 面試之前
PART 5 行為式問題
PART 6 技術問題
PART 7 收到工作邀請之後
PART 8 面試考題
資料結構：面試考題與建議
01 陣列與字串
02 鏈結串列
03 堆疊與佇列
04 樹與圖形
概念與演算法：面試考題與建議
05 位元操作
06 腦力激盪考題
07 數學與機率
08 物件導向設計
09 遞迴與動態規劃法
10 規模擴展性與記憶體限制
11 排序與搜尋
12 測試 知識型：面試考題與建議
13 C與C++
14 Java
15 資料庫
16 執行緒與鎖
其他複習題：面試考題與建議
17 一般程度考題
18 進階程度考題
PART 9 解題技巧
資料結構：解題技巧
01 陣列與字串
02 鏈結串列
03 堆疊與佇列
04 樹與圖形
概念與演算法：解題技巧
05 位元操作
06 腦力激盪考題
07 數學與機率
08 物件導向設計
09 遞迴與動態規劃法
10 規模擴展性與記憶體限制
11 排序與搜尋
12 測試
知識型：解題技巧
13 C與C++
14 Java
15 資料庫
16 執行緒與鎖
其他複習題：解題技巧
17 一般程度考題
18 進階程度考題
勘誤表：
（感謝「路人22/9/12 11:38」的指正）
頁數：87、213
考題2.6的「連結串列」，應該是「鏈結串列」才對。
頁數：92
traversal跟traverse，我翻譯成「追蹤」，有讀者指出翻為「遍歷」或「走訪」較佳，我不否認，但追蹤一詞已經用了滿久了，有其歷史包袱。
頁數：132
合併排序法的英文應為「Merge Sort」，而非「Selection Sort」。
頁數：258、520
suffix tree，我翻成「後置樹」，應該翻成「後綴樹」才對。
頁數：266
原文：2. 搬移（shift）M，讓它對齊從 j到 i的位元。
shift在此翻譯成「移位」或「位移」 應該較佳。
你好，想回報一下一些小問題。
ReplyDelete我手上的版本是首版一刷。
[type error]
p87 環狀鍊結串列的鍊是錯別字。
p92 traversal通常譯作「遍歷」或者「走訪」，意義是讀遍所有資料。即便是traverse也不是追蹤的意思。
p132 合併排序法的英文應為「merge sort」。
p266 shift通常譯作「移位」或者「位移」。
p258 suffix tree應譯作「後綴樹」。
[concept error]
p134 基數排序法的平均狀況應該不是O(nlogn)。
p400 習題11.3最後說到最多需要O(n)，但是其實這題可以嚴謹的達到O(logn)。首先用O(logn)找到陣列最小的元素，往後就直接分成兩個陣列、分別做binary search。
p402 習題11.6有個極簡單的O(M+N)作法，作者沒提到。
感謝回報，我已經修改此篇文章，加上勘誤表。
Delete但關於你提到的[concept error]，我還有些疑惑：
關於p134的基數排序法
原文的確是寫O(nlogn)，我查到的資料也是。
關於p400的習題11.3
請問怎麼以O(logn)找到最小元素？
關於p402的習題11.6
請問此作法在網路上找得到嗎？
關於基數排序法，我也查了幾本書，的確有人說是O(nlgn)，不過這種說法相當詭異。
Delete基數排序法原本是O(kn)，k是指陣列當中最大的數字的位數。然而有些書在分析的時候，莫名其妙就說k大致上是logn，所以average-case、best-case是O(nlogn)。這根本就沒有道理，因為位數最大可以到無限大。
還有另一派人說是O(n)，這種說法有比較合理的解釋。
如果在比較式的排序法中，我們都假定O(1)時間就能比較兩個數字的大小。根據這個假定，一個數字的位數就是O(1)，於是用O(1)時間就能比較兩個數字的大小。因此基數排序法的時間複雜度可以寫成O(n)，其中的k就當作是O(1)了。這種情況下，不管worst-case、average-case、best-case都是O(n)了。
-----
索引值每次放大兩倍，直到數字比左端元素還小。此時最小值必在2^i和2^(i-1)之間，再用二分搜尋去找就找到了。
-----
找的到。
關鍵字sorted 2d array binary search
http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom
當然這是假設陣列裡的數字都不一樣。如果陣列裡的數字可以一樣，那麼時間複雜度是O(N*M)，每個元素都可能是答案，都至少要找一次。
關於p134的基數排序法：
Delete我想可能是你想的「worst-case、average-case、best-case」與作者想的假設條件不同，導致推論出來的big-O也不同。
關於p400的習題11.3：
以你的作法，最小值的確會在2^i和2^(i-1)之間，但是這一區間內的數字並不一定會是排序好的，這麼一來就不能用二分搜尋法。
關於p402的習題11.6：
如你所說，「假設陣列裡的數字都不一樣」，你想的條件跟作者假設的不同，所以導致不同的答案。
關於p134的基數排序法：
Delete作者先前在介紹合併、選擇、快速排序法時，便是假設交換兩數字為O(1)，才得到這些演算法的時間複雜度。然而作者沒有察覺到，以此為假設，基數排序法的時間複雜度應該是O(N)而不是O(NlogN)，況且上網查一下就能知道這件事了。
究其原因，多半是因為作者不夠瞭解這個問題，就連自己假設的條件都沒弄清楚。當然這不是譯者的問題。
關於p400的習題11.3：
無論陣列如何旋轉，最小值以左的數字，都比最左端元素（array[0]）還大；最小值以右的數字，都比最左端元素（array[0]）還小──2^i和2^(i-1)這段區間亦如是。
因此2^i和2^(i-1)可以使用二分搜尋法，當mid大於最左端元素（array[0]），表示最小值在右半邊，反之則在左半邊。
關於p402的習題11.6：
作者的第一個方法所提供的時間複雜度，便是假設數字都不一樣所得到的結果。然而作者沒有察覺到，以此為假設，其實有個更簡單的、針對數字都不一樣的O(M+N)方法，況且上網查一下就找得到這個方法了。
究其原因，多半是因為作者不夠瞭解這個問題，就連自己假設的條件都沒弄清楚。當然這不是譯者的問題。
This comment has been removed by the author.
ReplyDelete首先感謝路人的指教。
ReplyDelete關於p134的基數排序法：
我反覆看了你的分析與假設條件，還是看不懂為什麼基數排序法的時間複雜度應該是O(N)，上網找並沒有找到想要的解釋。請問，你是做了哪些假設、要怎麼分析才能得出O(N)？
關於p400的習題11.3：
你說的敘述是對的，但你不知道右半邊與左半邊的分界，其分界點是最小值，而這正是我們要找的。
關於p402的習題11.6：
你說的O(M+N)方法我看了，的確是較簡易的方法。
但作者並沒有假設「數字都不一樣」這個條件。
關於p134的基數排序法：
ReplyDelete如果你看不懂我所說的，應該是我講的不清楚。
請你多翻閱幾本演算法的書吧，相信書上一定會有提到，而且講得比我清楚。
如果是上網找資料的話，google book就有許多演算法電子書可供參考，關鍵字請下radix sort。
關於p400的習題11.3：
也許我講的不清楚。那麼我提供幾個討論串吧：
關鍵字rotation array binary search。
http://stackoverflow.com/questions/1878769/searching-a-number-in-a-rotated-sorted-array
http://stackoverflow.com/questions/4773807/searching-in-an-sorted-and-rotated-array
關於p402的習題11.6：
既然沒有假設，
那麼，數字可以一樣、也可以不一樣。
那麼，解題技巧1的時間複雜度應該是O(N*M)。
結論是：
（一）顯然作者沒有考慮到數字可以一樣。
（二）顯然作者沒寫下O(M+N)這個簡單的方法。
--
另外，習題11.6的題目有個括號寫著（漸昇型）。
如果它的原文是strictly increasing、monotone increasing，學術上是指每個數字都不一樣，一般譯作「嚴格遞增」、「單調遞增」。
如果它的原文是increasing，學術上是指數字可以一樣、也可以不一樣，一般譯作「遞增」或者「非嚴格遞增」。
所以原文書上的這個英文字，就決定了作者的假設條件。
根據你的翻譯方式，我想你可能不清楚這個英文字是個相當關鍵的地方。更大的可能性是，作者自身也不清楚這個英文字是個相當關鍵的地方。
關於p134的基數排序法：
ReplyDeleteO(n)的條件與分析，需要較多的篇幅，所以這本書就不寫了，這也不是一本演算法的書。
關於p400的習題11.3：
原來如此，謝謝。
關於p402的習題11.6：
原書用的是「ascending order」。
根據書上的遣詞用字以及內文，作者有時用「greater」，有時用「<=」，並沒有清楚地說出是遞增還是嚴格遞增。
作者似乎是假設每一列上的數字皆不相同、每一欄上的數字皆不相同，但某兩個位置的數字可能相同，就如同此題範例所畫出來的樣子，20重複出現了。
您好，因為這本書已經絕版多時，不知道在哪裡還可以找到您的譯本?
ReplyDelete(或是可否能請您提供電子檔呢? 感謝)
請向 悅知出版社 詢問，他們手上或許還有幾本。
Delete到二手書店找找，實體的、網路上的。
原文書有新版，寫信建議出版社翻譯新版。