查看: 2798|回复: 12
收起左侧

[高频题] 微软近期高频面试题分享 + 分析(五)

  |只看干货
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

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

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

往期链接:

微软近期高频面试题分享 + 分析(一)


微软近期高频面试题分享 + 分析(二)


微软近期高频面试题分享 + 分析(三)


微软近期高频面试题分享 + 分析(四)

评分

参与人数 14大米 +17 收起 理由
小马3107 + 3 给你点个赞!
YunkiNi + 1 赞一个
frandblinkc + 1 赞一个
lowcore + 1 赞一个
nbcruz + 1 赞一个
ydog5 + 1 赞一个
jommee + 1 赞一个
mvrunner + 1 赞一个

查看全部评分


上一篇:刷题路上有什么曾经你认为很难做到,如今却做到了的事情?
下一篇:从114. Flatten Binary Tree to Linked List展开兼谈Tree的传值问题
 楼主| YankeeDoodle 2021-5-19 10:35:19 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
小猪问题

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

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

使用道具 举报

yzhan145 2021-5-20 03:00:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
楼主我想加下你的linkedin,但是显示无效,很想进微软
回复

使用道具 举报

wyb1998 2021-5-20 03:24:40 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
谢谢楼主 mark住
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-20 11:01:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
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个桶;


无标题.png
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-20 11:16:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
yzhan145 发表于 2021-5-20 03:00
楼主我想加下你的linkedin,但是显示无效,很想进微软

你再试试,现在可以了
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (20)
 
 
4% (1)    👎
mark 一下 谢谢楼主分享
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-21 10:37:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
rand7()问题

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

使用道具 举报

 楼主| YankeeDoodle 2021-5-22 10:23:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
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;
}

评分

参与人数 2大米 +2 收起 理由
ourgit + 1 经典概率算法题
frandblinkc + 1 赞一个

查看全部评分

回复

使用道具 举报

ydog5 2021-5-22 11:38:10 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (49)
 
 
0% (0)    👎
感谢楼主,已加米!linkin已加楼主。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表