程序員面試邏輯題解析

前言

　　“我去了一家以出晦澀謎題著稱的公司面試，因?yàn)樯线^這門課，那些謎題都不在話下。”　　——鮑里斯（Boris），上過我的謎題課的紐約大學(xué)畢業(yè)生　　有些人（比如我）喜歡謎題，還有些人覺得必須研究謎題才能在求職面試中取得成功。本書就是為這兩種人寫的。書中有一些很巧妙的題目，同時(shí)我也會(huì)教你一些解題技巧，幫助你挑戰(zhàn)新的謎題。還有，如果你能解決最后一部分的那些超級(jí)難題，還有可能會(huì)獲得獎(jiǎng)勵(lì)呢?！　『芏嗳朔磳?duì)在面試中采用謎題。他們反對(duì)的理由之一便是謎題的場(chǎng)景設(shè)置往往不合情理，例如，一個(gè)邏輯嚴(yán)謹(jǐn)?shù)娜瞬荒馨l(fā)聲也不愿寫字。好吧，我承認(rèn)，我也設(shè)計(jì)過這樣的題目，但是我的大部分謎題都源自真實(shí)的問題（例如，用偶爾說謊的人來對(duì)應(yīng)偶爾會(huì)發(fā)生故障的硬件）。在做研究時(shí)，我會(huì)嘗試將遇到的問題抽象成一道謎題，以便認(rèn)清根本問題，然后再處理表面現(xiàn)象。這個(gè)方法非常有效。因此，對(duì)我來說，謎題，尤其是那些恰當(dāng)?shù)暮妙}，也算是通往科學(xué)研究和工程實(shí)踐的光明之路?！　∧敲矗覟槭裁匆帉戇@些謎題呢？首先，當(dāng)然是因?yàn)樗鼈兎浅Ｓ腥?。其次，它們能有效地鍛煉腦力。在鮑里斯提到的謎題課上，學(xué)生們每周都編寫程序，還要比賽。這些程序每個(gè)運(yùn)行兩分鐘，獲勝者可以得到一塊奇巧巧克力。我講課的內(nèi)容不多，教給他們的技巧在第二部分都能找到。在課程結(jié)束時(shí)，學(xué)生們發(fā)現(xiàn)他們解決實(shí)際應(yīng)用問題的能力大大提高了，而這些必須要解決的現(xiàn)實(shí)問題往往已經(jīng)被算法教授打上了“難搞”的標(biāo)簽。我無法明確地告訴你這個(gè)神奇的轉(zhuǎn)變是由什么引起的，但是它確實(shí)發(fā)生了。　　本書第一部分中的多數(shù)題目都來自我在Scientific American和Dr. Dobb’s Journal上的謎題專欄，很多讀者給予了我至關(guān)重要的、充滿想象的反饋。這些反饋或者謎題本身引出了一些新的變體，因此即使你曾在雜志中看過這些題目，也需要更為深入地思考?！　≡?jīng)有很多次，當(dāng)不知道要如何解題時(shí)（即使是我自己設(shè)計(jì)的題目也會(huì)如此），我會(huì)先在紙上打打草稿，做一些嘗試。最初的嘗試通常是錯(cuò)的，但有時(shí)它會(huì)啟發(fā)我找到更好的思路。第一部分的每道題后面都有一些留白，供你打草稿用。　　攻克謎題是需要一定的思維模式的，一開始要天馬行空式地發(fā)散思維，然后要確定方向縝密有序地找出解決方案——整個(gè)過程神似于我們?cè)诘?章介紹的“模擬退火”技術(shù)。當(dāng)然我的方法不是唯一的思維模式。其他人告訴我的更好解法，我也很樂意分享給讀者?！　〉谝徊糠值拿恳徽拢ê芏蹋┒际且坏乐i題，答案在第一部分的最后。第二部分就幾種類型的謎題的解答方式展開探討，既有徒手計(jì)算的也有用計(jì)算機(jī)解答的。你會(huì)在這部分學(xué)到多種解題技巧應(yīng)付那些帶有約束條件的謎題，諸如數(shù)獨(dú)、調(diào)度問題、數(shù)學(xué)文字游戲和概率題等。坦率地說，我覺得這些解題技巧也算是一種算法。你要善假于物，隨意使用手頭的工具。第三部分需要你解開一個(gè)涉及密碼、銀行賬號(hào)和地理的謎團(tuán)。數(shù)學(xué)偵探艾可博士和他的朋友們會(huì)陪你一起探險(xiǎn)。（你以前可能已經(jīng)認(rèn)識(shí)了他們。）如果能解開這些謎題，就有可能獲獎(jiǎng)?！　『煤孟硎馨桑Ｄ愫眠\(yùn)?！　「?jìng)賽信息　　想要參與謎題破解競(jìng)賽的讀者，請(qǐng)把第三部分所有謎題的答案發(fā)到郵箱?！　「寮蟛捎肕icrosoft Word或PDF格式，截止時(shí)間是2008年8月31日。本書作者丹尼斯·夏沙（Dennis E. Shasha）是唯一的裁判，他會(huì)從所有回答正確的稿件中選出10份。優(yōu)勝者的獎(jiǎng)品是一件Wrox T恤和一頂Wrox棒球帽（或其他等值商品），Wrox出版的3本書（優(yōu)勝者自行挑選），還有一份“智多星”證書。為了確保收到獎(jiǎng)品，參賽者需要在來稿中附上郵寄地址（不能是郵政信箱）。提供法定禁止投送地區(qū)的無效。一般配送時(shí)間為6到8周。Wiley出版社對(duì)于參賽稿的遺失、字跡模糊或殘缺不全概不負(fù)責(zé)。Wiley出版社的員工不得參賽?！　〉谌糠殖霈F(xiàn)的所有密文可以在網(wǎng)站上下載Microsoft Word版本。進(jìn)入網(wǎng)站后，在搜索框內(nèi)輸入書名或ISBN號(hào)（978-0-470-12168-9）即可查到此書，然后在詳細(xì)信息頁(yè)面上單擊下載鏈接，便能獲得所有密文?！　2p.wrox.com　　我們也邀請(qǐng)你在p2p.wrox.com網(wǎng)站的P2P論壇上發(fā)表書中謎題的變體，或是提供其他的解決方案。這些論壇是一個(gè)基于Web的系統(tǒng)，讀者可以在上面發(fā)布與Wrox圖書相關(guān)的消息和相關(guān)技術(shù)，與其他讀者和技術(shù)用戶交流心得。論壇還提供了訂閱功能，只要論壇上發(fā)布了你感興趣的新話題，我們就會(huì)發(fā)電子郵件告知你。Wrox的作者、編輯、其他業(yè)界專家和讀者都會(huì)出現(xiàn)在這些論壇上?！　≡趆ttp：//p2p.wrox.com上，你會(huì)發(fā)現(xiàn)很多不同的論壇，它們不僅有助于閱讀此書，還有助于你開發(fā)自己的應(yīng)用程序。加入論壇的步驟如下?！　?1) 登錄p2p.wrox.com網(wǎng)站，單擊“注冊(cè)”（Register）鏈接。　　(2) 閱讀用戶使用條款，然后單擊“同意”（Agree）?！　?3) 填寫必要的注冊(cè)信息以及愿意提供的選填信息，并單擊“提交”（Submit）?！　?4) 你會(huì)收到一封電子郵件，告訴你如何確認(rèn)注冊(cè)賬戶并完成注冊(cè)過程。　　瀏覽論壇無需注冊(cè)，但只有注冊(cè)后才能發(fā)帖?！　〖尤胝搲缶涂梢园l(fā)帖和回帖了，你可以隨時(shí)訪問站點(diǎn)讀取信息。如果想要以郵件的形式訂閱某個(gè)特定論壇的更新，可以單擊論壇名旁邊的“訂閱此板塊”（Subscribe to this Forum）的圖標(biāo)?！　∮敿?xì)了解Wrox P2P的使用方法，一定要查看P2P FAQ，獲取關(guān)于論壇軟件運(yùn)行方式及P2P和Wrox圖書的常見問題的解答。要查看FAQ，在任意一個(gè)P2P頁(yè)面上點(diǎn)擊FAQ鏈接即可。

