有两个玻璃珠，求最快的方法找到临界的从楼上丢下来不会丢的层数

A B C D E 海盗，他们要瓜分 100 个金币。A B C D E，轮流提议，提议的人需要获得半票以上包括半票，不然就会被杀死，下一个继续提议，你是 A 会怎么分配

智力题n根绳子燃烧问题，一个绳子烧完需要1h，求1h30min怎么烧

1.1024! 末尾有多少个0？

末尾0的个数取决于乘法中因子2和5的个数。显然乘法中因子2的个数大于5的个数，所以我们只需统计因子5的个数。 是5的倍数的数有： 1024 /5 = 204个 是25的倍数的数有：1024 /25 = 40个（25是5*5 所以包含25的包括了两个5） 是125的倍数的数有：1024/ 125 = 8个 是625的倍数的数有：1024/ 625 = 1个 所以1024! 中总共有204+40+8+1=253个因子5。 也就是说1024! 末尾有253个0。

  1. 给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

定义长度为1000的数组。 对于数据流中的前1000个关键字，显然都要放到数组中。 对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。 对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。

  1. 将下列表达式按照复杂度排序 2^n n^Googol (其中 Googol = 10^100) n! n^n

按照复杂度从低到高为 n^Googol 2^n n! n^n

  1. 在半径为1的圆中随机选取一点。

假设圆心所在位置为坐标元点(0, 0)。方法1. 在x轴[-1, 1]，y轴[-1, 1]的正方形内随机选取一点。然后判断此点是否在圆内（通过计算此点到圆心的距离）。如果在圆内，则此点即为所求；如果不在，则重新选取直到找到为止。 正方形的面积为4，圆的面积为pi，所以正方形内的随机点在圆内的概率是 pi / 4。 方法2. 从[0, 2*pi)中随机选一个角度，对应于圆中的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取，选取的概率应该和距圆心的长度成正比，这样才能保证随机点在圆内是均匀分布的。

  1. 给定一个未知长度的整数流，如何随机选取一个数？

方法1.将整个整数流保存到一个数组中，然后再随机选取。 如果整数流很长，无法保存下来，则此方法不能使用。 方法2.如果整数流在第一个数后结束，则我们必定会选第一个数作为随机数。 如果整数流在第二个数后结束，我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。 …. 如果整数流在第n个数后结束，我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。 …. 利用这种方法，我们只需保存一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。

  1. 设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。

  2. 使用数组存储。 插入数字时，在O(1)时间内将该数字插入到数组最后。 获取中数时，在O(n)时间内找到中数。（选数组的第一个数和其它数比较，并根据比较结果的大小分成两组，那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分，直到找到中数。）

  3. 使用排序数组存储。 插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。 获得中数时，在O(1)复杂度内找到中数。

  4. 使用大根堆和小根堆存储。 使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。 插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。 获取中数时，在O(1)时间内找到中数。

  5. 给定一个固定长度的数组，将递增整数序列写入这个数组。当写到数组尾部时，返回数组开始重新写，并覆盖先前写过的数。 请在这个特殊数组中找出给定的整数。

假设数组为a[0, 1, …, N-1]。 我们可以采用类似二分查找的策略。 首先比较a[0]和a[N/2]，如果a[0] < a[N/2]，则说明a[0,1,…,N/2]为递增子序列，否则另一部分是递增子序列。 然后判断要找的整数是否在递增子序列范围内。如果在，则使用普通的二分查找方法继续查找；如果不在，则重复上面的查找过程，直到找到或者失败为止。

  1. 给定两个已排序序列，找出共同的元素。

不妨假设序列是从小到大排序的。定义两个指针分别指向序列的开始。 如果指向的两个元素相等，则找到一个相同的元素；如果不等，则将指向较小元素的指针向前移动。重复执行上面的步骤，直到有一个指针指向序列尾端。（我上次面试面度的时候他们问这道题了，等分情况，如果两个数组大小差不多，用你的方法就行了，如果数组大小差得很多，就遍历小的，然后在大的里二分查找~ ）

  1. 给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

此题的关键是让生成的 1 到 7 的数出现概率相同。只要我们可以从 n 个数中随机选出 1 到 n 个数，反复进行这种运算，直到剩下最后一个数即可。 我们可以调用 n 次给定函数，生成 n 个 1 到 5 之间的随机数，选取最大数所在位置即可满足以上要求。

例如 初始的 7 个数[1,2,3,4,5,6,7]. 7 个 1 到 5 的随机数 [5, 3,1,4,2,5,5] 那么我们保留下[1,6,7], 3 个1 到 5 的随机数[2,4,1] 那么我们保留下[6] 6 就是我们这次生成的随机数。

  1. 判断一个自然数是否是某个数的平方。当然不能使用开方运算。

假设待判断的数字是 N。

方法1： 遍历从1到N的数字，求取平方并和N进行比较。 如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。 复杂度为O(n^0.5)。

方法2： 使用二分查找法，对1到N之间的数字进行判断。 复杂度为O(log n)。

方法3： 由于 (n+1)^2 =n^2 + 2n + 1， = … = 1 + (21 + 1) + (22 + 1) + … + (2*n + 1) 注意到这些项构成了等差数列（每项之间相差2）。 所以我们可以比较 N-1， N - 1 - 3， N - 1 - 3 - 5… 和0的关系。 如果大于0，则继续减；如果等于0，则成功退出；如果小于 0，则失败退出。 复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。

  1. 给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

