第 4 章 面试之前
积累相关经验 构建人际网络 写好简历
4.1 积累相关经验
录用与否主要取决于你在面试中的表现，而简历和过往经验则决定你有没有面试机会。你应该想方设法提升自己的技术水平。不管是应届毕业生还是专业人士，拥有额外的编程经验都会让你受益匪浅。在校生可以采取下面这些举措。选修有大作业的课程：如果你还是学生，请不要避开那些有大作业的课程。将来，你可以把这些项目经历都写在简历上，这会大幅提高得到顶尖科技公司面试机会的几率。当然，这些项目与实际情况联系越紧密，效果就越好。找一些实习生工作：就算你是大学新生，也有机会得到相关的专业经验。大一、大二的学生可以考虑参加诸如“微软探索者”和“谷歌编程夏令营”这样的活动。如果得不到类似的机会，进入创业公司历练一下也不错。开拓一些业务或项目：绝大多数公司都青睐富有创业精神的人。此举不仅可以培养一些技术经验，而且同时也能展示你的主观能动性和把事情做好的能力。你可以利用周末和休息时间写个软件。要是认识学校教授，不妨试着请他予以“资助”，以便你将自己的工作变成一项独立研究。另一方面，专业人士可能早已累积好相应资本，准备跳槽进入他们梦寐以求的公司。比如，谷歌的开发人员可能已经攒够经验，有机会跳槽到Facebook工作。不过，如果你想从不知名的小公司跳到科技巨头公司，或者从测试岗位转成开发人员，请参考以下这些建议。多承担一些编程职责：在不透露跳槽意向的前提下，你可以向经理表达自己想在编程上接受更大的挑战。尽可能地参与一些重大项目，并多多使用对自己以后有利的技术，将来它们会成为简历上的亮点。另外，简历上也要尽量多列举这些与编程相关的项目。善用晚上和周末的闲暇时光：如有空闲时间，可以试着构建一些手机应用、网页应用或桌面软件。这样，你就有机会接触到时下流行的新技术，从而更契合科技公司的要求。这些项目经验都可以写到简历上，没有什么比“为兴趣而工作”更能打动招聘人员的了。总而言之，公司最青睐的人才必须具备两大特性：一是天资聪颖，二是扎实的编程功底。要是你能在简历上充分展示这两点，面试机会就唾手可得了。此外，你应当提前规划好职业发展路径。如果打算转型成为管理者，哪怕当下应聘的仍是开发岗位，也应现在就想方设法培养自己的领导才能。
4.2 构建人际网络
你或许听说过很多人靠朋友推荐找到了好工作。不过，你可能想不到，还有更多人是通过朋友的朋友找到工作的。这真的很有道理。用极客的话来说，你有N个朋友，也就意味着你有N2个朋友的朋友。那么，在你找工作时这个数字意味着什么呢？这意味着，不管是直接联系人还是拐弯抹角的关系，对你找工作都很有帮助。什么叫好的人际网络好的人际网络不仅意味着你广交朋友，还要与他们保持紧密的联系。这句话看似矛盾，实则要辩证地看待。广度：你的人际网络中不仅要有业内技术人士，而且最好还能涵盖各行各业的人才。比如说，结交一位会计朋友会对你的职业生涯帮助很大，因为他很可能在其他领域有很多朋友。有时候，其中有些人可能就想认识像你这样的技术人才。请抱着开放的交友态度去对待他人。深度：通过自己的密友来结交新朋友是个不错的方法，总好过让不太熟的人为你牵线搭桥。此外，人们会对那些所谓的“老油条”和“交际花”避之唯恐不及，觉得这些人太虚伪了。因此，尽量与朋友保持真诚和深厚的关系。其中的微妙之处就在于找到平衡点，你认识的人当然越多越好，但要确保自己待人真诚、开放。如果只是热衷于收集大家的名片，那你最终往往只会一无所获。如何构建坚实的人际网络有些人认为，我们应当走出家门，去结识更多人。这么说也有道理。但是去哪里呢？而且，如何才能将“点头之交”发展成好朋友呢？以下这些建议或许能给你一些启发。通过Meetup.com这样的社交网站或校友网来获取你感兴趣的活动资讯。记得带上你的名片。如果你暂时没有工作或还是学生，那就自己印些名片。主动跟人打招呼。也许你生性胆怯，不敢迈出这第一步。但请相信我，没人会拒绝你的友好之举，甚至有些人还会欣赏你的自信。话说回来，最坏能坏到什么地步呢？他们不喜欢你，不会与你结交，从此和你老死不相往来吗？大大方方地聊你的兴趣，并和人们谈论他们的兴趣。如果他们正在运营创业公司，或是从事其他你也感兴趣的活动，不妨邀请他们一起喝咖啡继续畅谈。活动结束后，你可以在linkedIn上把他们加为好友，或者给他们发邮件。当然，更好的方式就是邀请他们一起喝咖啡，这样你们就会有充足的时间来畅谈他们的创业公司，或是双方都感兴趣的话题。最重要的是乐于助人。经常助人一臂之力，你就会给人留下慷慨大方、友好和善的印象。那些乐善好施的人往往也会得到更多帮助。切记，不要只局限于现实生活中的社交。在这个信息爆炸的时代，社交还可以拓展到网络上，通过博客、微博、Facebook和电子邮件结交朋友。当然，也不要太“走火入魔”沉迷于在线社交，你得努力建立实实在在的人际关系。
4.3 写好简历
简历筛选标准与面试标准并无太大差别，也是看你是否又聪明又会写程序。这意味着你在准备简历时应该突出这两点。提到自己喜欢打网球、旅游或玩魔法牌可没什么用。在罗列这类无关紧要的爱好之前，务请三思，宝贵的篇幅应该用来展示自己的技术才能。
1. 简历篇幅长度适中
在美国，人们会建议工作经验不足10年的求职者将简历压缩成一页；超过10年的，至多用两页。为什么呢？主要有两大理由。招聘人员浏览一份简历一般只会用20秒钟左右。要是你的简历言简意赅恰到好处，招聘人员一眼就能看到。废话连篇只会模糊重点，扰乱招聘人员的注意力。有些人遇上冗长的简历连看都不看。你真的想冒这个风险，让别人直接扔掉你的简历吗？如果看到这里你还在想，我工作经验太丰富了，一页篇幅根本放不下怎么办？相信我，你可以的。一开始大家都会这么说。其实，简历写得洋洋洒洒并不代表你经验丰富，反而只会显得你完全抓不住重点。
2. 工作经历
简历不是也不应该是关于工作经历的编年史。比如，卖过冰淇淋跟聪明与否或代码写得怎么样关系不大。你应该只列举那些相关的工作经验。列举要点在描述工作经历时，请尽量采用这样的格式：“使用Y实现了X，从而达到了Z效果。”比如，下面这个例子：“通过实施分布式缓存功能减少了75%的对象渲染时间，从而使得用户登录速度加快了10%。”下面还有一个例子，描述略有不同：“实现了一种新的基于windiff的比较算法，系统平均匹配精度由1.2提升至1.5。”尽管不是所有经历都能套用此句型，但原则无二：描述做过的事情、怎么做的，以及结果如何。理想的做法是尽可能地量化结果。
3. 项目经历
在简历中列出“项目经历”这一部分会让你看起来很专业。对于大学生和毕业不久的新人尤其如此。简历上应该只列举2到4个最重要的项目。描述项目要简明扼要，比如使用哪些语言和技术。你也可以加上一些细节，比如该项目是个人独立开发还是团队合作的成果，是某一门课程的一部分还是自主开发的。当然，这些细节不一定放到简历上，除非能让简历更出彩。项目也不要列太多。很多求职者就犯过这样的错误，在简历上一股脑儿列出先前做过的13个项目，鱼龙混杂，效果反而不佳。
4. 编程语言和软件
软件一般说来，“熟悉微软Office”之类不必列入简历。这应该是地球人的必备技能，列出来反而会模糊重点。你应该列出那些能反映自身技术水平的软件或系统，不过坦白说，这么做用处也不大。编程语言列举编程语言确实是件难事。我们到底应该列出自己用过的所有语言，还是只列那些用得最顺手的语言呢？我建议采用下面这个折中办法：列出你用过的主要语言，后面加上熟练程度。比如像下面这样：编程语言：Java，C++，Javascript。
5. 给母语为非英语的人及国际人士的建议
一些公司可能会因为小小的笔误就扔掉你的简历，所以请至少找一位以英语为母语的人来帮你审阅简历。此外，申请美国的工作时，简历中不要包含年龄、婚姻状况或国籍等。公司并不想看到这些个人信息，因为怕惹上不必要的麻烦。
第 5 章 行为面试题
准备工作 如何应对
5.1 准备工作
行为面试题的考察有各种各样的原因。人们可以通过这些问题来了解你的个性，或是更深入地掌握你的履历，又或者缓和一下面试的紧张气氛。不管怎样，这个部分很重要，而且有办法做好准备、有的放矢。准备工作行为面试题一般是这么问的：“说说你曾经……”面试官可能还会要求你列举并说明具体的项目或岗位。我建议你先按如下格式拟定一份“准备表格”：常见问题 项目1 项目2 项目3 项目4 最难的部分 有什么收获 最有意思的部分 最难解的bug 最享受的过程 与团队成员的冲突第一行可以列举你在简历中提到的主要事项，比如项目、职位或活动。第一列应该写一些常见问题：你最享受和最不喜欢的过程、最难的部分、从中学到的经验、最难解的bug，等等。然后，在对应单元格里写下相应的小故事。当面试官问及项目有关的问题时，你就能回想起这些小故事，从容应对。记得在面试前复习这份表格。另外，建议大家将小故事浓缩成几个关键字，以便填到单元格里。这样一来，这份表格用起来就会更顺手，方便记忆。电话面试时，最好将这份表格摆在自己跟前。把每个小故事都概括成几个关键字，更容易记忆，自然而然就能把整个故事串起来，比死记硬背一段文字要轻松得多。你还可以将这份表格扩展成一系列“软问题”，比如团队冲突、项目失败的经历以及你需要说服团队成员的事例。对于那些不是专职开发的职位如技术主管、PM或测试人员而言，这些都是很常见的面试问题。如果你刚好要申请其中一个职位，建议你针对这些“软问题”再准备一份表格。在回答问题时，你不只是在讲述一个与该问题密切相关的故事，更是在向别人展现自我。所以，请用心思索每个故事都能体现出自己的哪些特性。
你有哪些缺点被问及自己有哪些缺点时，回答不要太空泛！诸如“我最大的缺点就是工作太努力了”的回答，反而会显得你傲慢自大，并且不愿正视自己的不足。没有人喜欢与这样的人共事。因此，你应该提到真实、合乎情理的缺点，然后话锋一转，强调自己如何克服这些缺点。比如：“有时候，我可能对细节不够重视。好的一面是我反应迅速、执行力强，但不免会粗心大意而犯错。有鉴于此，我总是会找其他同事帮忙检查自己的工作，确保不出问题。”
2. 项目中最难处理的问题是什么
当面试官问到这个问题时，请不要泛泛地回答“我得学习很多新的编程语言和技术”。除非你实在是无话可说，否则这种回答似乎是在强调：该项目并不是很难，没什么棘手的问题。
3. 你应该问面试官哪些问题
大多数面试官都会给你提问的机会。有意无意间，你提问的质量也会成为他们评估你的整体表现的因素之一。也许你会在面试过程中临时想到若干问题，但你还是可以并且应该事先准备好问题。对公司和团队做些调研，有助于你准备问题。问题可以分成以下三大类。真实的问题也就是你真的想知道答案的问题。下面是对多数求职者有用的一些问题点。“你每天有多少时间花在写代码上？”“你一周要开几次会？”“整个团队中，测试人员、开发人员和项目经理的比例是多少？他们是如何互动的？团队怎么做项目规划？”这些问题有助于你较好地了解公司的工作环境和日程安排。有见地的问题有见地的问题可以充分反映出你的编程水平和技术功底，同时，还能显示你对该公司或其产品的兴趣。“我注意到你们使用了X技术，请问你们是如何处理Y问题的？”“为什么你们的产品选择使用X协议而不是Y协议？据我所知，虽然X有A、B、C等几大好处，但因为存在D问题，很多公司并未采用该协议。”只有事先对该公司做过充分调研，才问得出这类有深度的问题。富有激情的问题这些问题旨在展示你对技术的热忱。要让面试官知道你热衷学习，将来能为公司的发展做出很大贡献。比如：“我对可扩展性很感兴趣。请问你从事过分布式系统方面的工作吗？有哪些机会可以学习这方面的知识？”“我对X技术不是太熟悉，不过听上去是个不错的解决方案。你能给我多讲讲它的工作原理吗？”
5.2 如何应对
如前所述，面试官喜欢在面试开始和结束时与你谈天说地或聊聊“软技能”。他们通常会就你的简历问些问题，或者泛泛地提问，此时你也可以问一些和公司有关的问题。这个面试环节除了缓和气氛，也是意在了解你。回答这类问题时，切记以下几个建议。
1. 力求具体，切忌自大
骄傲自大是面试大忌。可是，你又想给面试官留下深刻的印象。那么，怎样才能很好地秀出自己的实力而又不显自大呢？那就是回答问题要具体！具体也就是只陈述事实，余下的留给面试官自己解读。请看下面这个例子。一号求职者：“我几乎包揽了团队中所有累活和难活。” 二号求职者：“我实施了文件系统，因为XXXX等原因，这是整个项目中最难的一部分。”二号求职者的回答不仅听起来更令人印象深刻，而且也不会显得骄傲自大。
2. 省略细枝末节
当求职者就某个问题喋喋不休时，不熟悉该主题或项目的面试官往往听得一头雾水。所以，请省略细枝末节，只谈重点。换言之，建议你这么回答：“在研究最常见的用户行为并应用Rabin-Karp算法1后，我设计了一种新算法，在90%的情况下搜索操作的时间复杂度由O降至O。您要是感兴趣的话，我可以详细说明。”该回答言简意赅，重点突出；要是面试官对实现细节感兴趣，他会主动询问。1 Rabin-Karp算法是由Michael O. Rabin和Richard M. Karp于1987年提出的字符串匹配算法。——译者注
3. 回答条理清晰
回答行为面试题有两种常见的组织方式：主题先行法与S.A.R.法2。你可以分别或组合使用这两种技巧。2 S.A.R即Situation、Action与Result的缩写，情景、行为与结果。——编者注主题先行主题先行即开门见山、直奔主题，回答简洁明了。比如，面试官：“讲一讲你必须说服一群人作出大幅调整的事例。” 求职者：“好的，我在学校提出过一个让本科生互相授课的想法，并成功说服学校采纳该建议。起初我们学校规定……”主题先行法可以快速抓住面试官的注意力，让他了解事情梗概。此外，假如你有滔滔不绝的倾向，这也有助于你不偏离主题，因为你早已开门见山地点明主旨。S.A.R.S.A.R.法是指先描述情景，然后解释你采取的行动，最后陈述结果。示例：“说说你与某位‘刺头’队友相处的事例。”情景：在操作系统课的大作业中，我被安排与其他三个人合作。其中两人都很卖力，但另外一个人做的不多。开会时他总是沉默寡言，也极少参与邮件讨论，只是很吃力地完成分配给他的模块。行动：有一天课后，我把他拉到一边讨论这门课程，然后谈起我们的大作业。我坦诚地询问他对大作业的感受，以及他最感兴趣的模块。他建议让他处理最简单的几个模块，并承诺会完成最后的总结报告。我意识到他其实一点都不懒——他只是对这项大作业感到很困惑，并且缺少自信心。此后，我开始与他合作，进一步细分组件模块。此外，在工作中我还经常称赞他以增强他的自信心。结果：他依然是我们团队最弱的一员，但是进步很大。他及时完成了分配给自己的任务，参与讨论也更积极。后来在另一个大作业中，我们合作得非常愉快。切记，描述情景与结果务必言简意赅。面试官一般不需要太多细节就知道来龙去脉，实际上，细节过多反而会令他们摸不着头脑。采用S.A.R.法简明扼要地描述情景、行动和结果，可让面试官快速了解你是如何施加影响的，起到了什么作用。
第6章 技术面试题
技术准备 如何应对 算法题的五种解法 怎样才算好代码
6.1 技术准备
既然你买了这本书，说明你已经为技术面试做了不少准备。干得好！即便如此，准备方式也有好有坏。许多求职者只是通读一遍问题和解法，囫囵吞枣。这好比试图单凭看问题和解法就想学会微积分。你得动手练习如何解题。单靠死记硬背效果不彰。
1. 如何练习
就本书的面试题，请参照以下几个步骤。尽量独立解题。也就是说，要试着实战演练解题过程。许多题目确实很难，但是没关系，不要怕！此外，解题时还要考虑空间和时间效率。多问问自己 ，能否通过降低空间效率来提高时间效率，或者相反。在纸上编写算法代码。之前你一直在计算机上编写代码，习惯了由此带来的诸多便利。不过，在面试中，你可享受不到语法高亮、代码补全或编译构建的种种好处。不妨在纸上编写代码模拟面试时的情景。在纸上测试代码。也就是要在纸上写下一般用例、基本用例和错误用例等。面试中就得这么做，因此最好提前做好准备。将代码照原样输入计算机。你也许会犯一大堆错误。请整理一份清单，罗列自己犯过的所有错误，这样在真正的面试中才能牢记在心。此外，模拟面试也非常有用。CareerCup.com提供了与微软、谷歌和亚马逊等公司员工进行模拟面试的机会，当然，你也可以跟朋友一起演练，轮流当面试官给对方做模拟面试。你的朋友不见得受过什么专业训练，但至少还能带你过一遍编码或算法面试题。
2. 你需要掌握的知识
大多数面试官都不会问你二叉树平衡的具体算法或其他复杂算法。老实说，离开学校这么多年，恐怕他们自己也记不清这些算法了。一般来说，你只要掌握基本知识即可。下面这份清单列出了必须掌握的知识：数据结构 算法 概念 链表 广度优先搜索 位操作 二叉树 深度优先搜索 单例设计模式 单词查找树 二分查找 工厂设计模式 栈 归并排序 内存队列 快速排序 递归 向量/数组列表 树的插入/查找等 O时间 散列表对于上述各项主题，务必掌握它们的具体实现和用法、应用场景、空间和时间复杂度如何等。对于其中的数据结构和算法，你还要练习如何从无到有地实现。面试官可能会要求你直接实现一种数据结构或算法，或者对其进行修改。不管怎样，你越是熟悉具体实现，把握就越大。其中，散列表一项特别重要。你会发现，解决面试问题时，经常会用到散列表。
3. 2的幂表
有些人已经把下面这张表背得滚瓜烂熟，如果你还没有的话，面试前一定要背下来。回答可扩展性问题时，这张表用处很大，借助它可以快速算出一组数据占用多少空间。2的幂 准确值 近似值 X字节转换成MB、GB等 7 128 8 256 10 1024 一千1K 16 65 536 64K 20 1 048 576 一百万 1MB 30 1 073 741 824 十亿 1GB32 4 294 967 296 4GB 40 1 099 511 627 776 一万亿 1TB有了这张表，就可以做速算。例如，一个将每个32位整数映射为布尔值的散列表可以把一台计算机的内存填满。在接受互联网公司的电话面试时，不妨将这张表放在跟前，也许能派上用场。
4. 需要知道C++、Java或其他编程语言的细节吗？
我个人不会问这类问题，不过许多面试官确实会问。对于微软、谷歌和亚马逊等大公司，我不太担心这些问题。如果你在简历上提到自己熟悉某种语言，那你自然应该掌握这种语言的基本概念。不过，我还是建议你在数据结构和算法方面多下工夫。参加小公司和非软件公司的面试，这些问题可能更显重要。在CareerCup.com上搜索你心仪的公司再作决定。如果找不到那家公司，那就找一家类似的公司作为参照。一般而言，创业公司更看重与他们使用的编程语言相关的技能。
6.2 如何应对
面试绝非易事。
要是没能立刻答出所有问题或某个问题，也没关系！实际上，根据我的经验，在我面试过的120多人中，大概只有10个人能立即答上我经常问的问题。因此，碰到棘手的问题，不要慌张。只管大声说出你准备怎么解决。向面试官说明你会如何处理这个问题，这样面试官就不会误以为你被难住了。另外，还有一点：只有面试官点头认可，你才算是真正解决了问题！我指的是，在给出算法后，你就要开始考虑它可能存在的问题。边写代码，边查缺陷。如果你和我面试过的其他110名求职者一样，那就免不了要犯一些错误。解决技术面试题的五步法解决技术面试题可采取下面的五步法。向面试官提问，以消除疑义。设计一种算法。先写伪码，但务必告诉面试官接下来会写“真实的”代码。写代码要不紧不慢。测试写好的代码，仔细修正每一处错误。下面我们将逐一探讨上述五个步骤。
第一步：提问技术面试题看似清晰明确实则模糊不清，因此务必多提问题以澄清所有存疑之处。问到最后，你可能会发现，这个问题与你最初预想的截然不同——也许更难，也许更简单。实际上，许多面试官会特意考察你能否提出好问题。好问题大概是这样的：数据类型是什么？有多少数据？解决这个问题需要什么假定条件？用户都是谁？示例：“设计一种列表排序算法。”问题：具体是哪种列表？数组还是链表？回答：数组。 问题：数组里存放的是什么？数字、字符、还是字符串？回答：数字。 问题：这些数字都是整数吗？回答：是的。 问题：这些数字来自何处？是身份证号码还是别的什么数值？回答：顾客年龄。 问题：总共有多少顾客？回答：大概一百万。现在我们要解决一个与最初理解很不一样的问题：对一个包含一百万个整数的数组进行排序，这些整数在0到130之间。该怎么解决这个问题呢？只需创建一个包含130个元素的数组，然后计算每一个元素出现的次数。
第二步：设计算法算法的设计可能会很难，不过下一节的“算法题的五种解法”可以帮上大忙。在设计算法时，记得问问自己以下几个问题：该算法的空间和时间复杂度如何？ 碰到大量数据会怎么样？ 你的设计会引发其他问题吗？例如，你设计了一种二叉查找树的变体，那么该设计是否会影响插入、查找或删除时间？ 如果还有其他问题或限制，你会做出正确的取舍吗？对于哪些场景，这一取舍可能不是最优的？ 如果面试官指定特定数据，你能否善用该信息？面试官给你特定信息往往是有原因的。先给出蛮力解法，这么做当然是允许的，甚至推荐这么做。然后，在此基础上不断优化。很显然，面试官总是期望你能给出尽可能最优的解法，但这并不意味着一开始就得给出完美无瑕的答案。
第三步：编写伪码先写伪码有助于你理清思路，减少犯错的次数。不过，务必先跟面试官打声招呼，你会先写伪码，紧接着就会编写“真实的”代码。许多求职者选择写伪码，意在“逃避”编写真实代码，你肯定不愿与那些求职者为伍。
第四步：编写代码编写代码不要太仓促；实际上，太仓促很可能会害了你自己。写代码时只管放松步调，做到有条不紊，丝丝入扣。另外，切记以下忠告。多用数据结构：根据实际情况选用合适的数据结构，或者自己定义数据结构。例如，有个面试题涉及从一群人中找出年龄最小的，不妨考虑定义一个数据结构Person表示一个人。这样也能展现出你注重良好的面向对象设计。写代码不要太杂乱：这看似小事一桩，实则很重要。在白板上写代码时，尽量从左上角而不是中间开始写。这样才有足够的地方从容答题。
第五步：测试没错，自己写的代码自己测试！考虑测试以下用例。极端用例：0、负数、空值、最大值、最小值。 用户错误：用户传入空值或负数会出什么问题？ 一般用例：测试正常用例。如果你的算法很复杂或涉及大量数值操作，建议边写代码边测试，而不是写完代码再测试。发现错误时，务必先弄清楚出现缺陷的原因再作修改。你肯定不希望自己在面试官看来像只热锅上的蚂蚁一样团团乱转，这里修修那里补补。举个例子，我就碰到过这样的求职者，他发现函数碰到某个特定值返回true而非正确的false，于是直接修改返回值，接着验证函数能否工作。这或许可以修正那种特定情况下出现的问题，但无疑又会滋生新的问题。当你察觉代码中存在的问题时，务必三思而后改，先理清代码失效的原因。这样你才能写出既漂亮又整洁的代码，也会越写越快。
6.3 算法题的五种解法
要解决棘手的算法问题，世上没有什么不二法门，不过下面介绍的几种方法可能管用。常言道熟能生巧，题目练习得越多，就越容易确定该采用哪种方法来解决问题。另外，下面这五种方法可以“混搭”使用。也就是说，施以“简化推广法”后，还可以接着尝试“模式匹配法”。
方法一：举例法我们先从你可能熟悉的“举例法”开始，也许你从未听过这种叫法。“举例法”是先列举一些具体的例子，看看能否发现其中的一般规则。示例：给定一个具体时间，计算时针与分针之间的角度。下面以3点27分为例。确定3点的时针位置和27分的分针位置，我们可以画出一个时钟。在下面的解法中，h表示小时，m表示分钟。同时，我们假定h的范围是0~23。从这些例子可以得出以下规则。分针的角度：360 × m / 60； 时针的角度：360 × / 12 + 360 × × ； 时针和分针之间的角度： % 360.简化上述式子可以得到 % 360。
方法二：模式匹配法模式匹配法是指将现有问题与相似问题作类比，看看能否通过修改相关问题的解法来解决新问题。示例：一个有序数组的元素经过循环移动，元素的顺序可能变为“3 4 5 6 7 12”。怎样才能找出数组中最小的那个元素？假设数组中的元素各不相同。这个问题和下面两个问题有点类似：在一个无序数组中找出最小的元素； 在一个有序数组中找出某个特定的元素。处理方法在无序数组中查找最小元素的算法没多大意思，同时它也没有利用给定信息，因此这个问题帮不上什么忙。然而，二分查找法就非常适合。我们知道，这是个有序数组，只是一部分元素循环移动过。因此元素排序肯定是从小到大，在某一位置突然变小，接着又开始从小到大排列。那个“转折点”正是最小的元素。比较中间元素与末尾元素，由于MID > RIGHT，可以确定这个转折点就在这两个元素之间。这不符合从小到大的排列顺序，故而表明转折点就在其中。如果MID比RIGHT小，则说明转折点要么在前半部分，要么根本不存在。不管怎样，我们都可以找到最小的元素。我们可以继续运用这个方法，将数组逐步二分进行查找，最终找到最小的元素。
方法三：简化推广法采用简化推广法，我们会分多步走。首先，我们会修改某个约束条件，比如数据类型或数据量，从而简化这个问题。接着，我们转而处理这个问题的简化版本。最后，一旦找到解决简化版问题的算法，我们就可以基于这个问题进行推广，并试着调整简化版问题的解决方案，让它适用于这个问题的复杂版本。示例：从一本杂志里剪下一些单词可以拼凑成一封勒索信。怎样才能断定勒索信是否由某本杂志里的单词组成？我们可以先这样简化问题：暂时不考虑单词，只当它是字符。也就是说，假设我们从杂志里剪下一些字符拼成了这封勒索信。接着，我们只需新建一个数组并数出字符的数量，即可解决这个简化后的勒索信问题。数组中的每个元素对应一个字母。首先，我们数出每个字符在勒索信中出现的次数，然后再遍历整本杂志，确认它是否包含勒索信上的全部字符。推广这个算法时，具体做法和上面的差不多。只不过这一回，我们不再创建包含字符计数的数组，而是创建一个散列表，将单词映射到其词频上。
方法四：简单构造法对于某些类型的问题，简单构造法非常奏效。使用简单构造法，我们会先从最基本的情况来解决问题，一般只需记下正确的结果。得到n = 1的结果后，接着设法解决n = 2的情况。接下来，有了n = 1和n = 2的结果，我们就可以试着解决n = 3的情况了。最后，你会发现这其实就是一种递归算法——知道N-1时的正确结果，就能计算出N时的结果。有时，只有等到算出N为3或4时的结果，我们才能从中找到规律，基于前面的结果解决整个问题。示例：设计一种算法，打印某个字符串所有可能的排列组合。为简单起见，假设字符串中没有重复字符。以字符串abcdefg为例：只有“a”的情况， 结果为：{"a"} 然后是“ab”， 结果为：{"ab", "ba"} 再然后是“abc”，结果会是什么呢？此时，问题开始变得“有点意思”了。得到P的答案，怎么才能生成P呢？很简单，新字符是“c”，我们只需在前一种情况的答案也即字符组合的任意位置加一个c就可以了。也就是：P= 将“c”字符插入P得到的所有字符串的任意位置。
亦即：
P = 将“c”字符插入{"ab", "ba"}这两个字符串中的任意位置。
也就是：
P = merge。
最后得出结果：
P = {"cab", "acb", "abc", "cba","bca", "bac"}。
既然掌握了其中的套路，我们就可以设计一个递归算法。要生成字符串s1……sn的所有排列，我们可以先“砍掉”最后一个字符，首先生成s1……sn-1的所有排列。得到s1……sn-1所有排列的结果列表之后，我们会循环遍历这个列表，并在每个字符串的任意位置插入sn。简单构造法最后往往会演变成递归法。
方法五：数据结构头脑风暴法这种方法看起来有点笨，不过很管用。我们可以快速过一遍数据结构的列表，然后逐一尝试各种数据结构。这种方法很实用，因为一旦找到合适的数据结构，很多问题也就迎刃而解了。示例：随机生成一些数字，并保存到一个数组中。如何跟踪数组的中位数？数据结构头脑风暴法的过程大致如下。链表？恐怕不行——在数字的存取和排序上，链表往往效果不佳。 数组？也许可以，不过你已经用了一个数组。你有办法让数组保持有序状态吗？这么做开销恐怕比较大。暂不考虑采用，必要的话，可以回头再试。 二叉树？倒也有可能，因为二叉树非常适合处理排序问题。实际上，如果这棵二叉树是完全平衡的，根结点可能就是中位数。不过，你要小心——如果它包含偶数个元素，那么中位数实际上是中间两个元素的平均值。而中间两个元素不可能都是根结点。因此，二叉树也许可行，我们待会再说。 堆？堆非常适合基本排序，跟踪最大值和最小值。堆其实也很有意思——只用两个堆，就能跟踪较大的那一半元素和较小的那一半元素。较大的一半保存在小顶堆中，其中最小元素位于堆顶。较小的一半则保存在大顶堆中，其中最大元素位于堆顶。现在，有了这些数据结构，整个数组的中位数很可能就是两个堆顶之一。如果这两个堆大小不一样，你可以从元素较多的堆中弹出一个元素并压入另一个堆中，两个堆很快就能“重获平衡”。切记，问题演练得越多，你就越容易判断该选用哪种数据结构。当然了，你也能更自如地从这五种方法中选出最管用的那种。
6.4 怎样才算好代码
至此，你也许明白了，许多公司都想找能写出“优美、整洁”代码的人才。
但这到底意味着什么，怎样才能在面试中展现出这方面的能力呢？一般说来，好代码具备如下特性。正确：代码应当正确处理所有预期输入和非法输入。高效：不管是从空间上还是从时间上来衡量，代码都要尽可能地高效运行。所谓的“高效”不仅是指在极限情况下的渐近效率，同时也包括实际运行的效率。也就是说，在计算O时间时，你可以忽略某个常量因子，但在实际环境中，该常量因子可能有很大影响。简洁：代码能写成10行就不要写成100行。这样开发人员才能尽快写好代码。易读：要确保其他开发人员能读懂你的代码，并弄清楚来龙去脉。易读的代码会有适当注释，实现思路也简单易懂。这就意味着，那些包含诸多位操作的花俏的代码不见得就是“好”代码。可维护：在产品生命周期内，代码经过适当修改就能应对需求的变化。此外，无论对于原开发人员还是其他开发人员，代码都应该易于维护。力求实现上述特性必须找到一个平衡点。比如，有些情况下，我们往往要牺牲一定的效率好让代码更易维护，有时则要反其道行之。在面试中，写代码时应该好好考虑这些要素。下文就前面的清单给出更具体的描述。多用数据结构假设面试官要求你编写一个函数，对两个简单的多项式求和，其形式为Axa+ Bxb +…，即多项式的每一项都是一个常量乘以某个数的n次幂。面试官还补充说，不必对这些多项式做字符串解析，可以使用任意数据结构来表示它们。这个函数有多种实现方式。最差的实现方式最差的实现方式就是将多项式存储为一个double型数组，其中第k个元素对应的是多项式中xk的系数。采用这种结构有一定问题，如此一来，多项式就不能含有负的或非整数指数。要想用这种方法来表示x1000多项式的话，这个数组就得包含1000个元素。1 int[] sum { 2 …… 3 }较差的实现方式一种不算最差的实现方式是将多项式存为一对数组coefficients和exponents。采用这种方法，多项式的所有项可以按任意顺序存放，只要系数和指数配对，多项式的第i项表示为coefficients[i] * xexponents[i]。采用这种实现方式，如果coefficients[p] = k和exponents[p] = m，则第p项为kxm。尽管这么做没有上面那种解法的限制，但还是很凌乱。一个多项式就要用两个数组记录。如果两个数组长度不同，多项式就会出现“未定义”值。而要返回多项式更是麻烦，因为一下子得返回两个数组。
sum {
……
}
较好的实现方式对于这个问题，较好的实现方式是专为多项式设计一种数据结构。
class PolyTerm {
double coefficient;
double exponent;
}
PolyTerm[] sum {
……
}
有些人可能或真的认为这么做“优化过了头”。也许是，也许不是。不管你是不是这么认为，上面的代码都表明你应该用心思考如何设计代码，而不要匆忙地胡乱堆砌一通。适当重用代码假设面试官要求你编写一个函数检查某个二进制数是否等于以字符串表示的十六进制数。我们可以善用代码重用巧妙解决该问题。
public boolean compareBinToHex {
intn1 = convertTobase;
int n2 = convertTobase;
if {
return false;
} else {
return n1 ==n2;
}
}
public int digitToValue {
if return c - ‘0’;
else if return 10 + c - ‘A’;
else if return 10 + c - ‘a’;
return -1;
}
public intconvertTobase {
if ) return -1;
int value = 0;
for - 1; i >= 0; i--) {
int digit =digitToValue);
if {
return -1;
}
int exp = number.length - 1 - i;
value+= digit * Math.pow;
}
return value;
}
我们本可以实现两套代码，实现二进制数和十六进制数的转换，但这么做只会加大代码的编写难度，而且维护起来也更难。相反，我们还是通过编写convertTobase和digitToValue的方法来重用代码。模块化编写模块化代码是指将孤立的代码块划分为相应的方法。这有助于让代码更易读，可读性和可测试性更强。假设你在编写交换整数数组中的最大和最小元素的代码，不妨将全部代码写在一个函数里，如下所示：
public void swapMinMax {
int minIndex = 0;
for {
if {
minIndex = i;
}
}
int maxIndex = 0;
for {
if
{
maxIndex = i;
}
}
int temp =array[minIndex];
array[minIndex] = array[maxIndex];
array[maxIndex] = temp;
}
或者，你还可以采取更模块化的方式，将相对孤立的代码块隔离到对应的方法中。
public static int getMinIndex {
int minIndex = 0;
for {
if {
minIndex = i;
}
}
return minIndex;
}
public static int getMaxIndex { 12 int maxIndex= 0;
for {
if {
maxIndex = i;
}
}
return maxIndex;
}
public static void swap {
int temp = array[m];
array[m] = array[n];
array[n] = temp;
}
public static void swapMinMaxBetter {
intminIndex = getMinIndex;
int maxIndex =getMaxIndex;
swap;
}
虽然前面的非模块化代码看起来也不怎么糟，但模块化代码的一大好处在于它易于测试，因为每一部分都可以单独验证。随着代码越来越复杂，编写模块化代码就变得越发重要。模块化的代码也更易阅读和维护。面试官希望看到你能在面试中展现这些技能。灵活、健壮不要因为面试官要求编写代码检查谁是三连棋游戏的赢家，就非得假定它是一个3×3的棋盘。何不放手针对N×N棋盘编写代码呢？编写灵活、通用的代码，也可能意味着使用变量，而不是在代码里直接把值写死，或者使用模板/泛型来解决问题。要是有办法编写代码解决更普遍的问题，那我们就应该这么做。当然，它也有限制条件。如果通用解决方案更为复杂，并且在面试中几乎没有必要使用，那就按照要求解决相应的问题，效果可能会更好。错误检查写代码很细心的人有一个明显的特征，那就是她不会想当然地处理输入信息。相反，她会用ASSERT语句或if语句仔细验证输入数据是否合理。比如，回到前面那段将基数为i的进制数转换成整数的代码。
public int convertTobase {
if ) return -1;
int value = 0;
for - 1; i >= 0; i--) {
int digit =digitToValue);
if {
return -1;
}
int exp = number.length - 1 - i;
value +=digit * Math.pow;
} return value;
}
在第2行，我们检查基数是否有效。在第6行，我们另加了一处错误检查：确保每个数字都落在允许范围内。诸如此类的错误检查在实际的产品代码中至关重要，因此，面试中也不能掉以轻心。当然，这些错误检查有时很繁琐，可能会浪费宝贵的面试时间。关键在于指出你会加上错误检查。如果错误检查远非一条if语句就能搞定，写代码时最好先为错误检查预留一些空间，并告诉面试官，完成其余代码之后你会补上错误检查代码。
免责声明：本平台仅供信息发布交流之途，请谨慎判断信息真伪。如遇虚假诈骗信息，请立即举报
举报
