程序员面试逻辑题解析

出版时间：2013-1  出版社：人民邮电出版社  作者：萨沙  页数：208  字数：328000  译者：朱学武,费若愚  
Tag标签：无  

前言

　　“我去了一家以出晦涩谜题著称的公司面试，因为上过这门课，那些谜题都不在话下。”　　——鲍里斯（Boris），上过我的谜题课的纽约大学毕业生　　有些人（比如我）喜欢谜题，还有些人觉得必须研究谜题才能在求职面试中取得成功。本书就是为这两种人写的。书中有一些很巧妙的题目，同时我也会教你一些解题技巧，帮助你挑战新的谜题。还有，如果你能解决最后一部分的那些超级难题，还有可能会获得奖励呢。　　很多人反对在面试中采用谜题。他们反对的理由之一便是谜题的场景设置往往不合情理，例如，一个逻辑严谨的人不能发声也不愿写字。好吧，我承认，我也设计过这样的题目，但是我的大部分谜题都源自真实的问题（例如，用偶尔说谎的人来对应偶尔会发生故障的硬件）。在做研究时，我会尝试将遇到的问题抽象成一道谜题，以便认清根本问题，然后再处理表面现象。这个方法非常有效。因此，对我来说，谜题，尤其是那些恰当的好题，也算是通往科学研究和工程实践的光明之路。　　那么，我为什么要编写这些谜题呢？首先，当然是因为它们非常有趣。其次，它们能有效地锻炼脑力。在鲍里斯提到的谜题课上，学生们每周都编写程序，还要比赛。这些程序每个运行两分钟，获胜者可以得到一块奇巧巧克力。我讲课的内容不多，教给他们的技巧在第二部分都能找到。在课程结束时，学生们发现他们解决实际应用问题的能力大大提高了，而这些必须要解决的现实问题往往已经被算法教授打上了“难搞”的标签。我无法明确地告诉你这个神奇的转变是由什么引起的，但是它确实发生了。　　本书第一部分中的多数题目都来自我在Scientific American和Dr. Dobb’s Journal上的谜题专栏，很多读者给予了我至关重要的、充满想象的反馈。这些反馈或者谜题本身引出了一些新的变体，因此即使你曾在杂志中看过这些题目，也需要更为深入地思考。　　曾经有很多次，当不知道要如何解题时（即使是我自己设计的题目也会如此），我会先在纸上打打草稿，做一些尝试。最初的尝试通常是错的，但有时它会启发我找到更好的思路。第一部分的每道题后面都有一些留白，供你打草稿用。　　攻克谜题是需要一定的思维模式的，一开始要天马行空式地发散思维，然后要确定方向缜密有序地找出解决方案——整个过程神似于我们在第2章介绍的“模拟退火”技术。当然我的方法不是唯一的思维模式。其他人告诉我的更好解法，我也很乐意分享给读者。　　第一部分的每一章（很短）都是一道谜题，答案在第一部分的最后。第二部分就几种类型的谜题的解答方式展开探讨，既有徒手计算的也有用计算机解答的。你会在这部分学到多种解题技巧应付那些带有约束条件的谜题，诸如数独、调度问题、数学文字游戏和概率题等。坦率地说，我觉得这些解题技巧也算是一种算法。你要善假于物，随意使用手头的工具。第三部分需要你解开一个涉及密码、银行账号和地理的谜团。数学侦探艾可博士和他的朋友们会陪你一起探险。（你以前可能已经认识了他们。）如果能解开这些谜题，就有可能获奖。　　好好享受吧，祝你好运。　　竞赛信息　　想要参与谜题破解竞赛的读者，请把第三部分所有谜题的答案发到邮箱。　　稿件要求采用Microsoft Word或PDF格式，截止时间是2008年8月31日。本书作者丹尼斯·夏沙（Dennis E. Shasha）是唯一的裁判，他会从所有回答正确的稿件中选出10份。优胜者的奖品是一件Wrox T恤和一顶Wrox棒球帽（或其他等值商品），Wrox出版的3本书（优胜者自行挑选），还有一份“智多星”证书。为了确保收到奖品，参赛者需要在来稿中附上邮寄地址（不能是邮政信箱）。提供法定禁止投送地区的无效。一般配送时间为6到8周。Wiley出版社对于参赛稿的遗失、字迹模糊或残缺不全概不负责。Wiley出版社的员工不得参赛。　　第三部分出现的所有密文可以在网站上下载Microsoft Word版本。进入网站后，在搜索框内输入书名或ISBN号（978-0-470-12168-9）即可查到此书，然后在详细信息页面上单击下载链接，便能获得所有密文。　　p2p.wrox.com　　我们也邀请你在p2p.wrox.com网站的P2P论坛上发表书中谜题的变体，或是提供其他的解决方案。这些论坛是一个基于Web的系统，读者可以在上面发布与Wrox图书相关的消息和相关技术，与其他读者和技术用户交流心得。论坛还提供了订阅功能，只要论坛上发布了你感兴趣的新话题，我们就会发电子邮件告知你。Wrox的作者、编辑、其他业界专家和读者都会出现在这些论坛上。　　在http：//p2p.wrox.com上，你会发现很多不同的论坛，它们不仅有助于阅读此书，还有助于你开发自己的应用程序。加入论坛的步骤如下。　　(1) 登录p2p.wrox.com网站，单击“注册”（Register）链接。　　(2) 阅读用户使用条款，然后单击“同意”（Agree）。　　(3) 填写必要的注册信息以及愿意提供的选填信息，并单击“提交”（Submit）。　　(4) 你会收到一封电子邮件，告诉你如何确认注册账户并完成注册过程。　　浏览论坛无需注册，但只有注册后才能发帖。　　加入论坛之后就可以发帖和回帖了，你可以随时访问站点读取信息。如果想要以邮件的形式订阅某个特定论坛的更新，可以单击论坛名旁边的“订阅此板块”（Subscribe to this Forum）的图标。　　欲详细了解Wrox P2P的使用方法，一定要查看P2P FAQ，获取关于论坛软件运行方式及P2P和Wrox图书的常见问题的解答。要查看FAQ，在任意一个P2P页面上点击FAQ链接即可。

