程序员面试白皮书

董飞
之前在自己准备面试的时候整理过一些准备面试的方法。经过一段时间的工作，也有了面试别人的经历，对公司需要怎么样的candidate有了更好的理解。总感觉这些零碎的信息散落地放着有些浪费，一直想整理一下分享给大家，帮助更多的人。终于，在一帮志同道合的小伙伴的帮助下，我们把大家各自的心得体会系统性地梳理成册，并在网络平台发布了这本电子书（iPhone, iPad平台）：程序员面试白皮书
(An Ultimate Guide to Coding Interviews)。
itunes.apple.com/us/boo
，如有任何建议意见，请不吝赐教问题邮箱（[email protected]
）。


程序员面试是对于面试者计算机知识的全面检测，因此，关于计算机诸如网络，操作系统，编译器，算法，数据结构等等各个领域的系统性学习不可或缺。但是考虑到面试的局限性，诸如时间限制，面试官对于面试者的熟悉程度等等，在白板(或者白纸)上写程序解决一些算法问题成为面试官较为青睐的方法之一。由于该面试方法比较机械，相对容易准备，也最适合总结一些方法论，所以我们写这本书的目的就在于传授白板写代码的准备技巧，帮助大家通过面试。作为一本工具书，我们希望它能创建一个实际的、可操作的面试方法论教程，提供一条快速熟悉技术面试题目的捷径，并且针对不同类型的题目，归纳总结解题方法。正如参加考试一样，关于考试技巧的书籍并不能让一个完全不懂的人通过考试，但是可以使得基础合格的人如虎添翼，大大增加通过考试的几率。这就是这本书的全部存在意义。


其实市面关于程序员面试的参考书也不少，但是我们认为这些书的关键问题在于它们大多是教你“怎么做”，但很少涉及“为什么这么做”。于是乎，读者往往会觉得书中的解法十分精妙，但是在面试的时候完全想不起来用哪种方法解决问题。其本质原因在于，这些参考书代替你做了最关键的一步：判断用什么方法解决当前的问题。

至于面试题来源，来自于网上的自由技术讨论，开放的在线题库，或其他面试参考资料，大家去Glassdoor, Geeksforgeeks, Careercup, Csdn blog上面都可以搜到。
我在这里就精选两道作为代表讲解一下。

