<
查看: 1457|回复: 10
收起左侧

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

  |只看干货
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎

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

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

x


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

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

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

往期链接:
微软近期高频面试题分享 + 分析(一)
微软近期高频面试题分享 + 分析(二)



正题开始!

评分

参与人数 6大米 +13 收起 理由
ylian0613 + 2 给你点个赞!
錢霓 + 1 很有用的信息!
Amy217 + 1 给你点个赞!
QueenieV + 5 欢迎分享你知道的情况,会给更多积分奖励!
v1rar1v + 1 给你点个赞!
yuchang1990 + 3 Good job

查看全部评分


上一篇:刷过的题老是忘,怎么办?
下一篇:动态规划子集合类题
Ryan_777 2021-5-3 08:20:50 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   88% (56)
 
 
11% (7)    👎
所以现在三哥三姐们都能把这些题做得很好?
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-2 10:01:04 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
现有一个房间,墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后,你需要返回这 n 只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 [1, 2, 3 ..., n],这 4 个按钮的功能如下:
将所有灯泡的状态反转(即开变为关,关变为开)
将编号为偶数的灯泡的状态反转
将编号为奇数的灯泡的状态反转
将编号为 3k+1 的灯泡的状态反转(k = 0, 1, 2, ...)

评分

参与人数 1大米 +1 收起 理由
泛泛点星辰 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

Ruka 2021-5-3 00:33:36 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (83)
 
 
5% (5)    👎
00年清华数学系……膜拜Orz
回复

使用道具 举报

泛泛点星辰 2021-5-3 00:38:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (79)
 
 
11% (10)    👎
YankeeDoodle 发表于 2021-5-1 21:01
现有一个房间,墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后,你需要返回这 n 只灯泡 ...

我想问这种题目在实际工作当中会应用到吗?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (781)
 
 
5% (43)    👎
YankeeDoodle 发表于 2021-05-01 19:01:04
现有一个房间,墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后,你需要返回这 n 只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 ,这 4 个按钮的功能如下:
这是排列组合题还是模拟题?
其实所有灯泡一共就4种,不管n多大也其实只有4个有效bit(奇数,偶数,3k+1,其他),最多16个可能性,看题目具体情况筛掉不可能的就是了吧?

补充内容 (2021-05-03 01:50 +08:00):
更正一下
奇数且不符合3K+1
偶数切不符合3k+1
奇数且满足3k+1
偶数且满足3k+1
其他
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-3 10:25:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
YankeeDoodle 发表于 2021-5-2 10:01
现有一个房间,墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后,你需要返回这 n 只灯泡 ...

解题思路
1、简化m
每个操作执行奇数次等于执行一次,执行偶数次等于没有执行,所以我们只需要考虑i操作是否执行就好。
2、简化n
a. 将所有灯泡的状态反转(即开变为关,关变为开)
b. 将编号为偶数的灯泡的状态反转
c. 将编号为奇数的灯泡的状态反转
d. 将编号为 3k+1 的灯泡的状态反转(k = 0, 1, 2, ...)

设 a b c d 为四种操作已经执行,!a !b !c !d 为四种操作未执行
简化到6
假设n > 6,所有灯泡已经初始为开,可以看到对于所有状态为灯泡有
Light 1 = true ^ a ^ c ^ d
Light 2 = true ^ a ^ b
Light 3 = true ^ a ^ c
Light 4 = true ^ a ^ b ^ d
Light 5 = true ^ a ^ c
Light 6 = true ^ a ^ b
=========== 重复1~6 ==============
Light 7 = true ^ a ^ c ^ d
Light 8 = true ^ a ^ b
Light 9 = true ^ a ^ c
Light 10 = true ^ a ^ b ^ d
可以发现,第i个灯泡的状态 = 第 i % 6 个灯泡的状态。简单看四个操作的最小公约数也可以求得循环,此时可以求前6个灯泡的所有状态即可
3、简化到3
假设 n>3 进一步思考可以发现,决定所有灯泡的操作为abcd,如果前三个灯泡的状态确定了,就可以得到个四元一次方程,就可以确定abcd的操作是否执行,即前三个灯泡的状态可以决定后续所有灯泡的状态。
Light 1 = true ^ a ^ c ^ d
Light 2 = true ^ a ^ b
Light 3 = true ^ a ^ c
前三个灯泡的状态共有8种,即后续灯泡的状态都由8种决定,所有灯泡的状态也最多只有8种。
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-4 10:04:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
丢鸡蛋问题
如果你有2颗鸡蛋,和一栋36层高的楼,现在你想知道在哪一层楼之下,鸡蛋不会被摔碎,应该如何用最少的测试次数对于任何答案楼层都能够使问题得到解决。
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-5 10:25:02 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
YankeeDoodle 发表于 2021-5-4 10:04
丢鸡蛋问题
如果你有2颗鸡蛋,和一栋36层高的楼,现在你想知道在哪一层楼之下,鸡蛋不会被摔碎,应该如何 ...

