算法与数据结构面试

基础数学

等比数列求和公式

字符串

链表

快行指针（常见技巧）

指同时用两个指针来迭代访问链表，其中一个比另一个往往先行几步。

用途：

1. 探测中间位置

栈

树

树的种类

1. 询问是二叉树是二叉查找树吗
2. 询问树是否平衡

若树不平衡，则应当从平均情况和最坏情况所需时间来描述自己的算法

3. 询问是否为满二叉树或者完全二叉树

位操作

清除c的最低有效位

c = c & (c-1)
eg. 
  before: c = 101000 
  after: c = 100000

题目	摘要	关于
8.5.1	给定32位的整数N和M，将M插入到N的第j位开始到第i位结束	1.将N中从j到i之间的位清零 2.对M进行移位操作，与j和i之间的位对齐 3.合并M与N
8.5.3	给定一个正整数，找出与其二进制表示中1的个数相同，且大小最接近的那两个数（一个略大，一个略小）	1.找略大： 反转最右边但非拖尾的0（记该位置为p，p右方1的个数为c），将p右方所有位清零，从最右边开始回填c-1个1. 2.找略小：记拖尾1的个数为c1,紧邻拖尾1左方的连续0的个数为c2，将连续0前的那个1的位置即为p，将p反转为0，之后将p紧邻右边回填c1+1个1；若找不到位置p，则略小的数不存在
8.5.7	数组A包含0到n的所有整数，但其中缺了一个。数组A的元素皆以二进制表示，唯一可用的访问操作是从A(i)取出第j位数据”，该操作的时间复杂度为常数。请找出那个缺失的整数，并在O(n)时间内完成	记 为最低有效位， 为次低有效位...在0到n的数中，若n为奇数，则0和1的数量相同；否则，0比1的数量多一个。检查最低有效位中0和1的数量，即可知道缺失的整数的最低位，并摒弃最低位与其不相同的数。之后，获取次低有效位，以此类推...复杂度为O(n+n/2+n/4+...)=O(n)

智力题

对策

1. 大声说出如何处理难题的思路，并不要求立即给出正确答案
2. 总结解题过程中发现的“规律”或模式

数学与概率

生成素数序列

埃拉托斯特尼筛法(Sieve Eratosthenes)

原理：剔除所有可被素数整除的非素数。

1. 一开始列出到max为止的所有素数（为节省空间，可以只列出奇数）。
2. 划掉所有可被2整除的数（2保留）。然后，找到下一个素数（也即下一个不会被划掉的数）,并划掉所有可被它整除的数（划掉数字时我们可以从primeprime开始，因为kprime早在之前的迭代里被划掉了，这里的k小于prime）。
3. 划掉所有可被2、3、5、7等素数整除的数，最终可得到2到max之间的素数序列。

考察概率

善用韦恩图。

注意

float和double之间无法直接使用==进行比较，需要通过epsilon

题目	摘要	关于
8.7.7	有些数的素因子只有3、5、7。请设计一个算法，找出其中第k个数。	记已出现的数字为，那么A_k则为列表里的数3或者5或者7，那么复杂度为 ；可以换个思路，每次将 放入列表，则将3 、5 、7 分别放入Queue3、Queue5、Queue7中，之后从每个队列头部取出最小的即可。但考虑到35与53的重复，357与537与735的重复，当从Queue5中取出 ，只往Queue5和Queue7中放值，当从当从Queue7中取出 ，只往Queue7中放值
8.17.11	给定rands()，实现一个方法rand7()。也即，给定一个产生0到4（含）随机数的方法，编写一个产生0到6（含）随机数的方法。	我们只需产生出一个范围的数值，且每个数值出现的概率相同（且这个范围至少要有7个元素）。如果能做到这一点，就可以舍弃后面大于7的倍数的部分，然后将余下元素除以7取余数。由此将得到范围0到6的值，且每个值出现的概率相等。例如通过5*rand5()+rand5()产生范围0~24（注意每个数出现的概率是相等的），然后舍弃21和24之间的数字，最后除以7取余数

面向对象设计

解答步骤

1. 处理不明确的地方
   切忌武断臆测，需要提出问题以厘清问题，比如谁是使用者，他们将如何使用。比如一台每小时服务几百位顾客，还能制作10中不同口味的咖啡机，就与简易咖啡机不同。

2. 定义核心对象，分析对象关系
   哪些对象是其他对象的数据成员？哪个对象继承自别的对象？对象之间是一对多的关系，还是多对多的关系？

3. 研究对象的动作
   试着想想对象可执行的关键动作，若发现遗漏，就需要补全并更新设计。

具体建议

1. 绘制结构图或者类图，明确数据与行为。（必要时可与面试官探讨，哪个方案更佳？）

相比你做了什么，你为什么这么做反而更显重要。面试官也许不会在意你是否选择将某个类实现为单例，但他可能真的在乎你有没有花时间思考，有没有跟他讨论各种做法的优劣。

2. 考虑设计模式，比如单例模式、工厂模式。

3. 列举之后考虑是否能够继续优化，比如重用代码、重构抽象等。

递归与动态规划

递归解法

1. 自下而上考虑递归
   从解决简单情况下的问题出发，构建出后续情况。

例如只有一个元素的列表，找出有两个、三个元素的列表的解法

2. 自上而下考虑递归
   思考将情况N下的问题分解成多个子问题，同时注意子问题是否重叠。

面试时考虑是否将递归代码改为迭代实现。

