微软近期高频面试题分享 + 分析（五）

最近来微软面试的小朋友通过概率实在太低了，代码老是写不对，我们组已经十连拒了，不得不感叹，现在出的面试题越来越难了，我决定还是上来地里透透题，说点最近我们组面试常考高频题和解析（毕竟岗位机会也不能都让三锅霸占了对不）。招人艰难，看微软机会的小伙伴，也欢迎LinkedIn勾搭：https://www.linkedin.com/in/andy-yongjian-deng-212977200/

注意打招呼的时候备注一下，方便识别友军，hhhh。

带娃有压力，尽量保持一周两更，大家海涵。

往期链接：

微软近期高频面试题分享 + 分析（一）


微软近期高频面试题分享 + 分析（二）


微软近期高频面试题分享 + 分析（三）


微软近期高频面试题分享 + 分析（四）

小猪问题

有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：
选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小猪数。

YankeeDoodle 发表于 2021-5-19 10:35
小猪问题

有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为 ...

这道题初看的时候，很多人会纠结：到底需要多少只小猪，而每只小猪又应该具体如何喝水才能判断出哪只水桶有***？
这道题最开始不要去关注细节，去想到底应该怎么喂水。而是应该先思考在考察哪方面的问题，数组、链表、二叉树还是数学？那么仔细思考就能得出结论，本质上在考察数学中的进制问题。举例说明：

假设：总时间 minutesToTest = 60，死亡时间 minutesToDie = 15，pow(x, y) 表示 x 的 y 次方，ceil(x)表示 x 向上取整
当前有只小猪，最多可以喝 times = minutesToTest / minutesToDie = 4 次水
最多可以喝 4 次水，能够携带 base = times + 1 = 5 个的信息量，也就是（便于理解从 0 开始）：
(1) 喝 0 号死去，0 号桶水有毒
(2) 喝 1 号死去，1 号桶水有毒
(3) 喝 2 号死去，2 号桶水有毒
(4) 喝 3 号死去，3 号桶水有毒
(5) 喝了上述所有水依然活蹦乱跳，4 号桶水有毒
结论是 1 只小猪最多能够验证 5 桶水中哪只水桶含有***，当 buckets ≤ 5 时，answer = 1
那么 2 只小猪可以验证的范围最多到多少呢？我们把每只小猪携带的信息量看成是 base进制数，2 只小猪的信息量就是 pow(base, 2) = pow(5, 2) = 25，所以当 5 ≤ buckets ≤ 25时，anwser = 2
那么可以得到公式关系：pow(base, ans) ≥ buckets，取对数后即为：ans ≥ log(buckets) / log(base)，因为 ans 为整数，所以 ans = ceil(log(buckets) / log(base))

看到这里我们再去关注细节，22 只小猪到底怎么喂水，在上述假设下，能够最多验证 2525 桶水呢？请看下方图画解答：
对于一只猪，可以在1h之内最多喝 4次水(60/15)，但是可以检验5个桶，如果前四次没死，说明第5个桶有毒。
对于2只猪，现在可以让一只猪一下喝5桶水，如图所示的一只猪喝行的五个，一只猪喝列的五个，这样就可以确定哪个桶有毒。
对于3只猪，就是三维的 5 X 5 X 5 ，可以检测125个桶；

YankeeDoodle 发表于 2021-5-21 10:37
rand7()问题

已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。

这题主要考的是对概率的理解。程序关键是要算出rand10，1到10，十个数字出现的考虑都为10%.根据排列组合，连续算两次rand7出现的组合数是7*7=49，这49种组合每一种出现考虑是相同的。怎么从49平均概率的转换为1到10呢？方法是：
1.rand7执行两次，出来的数为a1=rand7()-1，a2=rand7()-1.
2.如果a1*7+a2<40,b=(a1*7+a2)/4+1；如果a1*7+a2>=40,重复第一步。
参考代码如下所示：
int rand7()
{
  return rand()%7+1;
}

int rand10()
{
  int a71,a72,a10;
  do
  {
    a71= rand7()-1;
    a72 = rand7()-1;
    a10 = a71 *7 + a72;
  } while (a10>= 40);
  return (a71*7+a72)/4+1;
}

楼主我想加下你的linkedin，但是显示无效，很想进微软

谢谢楼主 mark住

yzhan145 发表于 2021-5-20 03:00
楼主我想加下你的linkedin，但是显示无效，很想进微软

你再试试，现在可以了

mark 一下 谢谢楼主分享

rand7()问题

已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。

感谢楼主，已加米！linkin已加楼主。