2012/07/26

[廣告] 來自程式的試鍊:專為程式開發人員所寫的技術面試完全攻略 (Cracking the Coding Interview, 5/e : 150 Programming Questions and Solutions)

嗨,我翻譯了一本書,在這裡打打廣告。

書名:來自程式的試鍊:專為程式開發人員所寫的技術面試完全攻略
原書名: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在此翻譯成「移位」或「位移」 應該較佳。

11 comments:

  1. 你好,想回報一下一些小問題。
    我手上的版本是首版一刷。

    [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)作法,作者沒提到。

    ReplyDelete
    Replies
    1. 感謝回報,我已經修改此篇文章,加上勘誤表。

      但關於你提到的[concept error],我還有些疑惑:

      關於p134的基數排序法
      原文的確是寫O(nlogn),我查到的資料也是。

      關於p400的習題11.3
      請問怎麼以O(logn)找到最小元素?

      關於p402的習題11.6
      請問此作法在網路上找得到嗎?

      Delete
    2. 關於基數排序法,我也查了幾本書,的確有人說是O(nlgn),不過這種說法相當詭異。

      基數排序法原本是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),每個元素都可能是答案,都至少要找一次。

      Delete
    3. 關於p134的基數排序法:
      我想可能是你想的「worst-case、average-case、best-case」與作者想的假設條件不同,導致推論出來的big-O也不同。

      關於p400的習題11.3:
      以你的作法,最小值的確會在2^i和2^(i-1)之間,但是這一區間內的數字並不一定會是排序好的,這麼一來就不能用二分搜尋法。

      關於p402的習題11.6:
      如你所說,「假設陣列裡的數字都不一樣」,你想的條件跟作者假設的不同,所以導致不同的答案。

      Delete
    4. 關於p134的基數排序法:

      作者先前在介紹合併、選擇、快速排序法時,便是假設交換兩數字為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)方法,況且上網查一下就找得到這個方法了。

      究其原因,多半是因為作者不夠瞭解這個問題,就連自己假設的條件都沒弄清楚。當然這不是譯者的問題。

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. 首先感謝路人的指教。

    關於p134的基數排序法:
    我反覆看了你的分析與假設條件,還是看不懂為什麼基數排序法的時間複雜度應該是O(N),上網找並沒有找到想要的解釋。請問,你是做了哪些假設、要怎麼分析才能得出O(N)?

    關於p400的習題11.3:
    你說的敘述是對的,但你不知道右半邊與左半邊的分界,其分界點是最小值,而這正是我們要找的。

    關於p402的習題11.6:
    你說的O(M+N)方法我看了,的確是較簡易的方法。
    但作者並沒有假設「數字都不一樣」這個條件。

    ReplyDelete
  4. 關於p134的基數排序法:
    如果你看不懂我所說的,應該是我講的不清楚。
    請你多翻閱幾本演算法的書吧,相信書上一定會有提到,而且講得比我清楚。
    如果是上網找資料的話,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,學術上是指數字可以一樣、也可以不一樣,一般譯作「遞增」或者「非嚴格遞增」。

    所以原文書上的這個英文字,就決定了作者的假設條件。

    根據你的翻譯方式,我想你可能不清楚這個英文字是個相當關鍵的地方。更大的可能性是,作者自身也不清楚這個英文字是個相當關鍵的地方。

    ReplyDelete
  5. 關於p134的基數排序法:
    O(n)的條件與分析,需要較多的篇幅,所以這本書就不寫了,這也不是一本演算法的書。

    關於p400的習題11.3:
    原來如此,謝謝。

    關於p402的習題11.6:
    原書用的是「ascending order」。
    根據書上的遣詞用字以及內文,作者有時用「greater」,有時用「<=」,並沒有清楚地說出是遞增還是嚴格遞增。
    作者似乎是假設每一列上的數字皆不相同、每一欄上的數字皆不相同,但某兩個位置的數字可能相同,就如同此題範例所畫出來的樣子,20重複出現了。

    ReplyDelete
  6. 您好,因為這本書已經絕版多時,不知道在哪裡還可以找到您的譯本?
    (或是可否能請您提供電子檔呢? 感謝)

    ReplyDelete
    Replies
    1. 請向 悅知出版社 詢問,他們手上或許還有幾本。

      到二手書店找找,實體的、網路上的。

      原文書有新版,寫信建議出版社翻譯新版。

      Delete