定义长度为1000的数组。对于数据流中的前1000个关键字，显然都要放到数组中。对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。

  1. 将下列表达式按照复杂度排序 2^n n^Googol (其中 Googol = 10^100) n! n^n

按照复杂度从低到高为 n^Googol 2^n n! n^n

  1. 谷歌笔试题：在半径为1的圆中随机选取一点 假设圆心所在位置为坐标元点(0, 0)。 方法1.在x轴[-1, 1]，y轴[-1, 1]的正方形内随机选取一点。然后判断此点是否在圆内（通过计算此点到圆心的距离）。如果在圆内，则此点即为所求；如果不在，则重新选取直到找到为止。 正方形的面积为4，圆的面积为pi，所以正方形内的随机点在圆内的概率是 pi / 4。 方法2.从[0, 2*pi)中随机选一个角度，对应于圆中的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取，选取的概率应该和距圆心的长度成正比，这样才能保证随机点在圆内是均匀分布的。

  2. 给定一个未知长度的整数流，如何随机选取一个数 方法1.将整个整数流保存到一个数组中，然后再随机选取。 如果整数流很长，无法保存下来，则此方法不能使用。 方法2.如果整数流在第一个数后结束，则我们必定会选第一个数作为随机数。 如果整数流在第二个数后结束，我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。….如果整数流在第n个数后结束，我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。…. 利用这种方法，我们只需保存一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。

15.设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。

  1. 使用数组存储。 插入数字时，在O(1)时间内将该数字插入到数组最后。 获取中数时，在O(n)时间内找到中数。（选数组的第一个数和其它数比较，并根据比较结果的大小分成两组，那么我们可以确定中数在哪组中。然后对那一组按照同样的方法进一步细分，直到找到中数。）
  2. 使用排序数组存储。插入数字时，在O(logn)时间内找到要插入的位置，在O(n)时间里移动元素并将新数字插入到合适的位置。获得中数时，在O(1)复杂度内找到中数。
  3. 使用大根堆和小根堆存储。使用大根堆存储较小的一半数字，使用小根堆存储较大的一半数字。插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。获取中数时，在O(1)时间内找到中数。给定一个固定长度的数组，将递增整数序列写入这个数组。当写到数组尾部时，返回数组开始重新写，并覆盖先前写过的数。请在这个特殊数组中找出给定的整数。假设数组为a[0, 1, …, N-1]。我们可以采用类似二分查找的策略。首先比较a[0]和a[N/2]，如果a[0] < a[N/2]，则说明a[0,1,…,N/2]为递增子序列，否则另一部分是递增子序列。然后判断要找的整数是否在递增子序列范围内。如果在，则使用普通的二分查找方法继续查找；如果不在，则重复上面的查找过程，直到找到或者失败为止。给定两个已排序序列，找出共同的元素。不妨假设序列是从小到大排序的。定义两个指针分别指向序列的开始。如果指向的两个元素相等，则找到一个相同的元素；如果不等，则将指向较小元素的指针向前移动。重复执行上面的步骤，直到有一个指针指向序列尾端。

16找到链表的倒数第m个节点。 方法1：首先遍历链表，统计链表的长度N。然后再次遍历链表，找到第N-m个节点，即为倒数第m个节点。 方法2：使用两个指针，并使它们指向的节点相距m-1个。然后同时向前移动两个指针，当一个指针指最后一个节点时，第二个指针指向倒数第m个节点。两个方法的复杂度都是O(n)。但是当N较大而m较小时，方法2可能会更快一些。因为方法2能更好利用CPU的缓存。 更多阅读： http://baike.baidu.com/view/2089.htm CPU -> 缓存

17给定一个排序数组，如何构造一个二叉排序树？ 采用递归算法。选取数组中间的一个元素作为根节点，左边的元素构造左子树，右边的节点构造有子树。

  1. 数组中是否有两个数的和为10 1.比较任意两个数的和是否为10。如 for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { …. }} 复杂度为O(n*n)。 2.将数组排序后，对每个数m，使用二分查找在数组中寻找10-m。 复杂度为O(nlogn)。 3.将数组存储到hash_set中去，对每个数m，在hash_set中寻找10-m。 复杂度为O(n)。 4.如果数组很大，超过内存的容量，可以按照hash(max(m, 10-m))%g，将数据分到g个小的group中。然后对每个小的group进行单独处理。 复杂度为O(n)。

  2. 找到两个字符串的公共字符，并按照其中一个的排序

写一函数f(a,b)，它带有两个字符串参数并返回一串字符，该字符串只包含在两个串中都有的并按照在a中的顺序。写一个版本算法复杂度O(N^2)和一个O(N) O(N^2)：对于a中的每个字符，遍历b中的每个字符，如果相同，则拷贝到新字符串中。

O(N)：首先使用b中的字符建立一个hash_map，对于a中的每个字符，检测hash_map中是否存在，如果存在则拷贝到新字符串中。 20.给定一个整数序列，其中有些是负数，有些是正数，从该序列中找出最大和的子序列。比如：-5，20，-4，10，-18，子序列[20，-4，10]具有最大和26。

Int GetMaxSubArraySum(int*array,int array_len)

{ int current_sum =0;

intmax_sum=0;

for(inti=0;i<array_len;i++)

{
   curren_sum+=array;

   if(current_sum>max_sum)

   {
       max_sum=current_sum;

}

else if(current_sum<0)

{ current_sum=0;

}

}

return max_sum;

}

