程序员面试金典

面试考题

  1. 数据结构
    • 数组与字符串
    • 链表
    • 栈与队列
    • 树与图
  2. 概念与算法
    • 位操作
    • 智力题
    • 数学与概率
    • 面向对象设计
    • 递归和动态规划
    • 扩展性与存储限制
    • 排序与查找
    • 测试
  3. 知识类问题
    • C和C++
    • Java
    • 数据库
    • 线程与锁
  4. 附加面试题
    • 中等难度
    • 高等难度

数组与字符串

数组问题与字符串问题往往是相通的。换句话说, 书中提到的数组问题也可能以字符串的形式出现,反之亦然。

哈希表

散列表(Hash table,也叫哈希表),是根据关键字(Key-value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

  1. 链式哈希表
    • 将数据存储在”桶”(bucket)中, 每个”桶”都是一个链表, 且链表的容量随着冲突的增加而增大.
  2. 开地址哈希表
    • 将数据存储在表本身, 并通过各种探查方法来避免冲突问题.
  3. 用二叉查找树实现哈希表
    • 搜索、插入、删除的复杂度等于树高, 期望O(log n),最坏O(n)(数列有序,树退化成线性表).通常采取二叉链表作为二叉查找树的存储结构.
    • 虽然二叉查找树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉查找树可以使树高为O(log n),如SBT,AVL树,红黑树等。
  4. 哈希函数

ArrayList(动态数组)

按需动态调整大小的数组, 数据访问时间为O(1).

StringBuffer

创建一个足以容纳所有字符串的数组, 等它拼接完成才将这些字符串转成一个字符串.

面试题目

  1. 实现一个算法, 确定一个字符串的所有字符是否全都不同.即使不允许使用额外的数据结构,又该如何处理?
  2. 用C或C++实现void reverse( char* str)函数, 即反转一个null结尾的字符.
  3. 给定两个字符串, 请编写程序, 确定其中一个字符串的字符重新排列后,能否变成另一个字符串.
  4. 编写一个方法, 将字符串中的空格全部替换为“% 20”。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的”真实”长度.
  5. 利用字符串重复出现的次数,编写一个方法,实现基本的字符串压缩功能,比如字符串aabcccccaaa会变成a2b1c5a3,若压缩后的字符串没有变短,则返回原来的字符串
  6. 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度。 你能原地进行操作吗?(即不开辟额外的存储空间)
  7. 编写一个算法, 若M × N矩阵中某个元素为0, 则将其所在的行与列清零
  8. 假设你有一个isSubstring函数,可以检测一个字符串是否是另一个字符串的子串。给出字符串s1和s2,只使用一次isSubstring就能判断s2是否是s1的旋转字符串, 请写出代码。旋转字符串:”waterbottle”是”erbottlewat”的旋转字符串。

链表

链表问题有时会难倒不少求职者,因为链表元素访问用时不定,而且往往涉及递归

快行指针技巧

快行指针指的是同时用两个指针来迭代访问链表,只不过其中一个比另一个超前一些。

递归问题

递归算法至少要占用 O( n) 空间,其中 n 为递归调用的层数。实际上,所有递归算法都可以转换成迭代法,只是后者实现起来可能要复杂得多。

面试题目

  1. 编写代码,移除未排序链表中的重复结点。进阶如果不得使用临时缓冲区,该怎么解决?
  2. 实现一个算法,找出单向链表中倒数第 k 个结点。
  3. 实现一个算法,删除单向链表中间的某个结点,假定你只能访问该结点。
  4. 编写代码,以给定值 x 为基准将链表分割成两部分,所有小于 x 的结点排在大于或等于x 的结点之前。
  5. 给定两个用链表表示的整数,每个结点包含一个数位。这些数位是反向存放的,也就是个位排在链表首部。编写函数对这两个整数求和,并用链表形式返回结果。
  6. 给定一个有环链表,实现一个算法返回环路的开头结点。
  7. 编写一个函数,检查链表是否为回文。

栈与队列

实现一个栈

栈采用后进先出( LIFO) 顺序。

实现一个队列

队列采用先进先出( FIFO) 顺序。

面试题目

  1. 描述如何只用一个数组来实现三个栈。
  2. 请设计一个栈,除pop与push方法,还支持min方法,可返回栈元素中的最小值。pop、push和min三个方法的时间复杂度必须为O(1)。
  3. 设想有一堆盘子,堆太高可能会倒下来。因此,在现实生活中,盘子堆到一定高度时,我们就会另外堆一堆盘子。请实现数据结构SetOfStacks,模拟这种行为。SetOfStacks应该由多个栈组成并且在前一个栈填满时新建一个栈。此外,SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同(也就是说,pop()返回的值,应该跟只有一个栈时的情况一样)进阶:实现一个popAt(int index)方法,根据指定的子栈,执行 pop 操作。
  4. 在经典问题汉诺塔中,有3根柱子及N个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自底向上从大到小依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时有以下限制: 每次只能移动一个盘子
    盘子只能从柱子顶端滑出移到下一根柱子
    盘子只能叠在比它大的盘子上
    请运用栈,编写程序将所有盘子从第一根柱子移到最后一根柱子。
  5. 实现一个MyQueue类,该类用两个栈来实现一个队列。
  6. 编写程序,按升序对栈进行排序(即最大元素位于栈顶)。最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中(如数组)。该栈支持如下操作:push、pop、peek和isEmpty。
  7. 有家动物收容所只收容狗与猫,且严格遵守“先进先出”的原则。在收养该收容所的动物时,收养人只能收养所有动物中“最老”(根据进入收容所的时间长短)的动物,或者,可以挑选猫或狗(同时必须收养此类动物中“最老”的)。换言之,收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构,实现各种操作方法,比如enqueue、dequeueAny、dequeueDog和dequeueCat等。

树与图

许多求职者会觉得树与图的问题是最难对付的。检索这两种数据结构比数组或链表等线性数据结构要复杂得多。

需要注意的问题

  1. 二叉树与二叉查找树
  2. 平衡与不平衡
  3. 完满和完整(Full and Complete)

二叉树遍历

面试之前,你应该能够熟练实现中序、后序和前序遍历。其中最常见的是中序遍历,先遍历左子树,然后访问当前结点,最后遍历右子树。

树的平衡:红黑树和平衡二叉树

学习如何实现平衡树可助你成为更好的软件工程师,只不过面试中很少会问及平衡树。

单词查找树( trie)

trie 树是 n 层树的一种变体,其中每个结点存储有字符。整棵树的每条路径自上而下表示一个单词。

图的遍历

大部分求职者都比较熟悉二叉树的遍历,但图的遍历则要难得多。广度优先搜索( BFS)更是难上加难。广度优先搜索( BFS) 和深度优先搜索( DFS) 通常用于不同的场景。如要访问最少的结点直至找到想找的结点, DFS 一般最为简单。我们可能搜索了该结点的成千上万个祖先结点,却还未搜索该结点的全部子结点。对于这种情况, 一般首选BFS。

  1. 深度优先搜索( DFS)
  2. 广度优先搜索( BFS)

面试题目

  1. 实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个结点,其两棵子树的高度差不超过1。
  2. 给定有向图,设计一个算法,找出两个结点之间是否存在一条路径。
  3. 给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小的二叉查找树。
  4. 给定一棵二叉树,设计一个算法,创建含有某一深度上所有结点的链表(比如,若一棵树的深度为D,则会创建出D个链表)。
  5. 实现一个函数,检查一棵二叉树是否为二叉查找树。
  6. 设计一个算法,找出二叉查找树中指定结点的“下一个”结点(即中序后继)。可以假定每个结点都含有指向父结点的连接。
  7. 设计并实现一个算法,找出二叉树中某两个结点的第一个共同祖先。不得将额外的结点储存在另外的数据结构中。注意:这不一定是二叉查找树。
  8. 你有两棵非常大的二叉树:T1,有几百万个结点;T2,有几百个结点。设计一个算法,判断T2是否为T1的子树。(如果T1有这么一个结点n,其子树与T2一模一样,则T2为T1的子树。也就是说,从结点n处把树砍断,得到的树与T2完全相同。)
  9. 给定一棵二叉树,其中每个结点都含有一个数值。设计一个算法,打印结点数值总和等于某个给定值的所有路径。注意,路径不一定非得从二叉树的根结点或叶结点开始或结束。

位操作

位操作原理与技巧

常见位操作:获取,设置,清除以及更新位数据

  1. 获取

     boolean getBit( int num, int i) { 
         return ((num & (1 << i)) != 0); 
     }
    
  2. 设置

     int setBit( int num, int i) { 
          return num | (1 << i); 
     }
    
  3. 置位

     int setBit( int num, int i) { 
          return num | (1 << i); 
     }		
    
  4. 清零

     int clearBit( int num, int i) { 
          int mask = ~( 1 << i); 
          return num & mask;
     }
    	
     /* > 将 num 最高位至 i 位(含)清零:*/
     int clearBitsMSBthroughI( int num, int i) { 
          int mask = (1 << i) - 1; 
          return num & mask;
     }
    	
     /* 将 i 位至 0 位(含)清零 */
     int clearBitsIthrough0( int num, int i) { 
          int mask = ~(( 1 << (i+ 1)) - 1);
          return num & mask;
     }
    
  5. 更新

     int updateBit( int num, int i, int v) { 
          int mask = ~( 1 << i); 
          return (num & mask) | (v << i);
     }
    

面试题目

  1. 给定两个32位的整数N和M,以及表示比特位置的i和j。编写一个方法,将M插入到N中,使得M从N的第j位开始,到第i位结束,假定从j位到i位足以容纳M,也即是M=10011,那么j和i之间至少可容纳5个数,假如,不可能出现j=3,i=2的情况,因为第三位和第二位之间放不下M。
  2. 给定一个介于 0 和 1 之间的实数(如 0. 72), 类型为 double, 打印它的二进制表示。如果该数字无法精确地用 32 位以内的二进制表示,则打印 ERROR。
  3. 给定一个正整数,找出与其二进制表示中 1 的个数相同、且大小最接近的那两个数(一个略大,一个略小)。
  4. 解释代码(( n & (n- 1)) == 0) 的具体含义。
  5. 编写一个函数,确定需要改变几个位,才能将整数 A 转成整数 B。
  6. 编写程序,交换某个整数的奇数位和偶数位,使用指令越少越好(也就是说,位 0 与位 1 交换,位 2 与位 3 交换,依此类推)
  7. 数组 A 包含 0 到 n 的所有整数,但其中缺了一个。在这个问题中,只用一次操作无法取得数组 A 里某个整数的完整内容。此外,数组 A 的元素皆以二进制表示,唯一可用的的访问操作是从 A[ i] 取出第 j 位数据,该操作的时间复杂度为常数。请编写代码找出那个缺失的整数。你有办法在 O( n) 时间内完成吗?
  8. 有个单色屏幕存储在一个一维字节数组中,使得 8 个连续像素可以存放在一个字节里。屏幕宽度为 w, 且 w 可被 8 整除(即一个字节不会分布在两行上),屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数 drawHorizontalLine( byte[] screen, int width, int x1, int x2, int y), 绘制从点( x1, y) 到点( x2, y) 的水平线。

智力题

大声说出你的思路

总结规律和模式

给定两条绳子, 每条绳子燃烧殆尽正好要用一个小时。 怎样用这两条绳子准确计量15分钟?注意这些绳子密度不均匀,因此烧掉半截绳子不一定正好用半小时。

给定两条绳子, 燃烧殆尽各需要x分钟和y分钟, 我们可以计时x+y分钟。
给定一条需要燃烧x分钟的绳子, 我们可以计时x/2分钟。
燃烧绳子1用时x分钟, 绳子2用时y分钟, 则可以用第二条绳子计时(y-x)分钟或(y-x/2)分钟

略作变通

“九球称重”是一个经典面试题。给定9个球,其中8个球的重量相同,只有一个比较重。然后给定一个天平,可以称出左右两边哪边更重。最多用两次天平,找出这个重球。

给定N个球,其中N能被3整除,称量一次便能找到包含重球的那一组球。

触类旁通

要是卡壳了, 不妨考虑运用前面提到的算法题的五种解法:举例法, 简化推广法, 模式匹配法, 以及简单构造法。

面试题

  1. 有20瓶药丸, 其中19瓶装有1可/粒的药丸, 余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平, 怎么找出比较重的那瓶药丸?天平只能用一次
  2. 有个8*8棋盘, 其中对角的角落上, 两个方格被切掉了。给定31块多米诺骨牌, 一块骨牌恰好可以覆盖两个方格。 用这31块骨牌能否盖住整个棋盘?请证明你的答案
  3. 有两个水壶, 容量分别为5夸脱和3夸脱, 若水的供应量不限量(但没有量杯),怎么用这两个水壶得到刚好4夸克的水?注意, 这两个水壶呈不规则形状, 无法精准的装满半壶水。
  4. 有个岛上住着一群人, 有一天来了个游客,定了一个奇怪的规矩:所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色,但不知道自己的(别人也不可以告知)。此外, 他们不知道岛上到底有多少人是蓝眼睛的, 只知道至少有一个人的额眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛?
  5. 有栋建筑高100层。若从第N层或更高的楼层扔下来,鸡蛋就会破。若从第N层以下的楼层扔下来则不会破。给你2个鸡蛋请找出N, 并要求最差情况下扔鸡蛋的次数为最少。
  6. 走廊上又100个关上的储物柜。有个人先是将100个柜子全都打开。接着, 每数两个柜子关上一个。 然后, 在第三轮时, 再每隔两个就切换第三个柜子的开光状态(也就是将关上的柜子打开, 将打开的关上)。照此规律反复操作100次,在第i轮, 这个人会每数i个就切换第i个柜子的状态。当第100轮经过走廊时, 只切换第100个柜子的开关状态,此时有几个柜子是开着的?

数学概率

在面试碰到的许多数学问题, 其中很多看起来像是智力题, 其实大都可以运用逻辑, 有系统的解决。这些问题通常都以数学或计算机科学为基础。

素数

每一个数都可以分解成素数为乘积。例如:

84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 ...

**整除**

上面的素数定理指出, 要想以x整除y(写作x/y,或mod(y, x) =0), x素因子分解的所有素数必须出现在y的素因子分解中

Yan Peipan 08 April 2015