《程序员面试逻辑题解析》书评

一本为程序员量身打造的面试逻辑题宝典——《程序员面试逻辑题解析》

近年来，越来越多的硅谷科技型公司开始采用谜题面试的方式。这些公司感兴趣的并不是正确答案，而是应聘者解决问题的方式和能力。在国内，无论是刚毕业的学生，还是正在找工作的程序员，在应聘程序设计、软件开发方面的工作时，招聘方总会安排笔试以考查其程序设计、逻辑分析能力。无论你是为工作面试而备战，还是喜欢挑战自我，本书都将带你踏上解决谜题的旅程。本书共分为3个部分，第一部分是从有趣且锻炼头脑的谜题入手，继而给出解题思路和详细答案，通过“热身问题”及其解答方案给大家提供充分的思考空间。第二部分综合了不同类型的谜题。神秘的第三部分带领大家不断历险，开动脑筋，解决大量密码及银行账户等方面的信息。这里举一个看似简单但应用很广泛的例子。“有一项赛事，共12支校队参加，简便起见，记作A、B、C、D、E、F、G、H、I、J、K和L。他们将在连续的11天内，在6块场地上举行比赛。每个队都必须和其他11队比赛一次。每个队每天只打一场比赛。有没有可能编排一个11天的赛程，同时满足以上各条件？”请大家仔细研究一个这个题目，如果实在想不出解答方案，不妨参见本书2.5节。值得一提的是，该书作者Dennis Shasha同样是畅销书《奇思妙想：15位计算机天才及其重大发现》的作者，图灵盼盼姐曾对他进行过专访，参见http://www.ituring.com.cn/article/12519。他集耶鲁大学理学学士、雪城大学理学硕士和哈佛大学哲学博士学位于一身。研究领域相当广泛，包括生物计算（包括实验性设计）、模式识别以及树和图标的查询、时间序列的模式探索、加密文件系统等。让我们跟随大师的指引，循着知名公司的面试思路，一起踏上探究谜题解答方案的旅程。下述文字译自amazon.com。提高脑力的饕餮盛宴，高度推荐！作者：PC一直以来，我对Shasha博士在Dr. Dobb's Journal上的数学谜题专栏都情有独钟。所以偶然间发现本书的时候，我欣喜若狂。总的来说，我非常喜欢本书中的谜题。谜题的描述一般都不太长（也就一两页），“热身问题”及其解答指明了解题的思路。你可以花5~10分钟来读读题、做做“热身问题”，不过接下来的一天甚至是几周可能都得用来解决真正的谜题了。其中有些问题很难呦，对我来说，甚至是“不可能”完成的任务。有些读者认为一些描述语言不是很清晰（比如说“冰上历险”那一节，直到看了“热身问题”的解答，我才真正理解问题），对于这一点，我表示同意。不过，由于本书是面向程序员一类的读者的，所以我猜相较于一些读者所期许的数学问题，本书更侧重于谜题方面。想象得出，作者开设的编程难题解析的课程是多难。很难想象的是其间的工作量，更难想象这门课是多么其乐无穷。有用的算法实例作者：K.Wang阅读本书之前，我真的不知道如何使用动态规划算法。而“最优包装”仅用一页纸的篇幅就教会了我。简单而优雅的解答方案让我一年后仍记忆犹新。令我惊讶的是，一个再普通不过的问题是这样从一个不同的角度用古老的算法来解决的。与其他谜题类图书不同，本书独具一格，专为程序员量身打造。个人认为经常做谜题能够改善大脑功能。本文选自图灵社区文章http://www.ituring.com.cn/article/16799

1.1 甜食爱好者个人解答思路

使用过的方法：罗列出的等式，解方程组（线性代数知识）。文中解决思路文字过多，个人尝试将其抽象化。n块蛋糕时，Marie有 M(n)块，Jeremy有J(n)块。(n-1): M(n-1)，J(n-1)。新增加一块时，分为f和(1-f)，f>(1-f)。边界条件：Marie先挑 = Jeremy先挑对于M：M(n-1)+f = (n-1)/2 + (1-f), M(n) = M(n-1)+f 对于J:J(n-1)+(1-f) = (n-1)/2 + f, J(n) = J(n-1)+(1-f) solve the equations, we get:M(n) = M(n-1)/2 + (n+1)/4J(n) = J(n-1)/2 + (n+1)/4因此，二者差别在于上一次蛋糕相差数的1/2然后就是非常简单的递归。2块相差 1/2(3/4, 5/4)块。3块相差 1/4块。……这样子避免了比较难解的某方程。