或者 int maxsum(int n,int *list)

{ int ret,sum=0;

int i;

for(ret =list[i=0];i<n;i++)

sum=(sum>0?sum:0)+list,ret=(sum>0?sum:ret);

return ret;

}

  1. 将无向无环连通图转换成深度最小的树

已知一个无向无环连通图T的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要求的树的根结点，并分析时空复杂度。

最简单直接的方法就是把每个节点都试一遍：假设某个节点为根节点，计算树的深度。当遍历完所有节点后，也就找到了使树的深度最小的根节点。但这个方法的复杂度很高。如果有n个节点，则时间复杂度为O(n^2)。树的深度取决于根节点到最深叶节点的距离，所以我们可以从叶节点入手。叶节点会且只会和某一个节点连通（反之不成立，因为根节点也可能只和一个节点连通），所以我们很容易找到所有可能的叶节点。题目可以等价于找到了两个叶节点，使得两个叶节点之间的距离最远。根节点就是这两个叶节点路径的中间点（或者中间两个点的任意一个）。我们可以每次都将连接度为1的节点删掉，直到最后只剩下1个或2个节点，则这一个节点，或者两个节点中的任意一个，就是我们要找的根节点。

  1. 将字符串中的小写字母排在大写字母的前面

有一个由大小写组成的字符串，现在需要对它进行修改，将其中的所有小写字母排在大写字母的前面（大写或小写字母之间不要求保持原来次序）。初始化两个int变量A和B，代表字符串中的两个位置。开始时A指向字符串的第一个字符，B指向字符串的最后一个字符。逐渐增加A的值使其指向一个大写字母，逐渐减小B使其指向一个小写字母，交换A，B所指向的字符，然后继续增加A，减小B….。当A>=B时，就完成了重新排序。i指向最后一个小写字符，j寻找小写字符。

void swapString(char *str,intlen)

{ inti=len-1,j=0;

while(j<=i)

{
   boolflag1=0,flag2=0;

   if(str[i]>'z'||str[i]<'a')

   {
       i--;

   }

   else

       flag1=1;








   if(str[j]>'Z'||str[j]<'A')

   {
       j++;

​

   }

   else

       flag2=1;

   if(flag1&&flag2)

   {
       swap(str[i],str[j]);

   }

​

}

}

  1. 在重男轻女的国家里，男女的比例是多少？在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少？

还是1：1。在所有出生的第一个小孩中，男女比例是1：1；在所有出生的第二个小孩中，男女比例是1：1；…. 在所有出生的第n个小孩中，男女比例还是1：1。所以总的男女比例是1：1。

  1. 如何拷贝特殊链表,有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand，如何拷贝这个特殊链表？

拷贝pNext指针非常容易，所以题目的难点是如何拷贝pRand指针。假设原来链表为A1 -> A2 ->… -> An，新拷贝链表是B1 -> B2 ->…-> Bn。为了能够快速的找到pRand指向的节点，并把对应的关系拷贝到B中。我们可以将两个链表合并成 A1 -> B1 -> A2 -> B2 -> … -> An -> Bn。从A1节点出发，很容易找到A1的pRand指向的节点Ax,然后也就找到了Bx，将B1的pRand指向Bx也就完成了B1节点pRand的拷贝。依次类推。当所有节点的pRand都拷贝完成后，再将合并链表分成两个链表就可以了。

25如何尽快找到一个好人

有n个人，其中超过半数是好人，剩下的是坏人。好人只说真话，坏人可能说真话也可能说假话。这n个人互相都知道对方是好人还是坏人。现在要你从这n个人当中找出一个好人来，只能通过以下方式：每次挑出两个人，让这两个人互相说出对方的身份，你根据两个人的话进行判断。问通过何种方法才能最快的找出一个好人来。(要考虑最坏的情况)

和百度面试题中的芯片测试问题非常相似，不再赘述。请参考： http://hi.baidu.com/mianshiti/blog/item/2bcc4a8225fa1ad4bd3e1e17.html按照这个方法，答案为3n，不知有没有更快的方法。

  1. 如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设为常概率条件下)

假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是(1-x)^3，也就是0.05。所以得到方程 (1-x)^3 = 0.05 解方程得到x大约是0.63。

  1. 有25匹马，每次比赛只能有5匹马参加，问最少进行几次比赛才可以得到25匹马中跑得最快的前3名？