题目	摘要	关于
8.9.3	在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i]＝i。给定一个有序整数数组，元素值可能重复，编写一个方法，在数组A中找出一个魔术索引，若存在的话。	采用二分查找模式，比较midIndex与midValue是否相同，然后递归搜索左半部分(start, min(midIndex-1, midValue))和右半部分(max(midIndex+1, midValue), end)
8.9.4	编写一个方法，返回某集合的所有子集。	经分析，时间和空间复杂度最优为O(n)。构造所有子集等同于构造1到 的所有二进制数，再将这些数字的二进制表示转换成集合

扩展性与存储限制

面试官并不考察你掌握了多少系统设计知识，只考察最基本的计算机科学概念。他们想要评估的是你分解棘手问题的能力，以及用所学知识解决问题的能力。

方法

1. 大胆假设
   假设一台计算机就能装下全部数据，且存储上没有任何限制。你会如何解决问题？由此得出的答案可以为你最终解决问题提供基本思路。

2. 切合实际
   一台计算机究竟能装下多少数据，拆分这些数据会产生什么问题？我们需要考虑如何合理拆分数据，以及一台计算机需要不同的数据片段时，如何得知该去哪里查找，等等问题。

3. 解决问题
   想一想该如何处理发现的问题。请记住，这些解决方案应该能彻底消除这些问题，或至少改善一下状况。

通常情况下，你可以继续使用（进行一定修改）步骤1描述的方法，但偶尔也需要改弦易张，从根本上改变解决方案。请注意，迭代法通常很有用。也就是说，等你解决好步骤2发现的问题，可能又会冒出新问题，你还要着手处理这些新问题。你的目标不是重新设计公司耗资数百万美元搭建的复杂系统，而是证明你有能力分析和解决问题。检验自己的解法，四处挑错并予以修正。

拆分策略

1. 按出现的顺序
   有新数据进来时，先放进当前机器，填满之后，再加一台机器。这么做的好处是不会浪费资源。然而，根据具体问题和数据集的不同，查找表可能会变得非常复杂、异常巨大。

2. 按散列值
   根据数据的散列值存放数据。具体一点来说，我们会采取以下步骤：(l)根据数据挑选某种键；(2)利用散列函数得到键的散列值；(3）将散列值除以机器数量求得余数；(4)将数据存储在这个值对应的机器上。

数据会存放在编号为#[mod(hash(key),N)］的机器上。这种做法的好处是不用创建数据查找表。每一台计算机自动掌握数据的存储位置。然而，这也会出问题，那就是某台机器的数据可能会多一些，并最终超出它的存储容量。若发生这种情况，可以将数据迁移到其他机器上，以实现更好的负载均衡。

3. 按实际值
   利用数据所代表的信息来降低系统延迟。将类似数据存储在同一台机器上，那么查询时只需访问较少数量的机器就能取得相关资料。

4. 随机存储
   通常情况下，我们随机划分数据再实现一个查找表以表明哪台机器拥有哪些数据。虽然这肯定需要一张巨大的查找表，但它简化了系统设计的某些方面，使我们得以实现更好的负载均衡。

题目标记

8.10.3
8.10.7

排序与查找

测试

切勿假设使用者会好好正常操作，请做好应对用户误用乱用软件的准备。

考察的方面：

1. 周全完备的测试用例；
2. 全局观：比如正确区分测试用例的优先顺序
3. 懂整合：比如如何对整合后的更大的软件生态系统进行测试
4. 会组织：有条理地处理问题，分类进行结构化处理。具体来说，将测试工作分割为几个主要模块，然后逐一展开分析。
5. 可操作：测试计划切实可行

测试现实生活中的事物

1. 使用者是哪些人？做什么用？
2. 有哪些用例？
3. 有哪些使用限制？
4. 压力与失效情况下的状态如何？
5. 如何执行测试？

测试一套软件

1. 要做黑盒测试还是白盒测试？
   1~5. 与上同

测试一个函数

1. 定义测试用例

• 正常情况
• 极端情况
• 空和非法输入
• 奇怪的输入，比如有序数组或反向排序的数组

2. 定义与其结果
3. 编写测试代码

调试与排除已知故障

比如故障时Chrome启动时会崩溃。

1. 理清状况，收集信息
   问题的频率、浏览器的版本号、用户操作系统、错误报告、问题发生情况...
2. 分解问题
   按照操作步骤进行分解，针对每个步骤逐一排查
3. 创建特定的、可控的测试

一些测试

负载测试

待测量对象包括响应时间、吞吐量、资源利用率、系统所能承受的最大负载等。

若缺少测试工具，可以编写多线程的程序，新建成千上万个线程，每个线程扮演一个实际用户，载入待测页面。

对于每个用户，可以利用程序测量响应时间，数据IO等等。之后需要分析测试期间收集的数据结果，并与可接受的值进行比较。

题目标记

8.12.2

语言类

处理问题时卡壳

根据情况创建实例，问问自己该如何推演，问问自己，换做其他语言，该怎么处理这种情况。

如果你是语言设计者，该怎么设计？各种设计选择都会造成什么影响？相比不假思索地答出问题，如果你能推导出答案，同样会给面试官留下深刻的印象。不要试图蒙混过关。你可以直接告诉面试官："我不确定能否想起答案，不过让我试试能不能搞定它。假设我们拿到这段代码……”

Reference：

程序员面试金典(第5版)

技术之瞳——阿里巴巴技术笔试心得