內(nèi)容概要

　　《程序員面試邏輯題解析》共分為3個(gè)部分。第一部分從有趣且鍛煉頭腦的謎題入手，繼而給出解題思路和詳細(xì)答案，更有“熱身問題”給大家提供充分的思考空間。第二部分綜合了不同類型的謎題，如數(shù)獨(dú)、調(diào)度問題及概率題等。神秘的第三部分帶領(lǐng)大家不斷歷險(xiǎn)，開動(dòng)腦筋，解決大量密碼及銀行賬戶等方面的問題。幾十道簡(jiǎn)潔的小謎題不僅充分鍛煉了我們的思維方式，更為提高面試成功率奠定了基礎(chǔ)。
　《程序員面試邏輯題解析》不僅適合程序員閱讀，更是謎題愛好者的饕餮盛宴。

作者簡(jiǎn)介

　　Dennis E.
Shasha，紐約大學(xué)柯朗數(shù)學(xué)研究所計(jì)算機(jī)科學(xué)教授，先后獲得耶魯大學(xué)理學(xué)學(xué)士、雪城大學(xué)理學(xué)碩士和哈佛大學(xué)哲學(xué)博士學(xué)位?！犊茖W(xué)美國(guó)人》網(wǎng)站和Dr.
Dobb’s Journal的謎題專欄作家。除本書外，還著有《奇思妙想：15位計(jì)算機(jī)天才及其重大發(fā)現(xiàn)》、Database
Tuning： A Principled Approach、The Puzzling Adventures of Dr.
Ecco、Natural Computing： DNA， Quantum Bits， and the Future of Smart
Machines 和Codes， Puzzles， and Conspiracy等書。

書籍目錄