最少需要7次。 首先将马分成a,b,c,d,e 5个组，每组5匹，每组单独比赛。然后将每组的第一名放在一起比赛。假设结果如下 a0,a1,a2,a3,a4 b0,b1,b2,b3,b4 c0,c1,c2,c3,c4 d0,d1,d2,d3,d4 e0,e1,e2,e3,e4 其中a, b,c,d,e小组都是按照名次排列（速度a0>a1>a2>a3>a4,b0>b1….)。并第6次比赛的结果为a0>b0>c0>d0>e0。 那么第6次比赛结束后，我们知道最快的一匹为a0。 我们知道第2名的马一定是a1或者b0，所以在接下来的比赛中要包含这两匹马。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是说第2名和第3名一定在a1，a2，b0，b1和c0当中，所以在第7场比赛中包括这5匹马就可以得到第2名和第3名。 所以7次比赛就可以获得前3名的马。

  1. 有5个海盗，按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决，如果多数（所有人中的多数）反对，那他就会被杀死。他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？ 分配方案是98，0，1，0，1。 5级海盗会不会被杀死，取决于5级海盗死后其他海盗是否会获得更多的利益。如果可以获得更多的利益，则肯定会反对，如果会获得更少的利益，则肯定会支持，如果利益没有变化，则反对或支持都可以。如果5级海盗死了，则有4级海盗分配，4级海盗面临同样的问题，需要看自己死后的利益分配变化。然后是3级海盗，2级海盗。2级海盗无论提出什么方案，都不会有多数人反对（自己支持，另一个人反对不能构成多数反对）。所以2级海盗肯定会提出100，0的分配方案，自己独享所有金币。猜到2级海盗的分配方案后，3级海盗会提出99，0，1的分配方案。这样1级海盗因获得了比2级海盗方案中更多的金币，所以会支持3级海盗的方案。猜到3级海盗的分配方案后，4级海盗会提出99，0，1，0的分配方案。这样2级海盗获得了比3级海盗方案中更多的金币，所以会支持4级海盗的方案。猜到4级海盗的分配方案后，5级海盗会提出98，0，1，0，1的分配方案。这样1级海盗和3级海盗获得了比4级海盗方案中更多的金币，所以会支持5级海盗的方案。

  2. 4 个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分钟的手电筒。通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。这四个人过索桥的速度都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三个5分钟，最慢的那个要10分钟。他们怎样才能在17分钟内全部走过索桥？ 1）第一个和第二个一起过去，用掉2分钟； 2）第一个回来，用掉1分钟； 3）第三个和第四个一起过去，用掉10分钟； 4）第二个回来，用掉2分钟； 5）第一个和第二个一起过去，用掉2分钟。 总共用掉17分钟。

30如何从8只球中找出比较重的一个 你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅称两次将那个重一些的球找出来。 解答：先取6个，天平上一边3个，同重则称剩余2个即可；不同重，则取重的3个中的2个来称。分析：此题可以通过倒推法来解决。如果我们知道重球在某两个球中，则可以通过天平两边各放一个，比较重量发现重球。如果我们知道重球在某三个球中，则可以通过天平两边各放一个，如果一样重，则第三个球是重球，否则天平上较重的即是重球。如果我们知道重球在大于等于四个球中，则不能通过一次称重发现重球。所以通过第一次称重，我们必须将重球限定在某两个或三个球当中。另外，天平两端放的球数应该相等，否则结果基本没有意义。 满足两端球相等的所有可能的比较方法 左，右 1， 1 2， 2 3， 3 4， 4 再考虑到必须将重球限定在2或3个球中，第一次只能采取3，3的比较方法。 此题还可以扩展一下：在m只大小相同的球中，m-1只重量相同，另外一只比较重。问需要用天平称多少次才能将重球找出来？ 从上面的分析中可以知道，称一次最多可以

  • 将重球从3个球中找出来。
  • 将重球从9个球中限定在3个球中。
  • 将重球从27个球中限定在9个球中。 ….. 所以，称n次最多可以将重球从3^n中找出来。倒推回去也就可以获得m个球需要称多少次。 （天平就三种状态 左重,左轻,平衡 那么N次最多可以有3^N种状态,而坏球有轻重两种状态,唯一特殊的是N次都平衡时可以找到坏球但不知道坏球轻重,那M个球可以有2(M-1)+1种状态 所以在有足量标准球时,有2(M-1)+1≤3^N即M≤(3＾n+1)/2 ）

作者：Yasu0 链接：https://www.nowcoder.com/discuss/526897 来源：牛客网

有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？ 首先，第一天出来的人，担当“计数者”，它把灯开起来（原来开着就不必动了）, 然后每天出来一个囚犯。 如果他不是“计数者”，并且没有关过灯， 并且灯开着， 那么就把灯关了。如果他是“计数者”， 如果灯关了， 就把他开起来（计数+1）。 当然如果灯被关了99次， 那么就去和国王说吧。

第一天出来的是“计数者”， 这是一个必然事件， 从第二天开始， 我们要完成以下过程 99 次

出来一个新的囚犯， 然后等待“计数者”出来把灯开起来。 第一次出来新的囚犯的概率是： 99 / 100 — 除去计数者， 其他任何囚犯出来都满足要求 , 完成这一步的平均时间是 100 / 99 天 完成上面这个过程后，接着要求“计数者”出来，开灯。 这个概率是 1 / 100 , 完成这一步的平均时间是 100 天

第二次， 新囚犯出来的概率是 98 / 100, 完成这一步的平均时间是 100 / 98 , 计数者出来的率还是 1 / 100 , 完成这一步的平均时间还是 100 天

…

第99次， 新囚犯出来的概率是 1 / 100 (只有一个囚犯没有出来了) , 计数者出来的率还是 1 / 100

然后我们把时间加起来:

100 / 99 + 100 + 100 / 98 + 100 + … 100 / 1 + 100

= 100 * 99 + 100 * (1 / 99 + 1 / 98 + 1 / 97 + … + 1)

= 9900 + 100 * (1 + 1 / 2 + 1 / 3 + … 1 / 99)

1 + 1 / 2 + 1 / 3 + … 1 / 99 这是一个调和级数 大概等于 ln 99 + 1 ，

所以上述值为： 10417

https://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf

家里有两个孩子，一个是女孩，另一个也是女孩的概率是多少？ https://www.bilibili.com/video/BV1ws411j77v

