• 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(.....)……
  • 18.3 实现一个单例模式的模板

    题目 实现一个单例模式的模板,当给一个类Foo时,你可以通过Singleton::instance() 来得到一个指向Foo类单例的指针。假设我们现在已经有了Lock类,其中有acquire() 和release()两个方法,你要如何使你的实现线程安全且异常安全? 解答 #include <iostream> using namespace std; /* 线程同步锁 */ class Lock { public: Lock() { /* 构造锁 */ } ~Lock() { /* 析构锁 */ } void AcquireLock() { /* 加锁操作 */ } void ReleaseLock() { /* 解锁操作 */ } }; // 单例模式模板,只实……
  • 18.2 你如何测量一次上下文切换所需时间?

    题目 你如何测量一次上下文切换所需时间? 解答 这是一个棘手的问题,让我们先从可能的解答入手。 上下文切换(有时也称为进程切换或任务切换)是指CPU 的控制权从一个进程或线程切换到另一个。 (参考资料) 例如让一个正在执行的进程进入等待状态(或终止它),同时去执行另一个正在等待的进程。 上下文切换一般发生在多任务系统中,操作系统必须把等待进程的状态信息载入内存, 同时保存正在运行的进程的状态信息(因为它马上就要变成等待状态了)。 为了解决这个问题,我们需要记录两个进程切换时第一条指令和最后一条指令的时间戳, 上下……