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

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

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

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

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


正题开始！

区间问题肯定按照区间的起点或者终点进行排序
这道题的思路是先按照起点升序排序，如果起点相同的话按照终点降序排序

为什么这样排序呢，主要考虑到这道题的以下两个特点：
1、要用若干短视频凑出完成视频[0, T]，至少得有一个短视频的起点是 0。
2、如果有几个短视频的起点都相同，那么一定应该选择那个最长（终点最大）的视频

这一条就是贪心的策略，因为题目让我们计算最少需要的短视频个数，如果起点相同，那肯定是越长越好，不要白不要，多出来了大不了剪辑掉嘛。
这样我们就可以确定，如果clips[0]是的起点是 0，那么clips[0]这个视频一定会被选择。
当我们确定clips[0]一定会被选择之后，就可以选出第二个会被选择的视频
我们会比较所有起点小于clips[0][1]的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频
然后可以通过第二个视频区间贪心选择出第三个视频，以此类推，直到覆盖区间[0, T]，或者无法覆盖返回 -1。

解题思路见下图


这道题的数学解法太秀了，简单说下我的理解：
思路及算法
预备知识：贝祖定理
我们认为，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。
你可能认为这有问题：如果往一个不满的桶里放水，或者把它排空呢？那变化量不就不是 x 或者 y 了吗？接下来我们来解释这一点：
首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的；
其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；
再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。
因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a, b使得
ax+by=z
而只要满足 z≤x+y，且这样的 a, b存在，那么我们的目标就是可以达成的。这是因为：
若 a≥0,b≥0，那么显然可以达成目标。
若a<0，那么可以进行以下操作：
往 y 壶倒水；
把 y 壶的水倒入 x 壶；
如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。
重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。
若b<0，方法同上，x 与 y 互换。
而贝祖定理告诉我们， ax+by=z 有解当且仅当 z 是 x, y的最大公约数的倍数。因此我们只需要找到 x, y的最大公约数并判断 z 是否是它的倍数即可。

回溯

一共有 4 个数和 3 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 4 个数字中有序地选出 2 个数字，共有4×3=12 种选法，并选择加、减、乘、除 4 种运算操作之一，用得到的结果取代选出的2个数字，剩下 3 个数字。
然后在剩下的 3 个数字中有序地选出 2 个数字，共有3×2=6 种选法，并选择 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 2 个数字。
最后剩下 2 个数字，有2种不同的顺序，并选择 4 种运算操作之一。
因此，一共有12×4×6×4×2×4=9216 种不同的可能性。
可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 2 个数字，再选择一种运算操作，用计算得到的结果取代选出的 2 个数字，这样列表中的数字就减少了 1 个。重复上述步骤，直到列表中只剩下 1 个数字，这个数字就是一种可能性的结果，如果结果等于 24，则说明可以通过运算得到 24。如果所有的可能性的结果都不等于 24，则说明无法通过运算得到 24。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10^{-6}可以认为是相等。
进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{-6}时，可以认为该数字等于 0。
还有一个可以优化的点。
加法和乘法都满足交换律，因此如果选择的运算操作是加法或乘法，则对于选出的 2 个数字不需要考虑不同的顺序，在遇到第二种顺序时可以不进行运算，直接跳过。

解题思路
1.判断4个数字是否能得到24是比较复杂的，但是两个数字通过四则运算是否能得到24就相当容易了，因此解决此问题的关键在于怎样把4个数字变成3个数字，再变成两个数字。
2.4->3:从4个数字中任取两个(6种可能)进行四则运算，得到五个值分别与剩下的两个数字组合，得到三个数；
3.3->2:从3个数字中任取两个（3种可能）进行四则运算，得到的五个值分别与剩下的一个数字组合，得到两个数；
4.2->结果：将两个数字进行四则运算，若可以得到24，返回true。

谢谢🙏 顺便请问下楼主 约好了面试时间下周，现在想把面试时间推到一个月后，这种可以跟HR 说么？ 感觉自己还没有准备好 😭

24 点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

楼主你好，在Linkedin上发消息一直没有回音啊？

楼主，行不行的linkedin上麻烦回个消息呗

YankeeDoodle 发表于 2021-04-22 19:28:20
24 点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

动态规划确定dp[i][j]的值集？

补充内容 (2021-04-23 11:32 +08:00):
靠，自动更正...
dp[i][j] 的值集

补充内容 (2021-04-23 11:33 +08:00):
疯了，论坛自动更正这么神奇吗
dp_i_j 值集

水壶问题

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
•        装满任意一个水壶
•        清空任意一个水壶
•        从一个水壶向另外一个水壶倒水，直到装满或者倒空
输入: x = 3, y = 5, z = 4  输出: True

milanism 发表于 2021-4-23 10:36
楼主你好，在Linkedin上发消息一直没有回音啊？

抽空回复哈，人太多了

milanism 发表于 2021-4-23 10:37
楼主，行不行的linkedin上麻烦回个消息呗

抽空回复哈，人太多了，望谅解