李永乐老师 yyds

ans : 1/3

参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门可赢得该汽车，另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门，但未去开启它的时候，节目主持人开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。问题是：换另一扇门会否增加参赛者赢得汽车的机率。 https://www.bilibili.com/video/av25648623/

李永乐老师 yyds

ans : 换， 不换1/3 ，换2/3

一副牌52张,告诉瞎子里面有10张牌是正面朝上的, 要求瞎子把这52张牌分成两堆, 并且每堆牌正面朝上的张数相同，可任意翻动牌，但是一直不可以看。 分成10和42， 10 中的所有牌。

proof： 第一堆（10张牌里有x张向上），全翻 = 10-x 张向上，等于第二堆向上的牌数

有无限的水，5L和6L 的桶精确装4L 水 通用解法： 用小的桶不断往大桶填水

这里： 5L桶 6L桶

0 0

5 0

0 5

5 5

4 6

1000瓶药，有一些可能有毒，用老鼠来喝药，喝到有毒的一周就死。一周内至少需要多少只老鼠才能检测到哪些有毒 二进制，死=1，不死=0，老鼠=bit，答案 lg1000 = 10

25匹马，5个赛道，最少需要比赛几次才能知道前3名 赛马经典问题： 5+1+1 = 7次

13个石头，有一个比较重其他都一样，用天平测量最多需要几次才能测出重的那个 一般都是分成3份ABC，称A和B，如果A=B，那么在C那，A>B 在A那，A<B 在B那 . 一次排除了2/3.

4 4 5

  1. 如果 4 == 4 在 5 里面 分为 2 2 1 1.1) 如果 2 == 2 在 1 那 ok 两次 1.2) 如果 2 != 2 称 1 1 ，那个沉就是答案，三次
  2. 4 != 4 在 沉的那堆里面 2.1) 称2 2 排除 2个 再称1 1 ，那个沉就是答案，三次

ps 评论提醒，最好是1次，直接 6 6 1 ，如果平衡那个1就是答案，但是不确保能测出

五对夫妇举行家庭聚会 每一个人都可能和其他人握手, 但夫妇之间绝对不握手. 聚会结束时,A先生提问大家握手几次（很关键），结果是每个人的握手次数不相同。问A先生的太太握手几次 首先有一个隐含的信息，他们握手的次数分别是0，1，2，3，4，5，6，7，8。为什么呢?显然，握手次数是小于等于8的，因为10个人，自己不和自己握手，自己不和配偶握手，只能是10-2=8，刚刚好大家的都不同所以就是0-8了

其次，握手x次和握手8-x次的是一家人。抽象来说，俩夫妻握手总次数刚刚好铺满其他8人。

比如0次和8次是一家人。因为一个人握了0次手，说明他（她）没有和其他任何人握手，而握了8次手的人握了别家的所有人的手，如果握了8次手的这个人和握了0次手的这个人不是一家人，握了8次手的这个人就必然握过握了0次手的人，那么，握了0次手的人就被握了8次手的人握了1次，这就矛盾了。

再比如，握1次手的人和握7次手的人是一家人。因为现在大家都至少握过一次手了（和握过8次手的那个人握的），所以握过7次手的人必须和除了第一家和自己家的所有人握手，而握过1次手的人已经不能再和任何人握手了，因此，他们只能是一家人。其他同理。

接着，既然握手次数之和为8的必定是一对夫妻,九人中又没有两个人握手的次数相同,而0-8次握手里面没有配对成功的是4（成功的是0-8，1-7，2-6，3-5），所以只有A先生和A太太握手次数同为4次

两人玩游戏，在脑门上贴数字（正整数>=1），只看见对方的，看不见自己的，而且两人的数字相差1。两人的对话： A：我不知道 B：我也不知道 A：我知道了 B：我也知道了。问A头上的字是多少，B头上的字是多少？ 每一个数n都是 有n-1和n+1两个相邻数，但是1只有一个2是相邻数

A：我不知道 。不知道自己是1还是3 B：我也不知道。 如果A是1，那么B肯定是能够确定他自己是2。 A：我知道了。自己不是1 而是3 B：我也知道了。 既然A知道自己，肯定是从2推出的3，那么也知道自己是2了

所以A是3，B是2

如果你是一名艾滋病患者，那么经过检测后，结果显示为阳性的概率为 99% 。如果你并没有携带艾滋病毒，经过检测后，结果显示为阳性的概率仅为 1% 。也就是说，这种设备较为‘可靠’， 不论你是否患有艾滋病，它基本能作出正确的判断。假如现在，用艾滋病检测试纸对自己进行一次 检测，检测结果显示是阳性，那请问你觉得自己得艾滋病的概率是多大？患艾滋病的概率是 1/10000 . 当随机从总体中抽出一个人，利用检测试纸进行检 测，如果检测结果呈阳性，并不意味着这个人一定患病，他患病的可能性其实不高，原因是没患病的人基数实在太高了。

阳性的情况（假阳+真有病）： 9999/10000 * 1% + 1/10000 * 99%

真有病概率 ： 1/10000 * 99% / （ 9999/10000 * 1% + 1/10000 *99% ） 约1%

后续问题： 连续2次都是阳性，真有病的概率？

阳性的情况（假阳+真有病）： 9999/10000 * 1%* 1% + 1/10000 * 99% * 99%

真有病概率 ： 1/10000 * 99% * 99% / （ 9999/10000 * 1% * 1% + 1/10000 * 99% * 99%） 约50%

烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢? 1 同时两头 2 一头 等1 烧完再点2的另一头，等2烧完再点燃3，等3 完就是1小时15min

有10瓶药，每瓶有10粒药，其中有一瓶是变质的。好药每颗重1克，变质的药每颗比好药重0.1克。问怎样用天秤称一次找出变质的那瓶药。 编号1-10 分别取1-10颗，重量为x, 坏药编号为 (x - 55) /0.1

有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？ 第一步：把140克盐分成两等份，每份70克。 第二步：把天平一边放上2+7克砝码，另一边放盐，这样就得到9克和61克分开的盐。 第三步：将9克盐和2克砝码放在天平一边，另一边放盐，这样就得到11克和50克。于是50和90就分开了

有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约，另一辆火车以每小时20公里的速度从纽约开往洛杉矶。如果有一只鸟，以外30公里每小时的速度和两辆火车现时启动，从洛杉矶出发，碰到另一辆车后返回，依次在两辆火车来回的飞行，直道两面辆火车相遇，假设洛杉矶到纽约的距离为s, 请问，这只小鸟飞行了多长距离？ 　　那小鸟飞行的距离就是(s/(15+20))*30。 时间 * 速度

你有两个罐子，50个红色弹球，50个蓝色弹球，随机选出一个罐子，随机选取出一个弹球放入罐子，怎么给红色弹球最大的选中机会？在你的计划中，得到红球的准确几率是多少？ 罐1 ： 红1 罐2 ： 红49+蓝50 红概率 = 1/2 * 1 + 1/2 * 49 /（49+50） 约3/4

想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒上下？ 因为人的两眼在水平方向上对称。

病狗问题 一个住宅区内有100户人家，每户人家养一条狗，每天傍晚大家都在同一个地方遛狗。已知这些狗中有一部分病狗，由于某种原因，狗的主人无法判断自己的狗是否是病狗，却能够分辨其他的狗是否有病，现在，上级传来通知，要求住户处决这些病狗，并且不允许指认他人的狗是病狗(就是只能判断自己的)，过了7天之后，所有的病狗都被处决了，问，一共有几只病狗?为什么? https://www.bilibili.com/video/av27732823/

李永乐老师，yyds

桌上有100个苹果，你和另一个人一起拿，一人一次，每次拿的数量大于等于1小于等于5，问：如何拿能保证最后一个苹果由你来拿？ 分析：如果要保证拿最后一个，那么就得保证拿到第94个，以此类推，要拿第94个，就要保证拿到第88个、82、76、70…最后只要保证你拿到第四个就行了，所以看下面：

解答：只需要你先拿，第一次拿4个，以后看对方拿的个数，根据对方拿的个数，保证每轮对方和你拿的加起来是6就行了，其实就是保证你拿到4，还要拿到10,16…直到94

两位盲人 , 他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。 他们每人怎样才能取回黑袜和白袜各两对呢？ 每一对分开，一人拿一只，因为袜子不分左右脚的；

一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？ 病狗问题

有三筐水果，一筐装的全是苹果，第二筐装的全是橘子，第三筐是橘子与苹果混在一起。筐上的标签都是错的 , 你的任务是拿出其中一筐，从里面只拿一只水果，然后正确写出三筐水果的标签。 从标着“混合”标签的筐里拿一只水果，就可以知道另外两筐装的是什么水果了。

一个小猴子边上有100 根香蕉，它要走过50 米才能到家，每次它最多搬50 根香蕉，每走1 米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。 设 小猴从 0 走到 50, 到 A 点时候他可以直接抱香蕉回家了, 可是到 A 点时候他至少消耗了3A 的香蕉( 到A, 回0, 到A), 一个限制就是小猴只能抱 50 只香蕉, 那么在 A 点小猴最多 49 只香蕉.100-3A=49, 所以A=17.

0 -> 17 放下 50 - 2*17 = 16 根

17-> 0 消耗完

0 -> 17 还有 50 - 17 + 16 = 49 根

直接回家 49 - （50 - 17） = 16 根

连续整数之和为1000的共有几组？ 首先1000为一个解。连续数的平均值设为x，1000必须是x的整数倍。假如连续数的个数为偶数个，x就不是整数了。x的2倍只能是5，25，125才行。因为平均值为12.5,要连续80个达不到。125/2 = 62.5是可以的。即62，63，61，64，等等。连续数的个数为奇数时，平均值为整数。1000为平均值的奇数倍。1000 = 2×2×2×5×5×5；x可以为2，4，8，40，200排除后剩下40和200是可以的。所以答案为平均值为62.5，40，200，1000的4组整数。

leetcode 相关：

https://leetcode-cn.com/problems/consecutive-numbers-sum/

18#楼给了个好一些的解法，大家可以参考一下

据说有人给酒肆的老板娘出了一个难题：此人明明知道店里只有两个舀酒的勺子，分别能舀7两和11两酒，却硬要老板娘卖给他2两酒。聪明的老板娘毫不含糊，用这两个勺子在酒缸里舀酒，并倒来倒去，居然量出了2两酒，聪明的你能做到吗？ 7 0

0 7

7 7

3 11

3 0

0 3

7 3

0 10

7 10

6 11

6 0

0 6

7 6

2 11

在9个点上画10条直线，要求每条直线上至少有三个点？