第一部分 　智力游戲
第1章 　競(jìng)賽--不可能都是贏家
1.1 　甜食愛好者
1.2 　拜占庭賭徒
1.3 "碰碰"運(yùn)氣
1.4 　信息增益
1.5 　直沖云霄！
1.6 　政治分肥
1.7 　社會(huì)博弈
1.8 　貓鼠游戲
1.9 　流感中的數(shù)學(xué)
第2章 　設(shè)計(jì)--想象力決定一切
2.1 　冰上歷險(xiǎn)
2.2 　最佳術(shù)語(yǔ)
2.3 　巧分彈珠
2.4 　顏色反轉(zhuǎn)
2.5 　賽程編排
2.6 　生物中的分形學(xué)
2.7 　輕松分餡餅
第3章 　運(yùn)氣--獲得幸運(yùn)之神的垂青
3.1 　幸運(yùn)輪盤賭
3.2 　法律邏輯
3.3 　籌碼盒游戲
3.4 　反饋系數(shù)
第4章 　推理--你在想什么
4.1 　數(shù)字線索
4.2 　智力游戲
4.3 　"拒"中生智
4.4 　棘手的迷宮
4.5 　瘋狂配比
第5章 　優(yōu)化--達(dá)到事半功倍
5.1 　尋找地道
5.2 　天生一對(duì)
5.3 　概不找零
5.4 　寂靜深海
第6章 　前5章難題解答
6.1 　甜食愛好者
6.2 　拜占庭賭徒
6.3 　"碰碰"運(yùn)氣
6.4 　信息增益
6.5 　直沖云霄！
6.6 　政治分肥
6.7 　社會(huì)博弈
6.8 　貓鼠游戲
6.9 　流感中的數(shù)學(xué)
6.10 　冰上歷險(xiǎn)
6.11 　最佳術(shù)語(yǔ)
6.12 　巧分彈珠
6.13 　顏色反轉(zhuǎn)
6.14 　賽程編排
6.15 　生物中的分形學(xué)
6.16 　輕松分餡餅
6.17 　幸運(yùn)輪盤賭
6.18 　法律邏輯
6.19 　籌碼盒游戲
6.20 　反饋系數(shù)
6.21 　數(shù)字線索
6.22 　智力游戲
6.23 　"拒"中生智
6.24 　棘手的迷宮
6.25 　瘋狂配比
6.26 　尋找地道
6.27 　天生一對(duì)
6.28 　概不找零
6.29 　寂靜深海
第二部分 　解題密鑰
第7章 　謎題
7.1 　年齡排位
7.2 　城市規(guī)劃
7.3 　任務(wù)調(diào)度
7.4 　海底尋寶
7.5 　數(shù)獨(dú)
7.6 　數(shù)字編碼
7.7 　選擇性貪心
7.8 　最優(yōu)包裝
7.9 　重溫旅行推銷員問題
7.10 　超載系統(tǒng)的任務(wù)調(diào)度與凍結(jié)晶體
7.11 　單詞接龍
7.12 　同盟最大化
7.13 　決勝老虎機(jī)
7.14 　骰子的奧秘
7.15 　西瓜還是芝麻
第三部分 　冒險(xiǎn)故事
第8章 　忠誠(chéng)的敵人

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   3.如果你可以參加5局，“不總說實(shí)話”的顧問5次中必須有4次說實(shí)話，另外3位顧問可以隨意說謊，在這種情況下，你能保證最后至少還有150美元嗎？ 即使是5局，顧問們依然可以讓你贏不了多少。他們的策略一開始跟4局時(shí)的策略相似。 第一局：A和B說是0，C和D說是1。 結(jié)果：紙上的數(shù)字是1，A和B說了一次謊。 第二局：A和C說是0，B和D說是1。 結(jié)果：紙上的數(shù)字是1，A已經(jīng)說過兩次謊了，A肯定是“可以隨意說謊”的顧問之一。B和C各說過一次謊。D還沒有說過謊。 第三局：B和C說是0，A和D說是1。 現(xiàn)在我們來分情況討論。 第一種情況 假設(shè)第三局你不下注。如果紙上的數(shù)字是1，那么你可以推斷出D是“不總說實(shí)話”的顧問，因?yàn)槠溆嗟念檰柖家呀?jīng)說過兩次謊了。然而，D還有可能說一次謊。如果在第四局，D的建議是1，那么押x美元在1上，如果x

媒體關(guān)注與評(píng)論

"與其他謎題類圖書不同，本書獨(dú)具一格，專為程序員量身打造。個(gè)人認(rèn)為經(jīng)常做謎題能夠改善大腦功能。"                                           --亞馬遜讀者評(píng)論 "閱讀本書之前，我真的不知道如何使用動(dòng)態(tài)規(guī)劃算法。'最優(yōu)包裝'僅用兩頁(yè)紙的篇幅就教會(huì)了我。簡(jiǎn)單而優(yōu)雅的解答方案讓我一年后仍記憶猶新。"         --亞馬遜讀者評(píng)

編輯推薦

知名謎題作家力作，程序員面試題必備.書中從不同角度闡釋了各種類型謎題的解題技巧，從廣為人知的數(shù)獨(dú)，幸運(yùn)輪盤，賽程編排，旅行推銷員問題到貓鼠游戲，同盟最大化及選擇性貪心等。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    程序員面試邏輯題解析 PDF格式下載

---