内容概要

　　《程序员面试逻辑题解析》共分为3个部分。第一部分从有趣且锻炼头脑的谜题入手，继而给出解题思路和详细答案，更有“热身问题”给大家提供充分的思考空间。第二部分综合了不同类型的谜题，如数独、调度问题及概率题等。神秘的第三部分带领大家不断历险，开动脑筋，解决大量密码及银行账户等方面的问题。几十道简洁的小谜题不仅充分锻炼了我们的思维方式，更为提高面试成功率奠定了基础。
　《程序员面试逻辑题解析》不仅适合程序员阅读，更是谜题爱好者的饕餮盛宴。

作者简介

　　Dennis E.
Shasha，纽约大学柯朗数学研究所计算机科学教授，先后获得耶鲁大学理学学士、雪城大学理学硕士和哈佛大学哲学博士学位。《科学美国人》网站和Dr.
Dobb’s Journal的谜题专栏作家。除本书外，还著有《奇思妙想：15位计算机天才及其重大发现》、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章 　竞赛--不可能都是赢家
1.1 　甜食爱好者
1.2 　拜占庭赌徒
1.3 "碰碰"运气
1.4 　信息增益
1.5 　直冲云霄！
1.6 　政治分肥
1.7 　社会博弈
1.8 　猫鼠游戏
1.9 　流感中的数学
第2章 　设计--想象力决定一切
2.1 　冰上历险
2.2 　最佳术语
2.3 　巧分弹珠
2.4 　颜色反转
2.5 　赛程编排
2.6 　生物中的分形学
2.7 　轻松分馅饼
第3章 　运气--获得幸运之神的垂青
3.1 　幸运轮盘赌
3.2 　法律逻辑
3.3 　筹码盒游戏
3.4 　反馈系数
第4章 　推理--你在想什么
4.1 　数字线索
4.2 　智力游戏
4.3 　"拒"中生智
4.4 　棘手的迷宫
4.5 　疯狂配比
第5章 　优化--达到事半功倍
5.1 　寻找地道
5.2 　天生一对
5.3 　概不找零
5.4 　寂静深海
第6章 　前5章难题解答
6.1 　甜食爱好者
6.2 　拜占庭赌徒
6.3 　"碰碰"运气
6.4 　信息增益
6.5 　直冲云霄！
6.6 　政治分肥
6.7 　社会博弈
6.8 　猫鼠游戏
6.9 　流感中的数学
6.10 　冰上历险
6.11 　最佳术语
6.12 　巧分弹珠
6.13 　颜色反转
6.14 　赛程编排
6.15 　生物中的分形学
6.16 　轻松分馅饼
6.17 　幸运轮盘赌
6.18 　法律逻辑
6.19 　筹码盒游戏
6.20 　反馈系数
6.21 　数字线索
6.22 　智力游戏
6.23 　"拒"中生智
6.24 　棘手的迷宫
6.25 　疯狂配比
6.26 　寻找地道
6.27 　天生一对
6.28 　概不找零
6.29 　寂静深海
第二部分 　解题密钥
第7章 　谜题
7.1 　年龄排位
7.2 　城市规划
7.3 　任务调度
7.4 　海底寻宝
7.5 　数独
7.6 　数字编码
7.7 　选择性贪心
7.8 　最优包装
7.9 　重温旅行推销员问题
7.10 　超载系统的任务调度与冻结晶体
7.11 　单词接龙
7.12 　同盟最大化
7.13 　决胜老虎机
7.14 　骰子的奥秘
7.15 　西瓜还是芝麻
第三部分 　冒险故事
第8章 　忠诚的敌人

