• 20.5 给出两个单词,找到它们的最短距离

    题目 有一个很大的文本文件,里面包含许多英文单词。给出两个单词,找到它们的最短距离 (以它们之间隔了多少个单词计数)。你能在O(1)的时间内返回任意两个单词间的最短距离吗? 你的解法空间复杂度是多少? 解答 先看一个例子,为了简单起见,我们假设文件里就只有以下两句话。然后, 我们现在来求is和name的最短距离。假设相邻的两个单词距离为1。 What is your name My name is Hawstein 12 What is your name My name is Hawstein  首……
  • 20.4 写一个函数,计算0到n之间2的个数。

    题目 写一个函数,计算0到n之间2的个数。 解答 最简单直观的方法就是对于0到n之间的数,一个个地去统计2在它们上出现的个数, 然后累加起来即可。求2在某个数上出现的次数需要O(logn)的时间,一共有n个数, 所以共需要O(nlogn)的时间。 代码如下: int Count2(int n){ int count = 0; while(n > 0){ if(n%10 == 2) ++count; n /= 10; } return count; } int Count2s1(int n){ int count = 0; for(int i=0; i<=n; ++i) count += Count……
  • 20.3 写一个函数,随机地从大小为n的数组中选取m个整数

    题目 写一个函数,随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。 解答 这道题目和随机洗牌问题类似,只需要随机选取1个元素, 然后在剩下的元素里面随机选取下一个元素,不断这样操作即可。 这样做能保证每个元素选中的概率一样吗?也就是选中每个元素的概率都是1/n? 答案是YES,让我们来做一下简单的计算。 选第1个元素:在n个中随机选,因此概率为1/n 选第2个元素:在剩下的n-1个中随机选:1/(n-1),由于第1次没有选中它, 而是在另外n-1个中选:(n-1)/n,因此概率为:(n-1)/n * 1/(n-1) = 1/n 选第3个元素……
  • 20.2 写一个随机洗牌函数

    题目 写一个随机洗牌函数。要求洗出的52!种组合都是等概率的。 也就是你洗出的一种组合的概率是1/(52!)。假设已经给你一个完美的随机数发生器。 解答 这是一道非常有名的面试题,及非常有名的算法——随机洗牌算法。 最直观的思路是什么?很简单,每次从牌堆中随机地拿一张出来。那么, 第一次拿有52种可能,拿完后剩下51张;第二次拿有51种可能,第三次拿有50种可能, …,一直这样随机地拿下去直到拿完最后1张,我们就从52!种可能中取出了一种排列, 这个排列对应的概率是1/(52!),正好是题目所要求的。 接下来的问题是,如何写代码去实……
  • 20.1 不能使用+号或其它算术运算符求两个数的和

    题目 写一个Add函数求两个数的和,不能使用+号或其它算术运算符。 解答 为了解决这个问题,让我们来深入地思考一下,我们是如何去加两个数的。为了易于理解, 我们考虑10进制的情况。比如我们要算759 + 674,我们通常从最低位开始加, 考虑进位;然后加第二位,考虑进位…对于二进制,我们可以使用相同的方法, 每一位求和,然后考虑进位。 能把这个过程弄得更简单点吗?答案是YES,我们可以把求两个数的和分成两步, “加"与"进位",看例子: 计算759 + 674,但不考虑进位,得到323。 计算759 + 674,只考虑进位,而不是去加每一位,得……
  • 19.11 设计一个算法,找到数组中所有和为指定值的整数对

    题目 设计一个算法,找到数组中所有和为指定值的整数对。 解答 时间复杂度O(n)的解法 我们可以用一个哈希表或数组或bitmap(后两者要求数组中的整数非负)来保存sum-x的值, 这样我们就只需要遍历数组两次即可找到和为指定值的整数对。这种方法需要O(n) 的辅助空间。如果直接用数组或是bitmap来做,辅助空间的大小与数组中的最大整数相关, 常常导致大量空间浪费。比如原数组中有5个数:1亿,2亿,3亿,4亿,5亿。sum为5亿, 那么我们将bitmap中的sum-x位置1,即第4亿位,第3亿位,第2亿位,第1亿位,第0位置1. 而其它位置都浪费了。 如果……
  • 19.10 给定一个能生成1到5随机数的函数,如何利用它来生成1到7的随机数。

    题目 给你一个能生成1到5随机数的函数,用它写一个函数生成1到7的随机数。 (即:使用函数rand5()来实现函数rand7())。 解答 rand5可以随机生成1,2,3,4,5;rand7可以随机生成1,2,3,4,5,6,7。 rand5并不能直接产生6,7,所以直接用rand5去实现函数rand7似乎不太好入手。 如果反过来呢?给你rand7,让你实现rand5,这个好实现吗? 一个非常直观的想法就是不断地调用rand7,直到它产生1到5之间的数,然后返回。 代码如下: int Rand5(){ int x = ~(1<<31); // max int while(x > 5) x = Rand7(……
  • 19.8 统计给定单词在一本书中出现的次数

    题目 设计一个函数,统计给定单词在一本书中的出现次数。 解答 这道题目和19.2是一个思路。如果只需要查询一次, 那就直接做;如果要多次查询,而且要查询各种不同的单词,那就先预处理一遍, 接下来就只需要用O(1)的时间进行查询。 只查询一次 遍历这本书的每个单词,计算给定单词出现的次数。时间复杂度O(n),我们无法继续优化它, 因为书中每个单词都需要访问一次。当然,如果我们假设书中的单词是均匀分布, 那我们就可以只统计前半本书某个单词出现的次数,然后乘以2; 或是只统计前四分之一本书某个单词出现的次数,然后乘以4。这……
  • 19.7 求最大连续子序列和

    题目 给出一个整数数组(包含正数和负数),找到数组中最大的连续子序列,并返回和。 例子: 输入: {2, -8, 3, -2, 4, -10} 输出: 5 (即, {3, -2, 4} ) 解答 经典的面试题目,遍历一遍数组,用变量maxsum保存遍历过程中的最大和, 用变量cursum保存遍历过程中的当前和。在遍历的过程中,我们只需要做3件事, 第一:如果当前和cursum小于等于0,说明前面的连续和不会对后面的连续和产生贡献, 要么使后面的连续和减少,要么不变。因此舍弃cursum,用当前的元素更新它。 第二:如果当前和cursum是大于0的,累加当前元素。第三:如果当前和cu……
  • 19.5 写一个函数来模拟游戏

    题目 游戏规则如下: 4个槽,里面放4个球,球的颜色有4种,红(R ),黄(Y),绿(G),蓝(B)。比如, 给出一个排列RGGB,表示第一个槽放红色球,第二和第三个槽放绿色球,第四个槽放蓝色球。 你要去猜这个排列。比如你可能猜排列是:YRGB。当你猜的颜色是正确的,位置也是正确的, 你就得到一个hit,比如上面第3和第4个槽猜的和真实排列一样(都是GB),所以得到2个hit。 如果你猜的颜色在真实排列中是存在的,但位置没猜对,你就得到一个pseudo-hit。比如, 上面的R,猜对了颜色,但位置没对,得到一个pseudo-hit。 对于你的每次猜测,你会得……
  • 19.4 你使用if-else及任何比较操作符,返回两个数中的较大者

    题目 写一个函数返回两个数中的较大者,不能使用if-else及任何比较操作符。 解答 我们可以通过一步步的分析来将需要用到的if-else和比较操作符去掉: If a > b, return a; else, return b. If (a - b) < 0, return b; else, return a. If (a - b) < 0, 令k = 1; else, 令k = 0. return a - k * (a - b). 令z = a - b. 令k是z的最高位,return a - k * z. 12345 If a > b, return a; else, return b.If (a - b) < 0, return b; else, return a.If (a - ……
  • 19.3 写一个算法计算n的阶乘末尾0的个数

    题目 写一个算法计算n的阶乘末尾0的个数 解答 首先,算出n的阶乘的结果再去计算末尾有多少个0这种方法是不可取的, 因为n的阶乘是一个非常大的数,分分种就会溢出。我们应当去分析, 是什么使n的阶乘结果末尾出现0。 n阶乘末尾的0来自因子5和2相乘,5*2=10。因此,我们只需要计算n的阶乘里, 有多少对5和2。注意到2出现的频率比5多,因此,我们只需要计算有多少个因子5即可。 我们可以列举一些例子,看看需要注意些什么: 5!, 包含1*5, 1个5 10!, 包含1*5,2*5, 2个5 15!, 包含1*5,2*5,3*5, 3个5 20!, 包含1*5,2*5,3*……
  • 19.2 设计算法检查某人是否赢得了井字游戏

    题目 设计算法检查某人是否赢得了井字游戏。 解答 假设这个检查某人是否赢得了井字游戏的函数为HasWon,那么我们第一步要向面试官确认, 这个函数是只调用一次,还是要多次频繁调用。如果是多次调用, 我们可以通过预处理来得到一个非常快速的版本。 方法一:如果HasWon函数需要被频繁调用 对于井字游戏,每个格子可以是空,我的棋子和对方的棋子3种可能,总共有39 = 19683 种可能状态。我们可以把每一种状态转换成一个整数, 预处理时把这个状态下是否有人赢得了井字游戏保存起来,每次检索时就只需要O(1)时间。 比如每个格子上的3种状……
  • 19.1 不能使用临时变量,交换两个数

    题目 写一个函数交换两个数,不能使用临时变量。 解答 交换函数swap是经常用到的函数,小巧简单,以下两种实现方式都不需要使用临时变量: // 实现1 void swap(int &a, int &b){ b = a - b; a = a - b; b = a + b; } // 实现2 void swap(int &a, int &b){ a = a ^ b; b = a ^ b; a = a ^ b; } 123456789101112 // 实现1void swap(int &a, int &b){    b = a - b;    a……
  • 18.5 线程调度

    题目 假设我们有以下代码: class Foo{ public: A(.....); /*当A被调用时,会创建一个新的线程并执行相应的函数*/ B(.....); /*同上*/ C(.....); /*同上*/ }; Foo f; f.A(.....); f.B(.....); f.C(.....); 12345678910 class Foo{public:    A(.....); /*当A被调用时,会创建一个新的线程并执行相应的函数*/    B(.....); /*同上*/    C(.....); /*同上*/};Foo f;f.A(.....);f.B(.....)……