五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死，不能交流，可以摸出剩下绿豆的数量，谁的存活几率最大？ 1、他们都是很聪明的人；2、他们的原则是先求保命，再去多杀人；3、100颗不必都分完，但要保证每人至少抓一颗；4、若有重复的情况，则也算最大和最小，一并处死。 https://www.zhihu.com/question/19912025

有甲、乙两人，其中，甲只说假话，而不说真话；乙则是只说真话，不说假话。但是，他们两个人在回答别人的问题时，只通过点头与摇头来表示，不讲话。有一天，一个人面对两条路：A与B，其中一条路是通向京城的，而另一条路是通向一个小村庄的。这时，他面前站着甲与乙两人，但他不知道此人是甲还是乙，也不知道“点头”是表示“是”还是表示“否”。现在，他必须问一个问题，才可能断定出哪条路通向京城。那么，这个问题应该怎样问？ 这个人只要站在A与B任何一条路上，然后，对着其中的一个人问：“如果我问他（甲、乙中的另外一个人）这条路通不通向京城，他会怎么回答？”如果甲与乙两个人都摇头的话，就往这条路向前走去，如果都点头，就往另一外一条走去。

f( g(x ) ) = g( f( x ) )

甲、乙、丙三个人在一起做作业，有一道数学题比较难，当他们三个人都把自己的解法说出来以后，甲说：“我做错了。”乙说：“甲做对了。”丙说：“我做错了。” , 在一旁的丁看到他们的答案并听了她们的意见后说：“你们三个人中有一 个人做对了，有一个人说对了。”请问，他们三人中到底谁做对了？ 假设丙做对了，那么甲、乙都做错了，这样，甲说的是正确的，乙、丙都说错了，符合条件，因此，丙做对了。

50名运动员按顺序排成一排，教练下令：“单数运动员出列！”剩下的运动 员重新排列编号，教练又下令：“单数运动员出列！”如此下去，最后只剩下一个人，他是几号运动员？最后剩下的又是谁？ 教练下令“单数”运动员出列时，教练只要下5次命令，就能知道剩下的那个人。此人在下第五次令之前排序为2，在下4次令之前排序为4，在下3次令之前排序为8，在下2次令之前排序为16，在下1次令之前排序为32，即32位运动员。 因此：32号。

赵女士买了一些水果和小食品准备去看望一个朋友，谁知，这些水果和小食品被他的儿子们偷吃了，但她不知道是哪个儿子。为此，赵女士非常生气，就盘问4个儿子谁偷吃了水果和小食品。老大说道：“是老二吃的。”老二说道：“是老四偷吃的。”老三说道：“反正我没有偷吃。”老四说道：“老二在说谎。”这4个儿子中只有一个人说了实话，其他的3个都在撒谎。那么，到底是谁偷吃了这些水果和小食品？ 是老三偷吃了水果和小食品，只有老四说了实话。用假设法分别假设老大、老二、老三、老四都说了实话，看是否与题意矛盾，就可以得出答案

某企业老板在对其员工的思维能力进行测试时出了这样一道题：某大型企业的员工人数在1700～1800之间，这些员工的人数如果被5除余3，如果被7除余4，如果被11除余6。那么，这个企业到底有多少员工？员工小王略想了一下便说出了答案，请问他是怎么算出来的？ 对题目中所给的条件进行分析，假如把全体员工的人数扩大2倍，则它被5除余1，被7除余1，被11除余1，那么，余数就相同了。假设这个企业员工的人数在3400 - 3600之间，满足被5除余1，被7除余1，被11除余1的数是

( x - 1 ) % 5 ==0

( x - 1 ) % 7 ==0

( x - 1 ) % 11 ==0

lcm (5 , 7 , 11 ) = 35 * 11 = 385

385 * 9 = 3465

x = 3466，符合要求，所以这个企业共有1733个员工。

老师让幼儿园的小朋友排成一行，然后开始发水果。老师分发水果的方法是这样的：从左面第一个人开始，每隔2人发一个梨；从右边第一个人开始，每隔4人发一个苹果。如果分发后的结果有10个小朋友既得到了梨，又得到了苹果，那么这个幼儿园有多少个小朋友？ 158个小朋友。10个小朋友拿到梨和苹果最少人数是（2+1）×（4+1）×（101）+1=136人，然后从左右两端开始向外延伸，假设梨和苹果都拿到的人为“1”，左右两边的延伸数分别为：3×5－3=12人，3×5－5=10人。所以，总人数为136+12+10=158。

有一个外地人路过一个小镇，此时天色已晚，于是他便去投宿。当他来到一个十字路口时，他知道肯定有一条路是通向宾馆的，可是路口却没有任何标记，只有三个小木牌。第一个木牌上写着：这条路上有宾馆。第二个木牌上写着：这条路上没有宾馆。第三个木牌上写着：那两个木牌有一个写的是事实，另一个是假的。相信我，我的话不会有错。假设你是这个投宿的人，按照第三个木牌的话为依据，你觉得你会找到宾馆吗？如果可以，那条路上有宾馆哪条路上有宾馆 假设第一个木牌是正确的，那么第一个小木牌所在的路上就有宾馆，第二条路上就没有宾馆，第二句话就该是真的，结果就有两句真话了；假设第二句话是正确的，那么第一句话就是假的，第一二条路上都没有宾馆，所以走第三条路，并且符合第三句所说，第一句是错误的，第二句是正确的。