章节摘录

版权页：   插图：   3.如果你可以参加5局，“不总说实话”的顾问5次中必须有4次说实话，另外3位顾问可以随意说谎，在这种情况下，你能保证最后至少还有150美元吗？ 即使是5局，顾问们依然可以让你赢不了多少。他们的策略一开始跟4局时的策略相似。 第一局：A和B说是0，C和D说是1。 结果：纸上的数字是1，A和B说了一次谎。 第二局：A和C说是0，B和D说是1。 结果：纸上的数字是1，A已经说过两次谎了，A肯定是“可以随意说谎”的顾问之一。B和C各说过一次谎。D还没有说过谎。 第三局：B和C说是0，A和D说是1。 现在我们来分情况讨论。 第一种情况 假设第三局你不下注。如果纸上的数字是1，那么你可以推断出D是“不总说实话”的顾问，因为其余的顾问都已经说过两次谎了。然而，D还有可能说一次谎。如果在第四局，D的建议是1，那么押x美元在1上，如果x

媒体关注与评论

"与其他谜题类图书不同，本书独具一格，专为程序员量身打造。个人认为经常做谜题能够改善大脑功能。"                                           --亚马逊读者评论 "阅读本书之前，我真的不知道如何使用动态规划算法。'最优包装'仅用两页纸的篇幅就教会了我。简单而优雅的解答方案让我一年后仍记忆犹新。"         --亚马逊读者评

编辑推荐

知名谜题作家力作，程序员面试题必备.书中从不同角度阐释了各种类型谜题的解题技巧，从广为人知的数独，幸运轮盘，赛程编排，旅行推销员问题到猫鼠游戏，同盟最大化及选择性贪心等。

用户评论 (总计36条)

•   一本为程序员量身打造的面试逻辑题
•   论实用性没有程序员面试宝典那般直接但可以拿来做思维训练用还是比较有意思的
•   说实话，其实本不想买这本书的，买了一本《程序员面试宝典》，提交订单提示还需购买1.5才免邮费，然后就买了这本⊙﹏⊙b汗
•   个人逻辑思维较差，看起来有不那么容易 但是慢慢的觉得很有趣 希望有助于锻炼自己的思维能力
•   快速的阅读了几页 它可以指导我们进一步完善自己以前编写代码的逻辑
•   适合对计算机感兴趣的读者。
•   给同学买的，说是适合于考公务员的同学们来阅读
•   书的质量不错，物流也挺快
•   推荐，好书，很好
•   这本书不错，又很多策略方面的问题，对面试的感觉很实用。缺点就是每篇追加的问题没有答案。
•   例子很难，不过也很有意思
•   书的内容有分量，适合于拓展思维
•   可以看着玩，注意是逻辑试题，没有编程的，要注意啊
•   好书，很有启发，非常喜欢，会好好研读
•   还没看，应该不错， 对逻辑推理应该有提高
•   看了书的介绍很期待，但真正到手后不符合自己的口味，有点失望。
•   有的答案不怎么详细啊！！！
•   13年新出版的书封皮烂的像是放了十年一样。
•   内容好难啊，不知道面试有用吗
•   没有想象中的好,内容比较乱,有的有解答,有的没有,解答很简略,不太适合面试
•   没有足够细致的讲解，没事儿的时候，做着玩儿还可以，但是中国的面试官现在基本没有拿这个出题目的，不知道是因为太难，还是因为他们没有注意到这本书，基本一些面试算法的书上的内容，基本上都被考烂了
•   书而已嘛,只要不是破的就该好评.只是有点看不懂
•   每种问题从 基本开始，然后 升级 ，关键是问题本身很有锻炼思维的特点
•   里面的东西比我想象的要麻烦
•   第一页就有装订错误，但是这种书不是收藏之用的，所以就懒得去换了。
•   听起来是面试逻辑题，但如果不用笔，光用脑袋想，还是很有些难度的，里面的每个问题都很有意思，而且不简单。
•   书的内容不错，就是要花点时间自己动动脑子，应该会有提高。
•   如题，但是内容很充实，我这种低智商一天看一页就可以了
•   可以当作手边的闲书看，没事就拿起来看看。
•   书本的知识体系和架构是很好的
•   好书，推荐看一下
•   一本可以锻炼思维的好书。
•   程序员可以学习一下
•   东西不错 价格也还行
•   还没看~~~看完回来评
•   看了网上很多面试题，发现自己