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

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

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

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

往期链接：
微软近期高频面试题分享 + 分析（一）
微软近期高频面试题分享 + 分析（二）



正题开始！

所以现在三哥三姐们都能把这些题做得很好？

YankeeDoodle 发表于 2021-5-6 10:55
最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在 ...

如果我们使用暴力解法，代码大概是这样的：
for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++)
        if s[i:j] 包含 t 的所有字母:
            更新答案
思路很直接，但是显然，这个算法的复杂度肯定大于 O(N^2) 了，不好。

滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

现有一个房间，墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后，你需要返回这 n 只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 [1, 2, 3 ..., n]，这 4 个按钮的功能如下：
将所有灯泡的状态反转（即开变为关，关变为开）
将编号为偶数的灯泡的状态反转
将编号为奇数的灯泡的状态反转
将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, ...)

00年清华数学系……膜拜Orz

YankeeDoodle 发表于 2021-5-1 21:01
现有一个房间，墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后，你需要返回这 n 只灯泡 ...

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

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-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种。

丢鸡蛋问题
如果你有2颗鸡蛋，和一栋36层高的楼，现在你想知道在哪一层楼之下，鸡蛋不会被摔碎，应该如何用最少的测试次数对于任何答案楼层都能够使问题得到解决。

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)

最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

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