解题思路
1、如果你从某一层楼扔下鸡蛋,它没有碎,则这个鸡蛋你可以继续用
2、如果这个鸡蛋摔碎了,则你可以用来测试的鸡蛋减少一个
3、所有鸡蛋的质量相同(都会在同一楼层以上摔碎)
4、对于一个鸡蛋,如果其在楼层i扔下的时候摔碎了,对于任何不小于i的楼层,这个鸡蛋都会被摔碎
5、如果在楼层i扔下的时候没有摔碎,则对于任何不大于i的楼层,这颗鸡蛋也不会摔碎
6、从第1层扔下,鸡蛋不一定完好,从第36层扔下,鸡蛋也不一定会摔碎。

实际上,我们的终极目的是要找出连续的两层楼i,i+1在楼层i鸡蛋没有摔碎,在楼层i+1鸡蛋碎了,问题的关键之处在于,测试之前,你并不知道鸡蛋会在哪一层摔碎,你需要找到的是一种测试方案,这种测试方案,无论鸡蛋会在哪层被摔碎,都至多只需要m次测试,在所有这些测试方案中,m的值最小。

对于只有1颗鸡蛋的情况,我们别无选择,只能从1楼开始,逐层向上测试,直到第i层鸡蛋摔碎为止,这时我们知道,会让鸡蛋摔碎的楼层就是i(或者直到顶层,鸡蛋也没有被摔碎),其他的测试方案均不可行,因为如果第1次测试是在任何i>1的楼层扔下鸡蛋,如果鸡蛋碎了,你就无法确定,i-1层是否也会令鸡蛋摔碎。所以对于1颗鸡蛋而言,最坏的情况是使鸡蛋摔碎的楼层数i>=36,此时,我们需要测试每个楼层,总共36次,才能找到最终结果,所以1颗鸡蛋一定能解决36层楼问题的最少测试次数是36.

对于2个鸡蛋,36层楼的情况,你可能会考虑先在第18层扔一颗,如果这颗碎了,则你从第1层,到第17层,依次用第2颗鸡蛋测试,直到找出答案。如果第1颗鸡蛋没碎,则你依然可以用第1颗鸡蛋在27层进行测试,如果碎了,在第19~26层,用第2颗鸡蛋依次测试,如果没碎,则用第1颗鸡蛋在32层进行测试,……,如此进行(有点类似于二分查找)。

这个解决方案的最坏情况出现在结果是第17/18层时,此时,你需要测试18次才能找到最终答案,所以该方案,解决36层楼问题的测试次数是18。相较于1颗鸡蛋解决36层楼问题,测试次数实现了减半。

递推公式的构造;
def eggDrop(k):
    if k==0 or k==1: return k
    if n==1: return k  #返回实验组 也就是需要重复多少次
    eggDrop(k, n-1)
eggDrop(k-1,n)
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-6 10:55:32 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (181)
 
 
1% (2)    👎
最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
示例 2:
输入:s = "a", t = "a"
输出:"a"
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

X 关闭
>
快速回复 返回顶部 返回列表