1. 算法题案例：

Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible. For example, if the input string is "applepie" and dictionary contains a standard set of English words, then we would return the string "apple pie" as output.
简单说就是给定字典，对无空格的短语切词。这里可以考虑一些情形，你先问面试官：
如果输入的刚好是字典中的一个单词怎么办？（特殊例子）
我是不是只要考虑切成2个单词的情况？（不仅仅2个，但可以从2个开始）
如果输入的根本无法切分呢？（就返回空）
有没有一些单词拼写或者助词缩写形式（如im = i am，如果在字典中没有就不算)
如果可以切分多种合理的词？（返回一种就行）
要不要用一些字典的高级数据结构（trie, heap, suffix tree)（不需要理解）
字典有哪些操作的方式？（就是词的查询）
字典有多大？（正常英语词典，内存足够）
这些问题时帮助你理解和简化题目，也考察出你对算法和数据结构的熟练度。
简单化的方案：
就把它拆成两个词。分别验证前后是否在字典中。这个直接简单，也让面试者心里有底。下面是python的代码实例：
def segment_string(input, dict): len = len(input) for i in range(len): prefix = input[0:i+1] if prefix in dict: suffix = input[i+1:] if suffix in dict: return prefix + " " + suffix return ""
下面考虑怎么推广到一般的情况，有种递归的办法，在上面的基础上稍微改动一下
def segment_string(input, dict): if input in dict: return input len = len(input) for i in range(len): prefix = input[0:i+1] if prefix in dict: suffix = input[i+1:] seg_suffix = segment_string(suffix, dict) if seg_suffix != '': return prefix + " " + seg_suffix return ''
给出解答还要分析复杂度，就是所谓的 大O分析，这种递归的做法很多人不清楚怎么计算，但你可以想象 如果单纯想 字典里面只有一个字符组合a，aa, aaa... 输入也是aaa... 你就发现就是全组合的可能性，答案O(2^N)。
还可以做的更好么？
如果大家清楚动态规划或者memoization，可以进一步节约计算，这是一种空间换时间的技巧，但大家能思考它的复杂度吗？如果我说是O(N^2), 大家有办法去证明吗？
memory = {} def segment_string(input, dict): if input in dict: return input if input in memory: return memory[input] len = len(input) for i in range(len): prefix = input[0:i+1] if prefix in dict: suffix = input[i+1:] seg_suffix = segment_string(suffix, dict) if seg_suffix != '': memory[input] = prefix + " " + seg_suffix return prefix + " " + seg_suffix memory[input] = '' return ''
这道题目就展示了不同层次的优化，首先是一道有现实意义的问题，就是做单词自动识别，它也不需要特定领域的知识，当然递归你还是要知道的。在面试过程中，我可以给你一些提示，但最终你走到哪一步，就看你的能力。并且如果你实现了优化解法，我可以继续问当字典大到内存放不下如何？
2. 设计题案例：
Design the data structures for a very large social network and an algorithm to show the connection between two people.
解题分析：首先我们考虑数据量不大的情况，即所用用户数据储存在同一部机器上。要查询两个用户之间的联系无非就是广度优先搜索。进一步地，如果数据量很大，那么我们需要用多台机器储存对象。不妨采用与上题类似的思路：引入另一层hash进行数据分流，建立对象与储存该对象的机器之间的映射。通常用户都有一个唯一的ID，我们可以利用ID的前几位数字，决定将该用户数据存放在哪台机器上。这样，广度搜索的查询流程变为：
1. 获得用户的好友ID列表
2. 根据ID获得机器
3. 访问机器获得对应的用户节点
4. 进行下一步递归
应用该方法我们需要注意一下问题：
1. 访问另一台机器的成本可能比较高，因此应该尽量把该机器上的所有相关数据一次性读取完毕。
2. 广度搜索需要记录某个节点是否已经访问过以避免循环访问，我们可以另外开辟一个hash table记录已经访问的用户节点。
3. 注意合理地简化问题：如果两个用户之间需要多于3重关系才能联系上，我们可以把他们归类为“陌生人”。那么，我们可以将关系链限制在3重关系以内，以减少搜索成本。
结语
其实面试题千变万化，在网上也可以找到讨论；但方法论比具体的解答更重要，在工作中也很难遇到你之前背过的‘答案’，如果你只是死记硬背还是不能进行创新和解决问题。我还是多推荐书籍，让大家去感悟吧。
推荐书籍
程序员面试白皮书：前言部分
编程之美
：微软亚洲研究院出版，很多好玩的例子。

编程珠玑(第二版) ：经典小册子。Jon Bentley 世界著名计算机科学家，被誉为影响算法发展的十位大师之一，以其独有的洞察力和创造力，引导读者理解这些问题并学会解决方法。
Cracking the Coding Interview
: 编程面试的复习指南。

打造Facebook
: 关于如何打造团队的一些干货分享。

梦断代码
:让你感同身受什么叫做软件的本质复杂性。

数学之美
: 吴军力作，讲解Google产品中的数学原理。

UNIX编程艺术
: Unix系统领域中的设计和开发哲学、思想文化体系、原则与经验，由公认的Unix编程大师、开源运动领袖人物之一Eric S. Raymond倾力多年写作而成。

代码之美:每章中的漂亮代码都是来自独特解决方案的发现，而这种发现是来源于作者超越既定边界的远见卓识，找出令人叹为观止的问题解决方案。
程序员的思维修炼
：学习方法，关于大脑思维方式或认知潜能的开发的。

Algorithms For Interviews
:题目较新。

算法设计手册： 设计实用且高效算法的全面指导书。
继续阅读
阅读原文