算法与数据结构面试
基础数学
字符串
| 题目 | 摘要 | 关于 |
|---|---|---|
| 确定一个字符串的所有字符是否全都不同 | 字符种类、位向量 | |
| 将N*N的矩阵旋转90度 | 逐层（从外向内/从内向外）交换4个元素 | |
| 给定两个字符串s1和s2，检查s2是否由s1旋转而成 | 若长度不同，直接返回；检查s1是否为s2+s2的子串 |
链表
快行指针（常见技巧）
指同时用两个指针来迭代访问链表，其中一个比另一个往往先行几步。
用途：
- 探测中间位置
| 题目 | 摘要 | 关于 |
|---|---|---|
| 以给定值x为基准将链表分成两部分，所有小于x的结点排在大于等于x的结点之前 | 两个链表、合并 | |
| 检测链表是否存在环路 | 快行指针、是否相遇 | |
| 给定有环链表，返回环路的开头结点 | 相遇后，一个指针返回链表头，一个指针在原地，他们相同速度相遇的位置（画图） | |
| 检查链表是否为回文 | 反转链表、前半部分后进先出、直觉解法 | |
| 有两个较长的单向链表a和b，想要找出同时存在于链表a和b中的节点node，请设计空间使用尽量小的算法。 | 如果有相同的节点，那么首个相同节点之后的所有节点都相同，也就是a和b的单向链表将会是横着的Y字形。因此，若从末尾开始，只需要一对一比对就可以。对称地想，分别得到lenA和lenB，针对长的链表，首先跳过差值数量个节点，伺候一对一比较即可找到相同节点 |
栈
| 题目 | 摘要 | 关于 |
|---|---|---|
| 栈支持min（取最小值）方法，且pop/push/min复杂度均为O(1) | 最小值也有状态，记录min值的额外栈 | |
| 按升序对栈进行排序（最大元素位于栈顶），最多只能使用一个额外的栈（支持push/pop/peek/isEmpty）存放临时数据 | 原栈未排序，额外栈有序；若原栈栈顶元素小于额外栈栈顶，则将原栈栈顶弹出为临时变量，额外栈栈顶不断弹出并压入原栈直到可插入位置，以此类推 |
树
树的种类
- 询问是二叉树是二叉查找树吗
- 询问树是否平衡
若树不平衡，则应当从平均情况和最坏情况所需时间来描述自己的算法
- 询问是否为满二叉树或者完全二叉树
| 题目 | 摘要 | 关于 |
|---|---|---|
| 检查一棵二叉树是否为二叉查找树 | *.中序遍历 *.用逐渐变窄的范围检查各个节点（而不是对于每个节点left.data<current.data<=right.data） | |
| 找出二叉树（不一定是二叉查找树）中某两个结点的第一个共同祖先，不得将额外的结点储存在另外的数据结构中 | .当有指向父节点的指针时，遍历，复杂度logNlogN *.当没有父指针时，若p和q都在某结点的左/右边，则进入该子树中查找，若不在同一边，则表示已找到，复杂度O(n) | |
| 给定一棵二叉树，其中每个结点都含有一个数值。打印结点数值总和等于某个给定值的所有路径。注意：路径不一定非得以根节点或叶节点为开始或者结束 | 1.询问是否为竖直不回溯的路径 2. 关注某个节点是否为总和为给定值的某条路径的末端（从节点n到root） |
位操作
| 符号 | 描述 | 运算规则 |
|---|---|---|
| & | 与 | 两个位都为1时，结果才为1 |
| \ | 或 | 两个位都为0时，结果才为0 |
| ^ | 异或 | 两个位相同为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| << | 左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
| >> | 右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
清除c的最低有效位
c = c & (c-1)
eg.
before: c = 101000
after: c = 100000
| 题目 | 摘要 | 关于 |
|---|---|---|
| 给定32位的整数N和M，将M插入到N的第j位开始到第i位结束 | 1.将N中从j到i之间的位清零 2.对M进行移位操作，与j和i之间的位对齐 3.合并M与N | |
| 给定一个正整数，找出与其二进制表示中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，则略小的数不存在 | |
| 数组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) |
智力题
对策
- 大声说出如何处理难题的思路，并不要求立即给出正确答案
- 总结解题过程中发现的“规律”或模式
| 题目 | 摘要 | 关于 |
|---|---|---|
| 给定两条绳子，每条绳子燃烧殆尽正好要用一个小时。怎样用这条绳子准确计量15分钟？注意绳子密度不均匀 | 点燃绳子1两头的同时，点燃绳子2的一头。当绳子1烧完的时候，点燃绳子2的另一头。15分钟后，绳子2将全部烧完。 | |
| 有20瓶药丸，其中19瓶装有1粒的药丸，余下一瓶装有1.1克粒的药丸。给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次。 | 对药瓶进行编号，对每个药瓶选取不同数量的药丸，进行称重，根据多出来的质量判断较重的那瓶药丸 | |
| 有个8x8棋盘，其中对角的角落上两个方格被切掉了。给定31块多米诺骨牌，一块骨牌恰好可以覆盖两个方格。用这31块骨牌能否盖住整个棋盘？请证明你的答案（提供范例，或证明为什么不可能）。 | 不可能。棋盘分别原有32个黑格，32个白格。切掉后，棋盘上仅剩30个黑格和32个白格。而每个骨牌必定盖住一个白格和一个黑格。 | |
| 有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人是蓝眼睛的，只知道至少有一个人的眼睛是蓝色的所有蓝眼睛的人要花几天才能离开这个岛？ | 记蓝眼睛人数为c。当c=1时，蓝眼睛的人知道至少有一人为蓝眼睛，因此他能推断是自己；当c=2时，蓝眼睛的人不知道c是1还是2；但若第2天另一个蓝眼睛依旧在岛上，那么他能推断c=2，那么自己也会离岛；以此类推，所有蓝眼睛的人要用c晚才能离岛，且都在同一晚离开 | |
| 走廊上有100个关上的储物柜。有个人先是将100个柜子全都打开。接着，每数两个柜子关上一个。然后，在第三轮时，再每隔两个就切换第三个柜子的开关状态（也就是将关上的柜子打开，将打开的关上）。照此规律反复操作100次，在第i轮，这个人会每数价就切换第i个柜子的状态。当第100轮经过走廊时，只切换第100个柜子的开关状态，此时有几个柜子是开着的？ | 柜子n会在n的每个因子轮切换状态；当因子个数为奇数时，柜子是开着的；由于可将n个两个互补因子配对，因此，完全平方数的因子是奇数；100内的完全平方数有10个 |
数学与概率
生成素数序列
埃拉托斯特尼筛法(Sieve Eratosthenes)
原理：剔除所有可被素数整除的非素数。
- 一开始列出到max为止的所有素数（为节省空间，可以只列出奇数）。
- 划掉所有可被2整除的数（2保留）。然后，找到下一个素数（也即下一个不会被划掉的数）,并划掉所有可被它整除的数（划掉数字时我们可以从primeprime开始，因为kprime早在之前的迭代里被划掉了，这里的k小于prime）。
- 划掉所有可被2、3、5、7等素数整除的数，最终可得到2到max之间的素数序列。
考察概率
善用韦恩图。
注意
float和double之间无法直接使用==进行比较，需要通过epsilon
| 题目 | 摘要 | 关于 |
|---|---|---|
| 有些数的素因子只有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中放值 | |
| 给定rands()，实现一个方法rand7()。也即，给定一个产生0到4（含）随机数的方法，编写一个产生0到6（含）随机数的方法。 | 我们只需产生出一个范围的数值，且每个数值出现的概率相同（且这个范围至少要有7个元素）。如果能做到这一点，就可以舍弃后面大于7的倍数的部分，然后将余下元素除以7取余数。由此将得到范围0到6的值，且每个值出现的概率相等。例如通过5*rand5()+rand5()产生范围0~24（注意每个数出现的概率是相等的），然后舍弃21和24之间的数字，最后除以7取余数 |
面向对象设计
解答步骤
-
处理不明确的地方
切忌武断臆测，需要提出问题以厘清问题，比如谁是使用者，他们将如何使用。比如一台每小时服务几百位顾客，还能制作10中不同口味的咖啡机，就与简易咖啡机不同。 -
定义核心对象，分析对象关系
哪些对象是其他对象的数据成员？哪个对象继承自别的对象？对象之间是一对多的关系，还是多对多的关系？ -
研究对象的动作
试着想想对象可执行的关键动作，若发现遗漏，就需要补全并更新设计。
具体建议
- 绘制结构图或者类图，明确数据与行为。（必要时可与面试官探讨，哪个方案更佳？）
相比你做了什么，你为什么这么做反而更显重要。面试官也许不会在意你是否选择将某个类实现为单例，但他可能真的在乎你有没有花时间思考，有没有跟他讨论各种做法的优劣。
-
考虑设计模式，比如单例模式、工厂模式。
-
列举之后考虑是否能够继续优化，比如重用代码、重构抽象等。
递归与动态规划
递归解法
- 自下而上考虑递归
从解决简单情况下的问题出发，构建出后续情况。
例如只有一个元素的列表，找出有两个、三个元素的列表的解法
- 自上而下考虑递归
思考将情况N下的问题分解成多个子问题，同时注意子问题是否重叠。
面试时考虑是否将递归代码改为迭代实现。
| 题目 | 摘要 | 关于 |
|---|---|---|
| 在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i]＝i。给定一个有序整数数组，元素值可能重复，编写一个方法，在数组A中找出一个魔术索引，若存在的话。 | 采用二分查找模式，比较midIndex与midValue是否相同，然后递归搜索左半部分(start, min(midIndex-1, midValue))和右半部分(max(midIndex+1, midValue), end) | |
| 编写一个方法，返回某集合的所有子集。 | 经分析，时间和空间复杂度最优为O(n)。构造所有子集等同于构造1到 的所有二进制数，再将这些数字的二进制表示转换成集合 |
扩展性与存储限制
面试官并不考察你掌握了多少系统设计知识，只考察最基本的计算机科学概念。他们想要评估的是你分解棘手问题的能力，以及用所学知识解决问题的能力。
方法
-
大胆假设
假设一台计算机就能装下全部数据，且存储上没有任何限制。你会如何解决问题？由此得出的答案可以为你最终解决问题提供基本思路。 -
切合实际
一台计算机究竟能装下多少数据，拆分这些数据会产生什么问题？我们需要考虑如何合理拆分数据，以及一台计算机需要不同的数据片段时，如何得知该去哪里查找，等等问题。 -
解决问题
想一想该如何处理发现的问题。请记住，这些解决方案应该能彻底消除这些问题，或至少改善一下状况。
通常情况下，你可以继续使用（进行一定修改）步骤1描述的方法，但偶尔也需要改弦易张，从根本上改变解决方案。请注意，迭代法通常很有用。也就是说，等你解决好步骤2发现的问题，可能又会冒出新问题，你还要着手处理这些新问题。你的目标不是重新设计公司耗资数百万美元搭建的复杂系统，而是证明你有能力分析和解决问题。检验自己的解法，四处挑错并予以修正。
拆分策略
-
按出现的顺序
有新数据进来时，先放进当前机器，填满之后，再加一台机器。这么做的好处是不会浪费资源。然而，根据具体问题和数据集的不同，查找表可能会变得非常复杂、异常巨大。 -
按散列值
根据数据的散列值存放数据。具体一点来说，我们会采取以下步骤：(l)根据数据挑选某种键；(2)利用散列函数得到键的散列值；(3）将散列值除以机器数量求得余数；(4)将数据存储在这个值对应的机器上。
数据会存放在编号为#[mod(hash(key),N)］的机器上。这种做法的好处是不用创建数据查找表。每一台计算机自动掌握数据的存储位置。然而，这也会出问题，那就是某台机器的数据可能会多一些，并最终超出它的存储容量。若发生这种情况，可以将数据迁移到其他机器上，以实现更好的负载均衡。
-
按实际值
利用数据所代表的信息来降低系统延迟。将类似数据存储在同一台机器上，那么查询时只需访问较少数量的机器就能取得相关资料。 -
随机存储
通常情况下，我们随机划分数据再实现一个查找表以表明哪台机器拥有哪些数据。虽然这肯定需要一张巨大的查找表，但它简化了系统设计的某些方面，使我们得以实现更好的负载均衡。
题目标记
排序与查找
| 题目 | 摘要 | 关于 |
|---|---|---|
| 给定两个排序后的数组A和B,其中A的末端有足够的缓冲空容纳B。编写一个方法，将B合并入A并排序。 | 从数组末尾开始合并 | |
| 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点、轻一点。己知马戏团每个人的高度和重量，请编写代码计算叠罗汉最多能叠几个人。 | 真正问题：给定一个列表，每个元素由一对项目组成。找出最长的子序列，其中第一项和第二项君以非递减的顺序排列。排序+最长递增子序列 | |
| 假设你正在读取一串整数。每隔一段时间，你希望能找出数字x的秩（小于或等于x的值的数目）。请实现数据结构和算法支持这些操作，也就是说，实现track(intx)方法，每读入一个数字都会调用该方法；以及getRankofNumber(int x)方法，返回值为小于或等于x的元素个数（不包括x本身）。 | 权衡插入元素(track操作)和查询操作，使用二叉查找树优于数组。查找元素时若向右移动累积左子树的大小，最后找到元素时计数即为秩。因此，可以为每个节点存储它左子树的节点数。 | |
| 求n个数中的最大值和最小值，最少的比较次数是多少次。 | 一个数如果大于当前最大值，那么将会替换成新的当前最大值，同时隐含这个数不可能是新的最小值，所以无须最小值比较。反之，最小值比较也是同样的道理。因此，可以每两个数（m,n）分为一组，无须完整的4次比较(即m和n分别与max和min比较，)，只需要3次比较（即m与n，较大与max，较小与min）就可以，最后需要的总比较次数3n/2。在计算算法复杂度时，还可以在系数k上面做优化。这对于实际系统的优化还是有意义的。 |
测试
切勿假设使用者会好好正常操作，请做好应对用户误用乱用软件的准备。
考察的方面：
- 周全完备的测试用例；
- 全局观：比如正确区分测试用例的优先顺序
- 懂整合：比如如何对整合后的更大的软件生态系统进行测试
- 会组织：有条理地处理问题，分类进行结构化处理。具体来说，将测试工作分割为几个主要模块，然后逐一展开分析。
- 可操作：测试计划切实可行
测试现实生活中的事物
- 使用者是哪些人？做什么用？
- 有哪些用例？
- 有哪些使用限制？
- 压力与失效情况下的状态如何？
- 如何执行测试？
测试一套软件
- 要做黑盒测试还是白盒测试？
1~5. 与上同
测试一个函数
- 定义测试用例
- 正常情况
- 极端情况
- 空和非法输入
- 奇怪的输入，比如有序数组或反向排序的数组
- 定义与其结果
- 编写测试代码
调试与排除已知故障
比如故障时Chrome启动时会崩溃。
- 理清状况，收集信息
问题的频率、浏览器的版本号、用户操作系统、错误报告、问题发生情况... - 分解问题
按照操作步骤进行分解，针对每个步骤逐一排查 - 创建特定的、可控的测试
一些测试
负载测试
待测量对象包括响应时间、吞吐量、资源利用率、系统所能承受的最大负载等。
若缺少测试工具，可以编写多线程的程序，新建成千上万个线程，每个线程扮演一个实际用户，载入待测页面。
对于每个用户，可以利用程序测量响应时间，数据IO等等。之后需要分析测试期间收集的数据结果，并与可接受的值进行比较。
题目标记
语言类
处理问题时卡壳
根据情况创建实例，问问自己该如何推演，问问自己，换做其他语言，该怎么处理这种情况。
如果你是语言设计者，该怎么设计？各种设计选择都会造成什么影响？相比不假思索地答出问题，如果你能推导出答案，同样会给面试官留下深刻的印象。不要试图蒙混过关。你可以直接告诉面试官："我不确定能否想起答案，不过让我试试能不能搞定它。假设我们拿到这段代码……”