有一富翁，为了确保自己的人身安全，雇了双胞胎兄弟两个作保镖。兄弟两个确实尽职尽责，为了保证主人的安全，他们做出如下行事准则： a．每周一、二、三，哥哥说谎； b．每逢四、五、六，弟弟说谎； c．其他时间两人都说真话。 一天，富翁的一个朋友急着找富翁，他知道要想找到富翁只能问兄弟俩，并且他也知道兄弟俩个的做事准则，但不知道谁是哥哥，谁是弟弟。另外，如果要知道答案，就必须知道今天是星期几。于是他便问其中的一个人：昨天是谁说谎的日子？结果两人都说：是我说谎的日子。你能猜出今天是星期几吗？ 首先分析，兄弟两个必定有一个人说真话，其次，如果两个人都说真话，那么今天就是星期日，但这是不可能的，因为如果是星期日，那么两个人都说真话，哥哥就说谎了。 假设哥哥说了真话，那么今天一定就是星期四，因为如果是星期四以前的任一天，他都得在今天再撒一次谎，如果今天星期三，那么昨天就是星期二，他昨天确实撒谎了，但今天也撒谎了，与假设不符，所以不可能是星期一、二、三。由此类推，今天也不会是星期五以后的日子，也不是星期日。 假设弟弟说了真话，弟弟是四五六说谎，那么先假设今天是星期一，昨天就是星期日，他说谎，与题设矛盾；今天星期二，昨天就是星期一，不合题意；用同样的方法可以去掉星期三的可能性。如果今天星期四，那么他今天就该撒谎了，他说昨天他撒谎，这是真话，符合题意。假设今天星期五，他原本应该撒谎但他却说真话，由“昨天我撒谎了”就知道不存在星期五、六、日的情况，综上所述，两个结论都是星期四，所以今天星期四。

对地理非常感兴趣的几个同学聚在一起研究地图。其中的一个同学在地图上标上了标号A、B、C、D、E，让其他的同学说出他所标的地方都是哪些城市。甲说：B是陕西。E是甘肃；乙说：B是湖北，D是山东；丙说：A是山东，E是吉林；丁说：C是湖北，D是吉林；戊说：B是甘肃，C是陕西。这五个人每人只答对了一个省，并且每个编号只有一个人答对。你知道ABCDE分别是哪几个省吗？ 假设甲说的第一句话正确，那么B是陕西，戊的第一句话就是错误的，戊的第二句话就是正确的；C是陕西就不符合条件。甲说的第二句话正确。那么E就是甘肃。戊的第二句话就是正确的，C是陕西。同理便可推出A是山东，B是湖北，C是陕西，D是吉林，E是甘肃。

已知：有N架一样的飞机停靠在同一个机场，每架飞机都只有一个油箱，每箱油可使飞机绕地球飞半圈。注意：天空没有加油站，飞机之间只是可以相互 加油。 如果使某一架飞机平安地绕地球飞一圈，并安全地回到起飞时的机场，问：至少需要出动几架飞机？ 注：路途中间没有飞机场，每架飞机都必须安全返回起飞时的机场，不许中途降落。 一共需要6架飞机。假设绕地球一圈为1，3 架飞机同时顺时针飞，在1/8 处 油量为 3/4 3/4 3/4 其中一辆給另外两加满往回飞，此时油量为1，1，到1/4 处 油量为3/4，3/4， 加满一辆，另一辆往回 2/4 ，1，可以飞到3/4 的位置 此时油量为0

3架飞机往逆时针方向飞，在7/8 位置3/4， 3/4， 3/4 ，一架给另两加满然后往回飞 1，1，0，继续飞，在3/4 位置 油量为 3/4， 3/4， 0 ， 平衡一下 2/4 ，2/4 ，2/4 可以把之前的飞机接回去

两个直径分别是2和4的圆环，如果小圆在大圆内部绕大圆转一周，那么小圆自身转了几周？如果在大圆的外部转，小圆自身又要转几周呢？ 小圆能转3周。 分析：两圆的直径分别为2、4，那么半径分别为1、2。假如把大圆剪开并 拉直，那么小圆绕大圆转一周，就变成从直线的一头移动到另一头。因为这条直线长就是大圆的周长，是小圆周长的2倍，所以小圆需要滚动2圈。 但现在小圆在沿大圆滚动的同时，自身还要作转动。小圆在沿着大圆滚动1周并回到原出发点的同时，小圆自身也转了1周。如果小圆在大圆的内部滚动，其自转的方向与滚动的转向相反，因此小圆自身转了1周；如果小圆在大圆的外部滚动，其自转的方向与滚动的转向相同，因此小圆自身转了3周。

在一个夜晚，同时有4人需要过一桥，一次最多只能通过两个人，且只有一只手电筒，而且每人的速度不同。A，B，C，D需要时间分别为：1，2，5，10分钟。问：在17分钟内这四个人怎么过桥？ 总共是17分钟

第一步：A、B过花时间2分钟。

第二步：B回花时间2分钟。

第三步：C、D过花时间10分钟。

第四步：A回花时间1分钟。

第五步：A、B再过花时间2分钟。

more :

https://www.nowcoder.com/discuss/262595?type=post&order=time&pos=&page=2&channel=1009&source_id=search_post https://www.nowcoder.com/discuss/150434?type=post&order=time&pos=&page=2&channel=1009&source_id=search_post https://juejin.im/entry/6844903633759420423

Reference

网上整理的google面试题

https://www.nowcoder.com/discuss/526897