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

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

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

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

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

x


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


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

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


往期链接:

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

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

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

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

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

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

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

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

评分

参与人数 20大米 +25 收起 理由
xzhang0980 + 1 赞一个
yhb2014ok + 1 给你点个赞!
weiyanyoyo + 1 赞一个
生蚝来十个 + 1 赞一个
saintangelo + 2 手动感谢一下大佬!
supawx + 1 谢谢分享!
Joey2019 + 1 赞一个
kk2019 + 2 感谢楼主!

查看全部评分


上一篇:问个刷题语言的事情
下一篇:5 种方法查看当前系统登录的用户信息
 楼主| YankeeDoodle 2021-7-2 10:24:04 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
YankeeDoodle 发表于 2021-6-30 10:26
丢鸡蛋问题

如果你有2颗鸡蛋,和一栋100层高的楼,现在你想知道在哪一层楼之下,鸡蛋不会被摔碎,应该如 ...

丢鸡蛋问题解析

实际上,我们的终极目的是要找出连续的两层楼$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层楼问题,测试次数实现了减半。
还有种优化的方式是我们手中有两个鸡蛋,尝试使每个鸡蛋的测试任务大致相当,即给100开个平方根,第一个鸡蛋只测试整十楼层,第二个鸡蛋测试两个整十楼层之间的楼层。我们可以先测10楼,20楼,30楼···,直到第一个鸡蛋碎掉。如果我们测到30楼,第一个鸡蛋碎了,那我们就用第二个鸡蛋遍历测试21~29楼。这种策略最糟糕的情况会是99层是临界楼层,测试次数是10+9=19次。最好的情况是1楼是临界楼层,测试次数是1+2=3次。
实际上,如果不限制鸡蛋个数的话,二分思路显然可以得到最少尝试的次数,但问题是,现在给你了鸡蛋个数的限制 K,直接使用二分思路就不行了。
由于要制定一种泛化的策略,所以我们通过观察可以发现。第一颗鸡蛋的测试次数$x$,用来缩小范围;第二颗鸡蛋用来在小范围内查找临界楼层$y$;即$x+y=n$。那么当测试次数固定为$n$时,每当$x$增加1,$y$则减少1(如果n=10,那么第一次探查了20楼,使用了一次机会,如果碎了,确定的范围是1~19,那么,第二颗鸡蛋需要使用10-1=9次机会去探查19层,在最糟糕的情形下显然无法完成。显然当n=10时,第一次探查为10楼显然更合适,确定下来的范围是1~9,第二颗鸡蛋使用10-1次探查9层楼,最糟糕的情形下也能满足);即每当第一颗鸡蛋测试一次,那么所留给第二颗鸡蛋探查的范围就应该减少1。将探查范围相加起来,再加上n就是探查的总范围,即n+(n-1)+...+0 = 100 (100为探测的总范围)。解的$n$刚好为正整数14,即使用此策略最多探查14次即可在100楼中找到临界楼层。另外,当探查总范围发生改变时,解的$n$可能为小数,显然探查次数只能为整数且$n$越小探查总范围越小,即$n$应向上取整。
熟悉动态规划的同学,都应该知道这是一道典型的动态规划题目。
我们可以考虑使用动态规划来做这道题,动态规划的框架是这个问题有什么「状态」,有什么「选择」,然后穷举。
状态就是当前拥有的鸡蛋数 K 和需要测试的楼层数 N,可以表示成$(k,n)$,其中$k$为鸡蛋数,$n$为楼层数。当我们从第$x$楼扔鸡蛋的时候
如果鸡蛋不碎,那么状态变成$(k,n−x)$,即我们鸡蛋的数目不变,但答案只可能在上方的 $n-x$层楼了。也就是说,我们把原问题缩小成了一个规模为$(k,n−x)$的子问题
如果鸡蛋碎了,那么状态变成$(k−1,x−1)$,即我们少了一个鸡蛋,但我们知道答案只可能在第 $x$ 楼下方的$x-1$层楼中了。也就是说,我们把原问题缩小成了一个规模为$(k−1,x−1)$的子问题。
一个简单的示例如下:
1.jpg


这样一来,我们定义$dp(k,n)$为在状态$(k, n)$下最少需要的步数。根据以上分析我们可以列出状态转移方程: $dp(k, n)=1+\min _{1 \leq x \leq n}(\max (dp(k-1, x-1), dp(k, n-x)))$
选择其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路,二分查找每次选择到楼层区间的中间去扔鸡蛋,而线性扫描选择一层层向上测试。不同的选择会造成状态的转移
最后就是要知道动态规划里最基础的状态是什么,当楼层数 N 等于 0 时,显然不需要扔鸡蛋;当鸡蛋数 K 为 1 时,显然只能线性扫描所有楼层。
如果我们直接暴力转移求解每个状态的$dp$值,时间复杂度是为 $O(kn^2)$,即一共有$O(kn)$个状态,对于每个状态枚举扔鸡蛋的楼层x,需要$O(n)$的时间。这无疑在当前数据范围下是会超出时间限制的,因此我们需要想办法优化枚举的时间复杂度。
我们观察到$dp(k, n)$是一个关于$n$的单调递增函数, 第一项$dp(k-1, x-1)$是一个随$x$的增加而单调递增的函数,第二项$dp(k, n-x)$是一个随着$x$的增加而单调递减的函数。那么必然第一项和第二项存在一个交点保证这两个函数相交。在这种情况下,我们需要找到最大的满足$dp(k-1, x-1) < dp(k, n-x)$的最大$x$值,以及最小满足$dp(k-1, x-1) > dp(k, n-x)$的最小$x$值。我们比较两个$x$所对应的函数值,取其中的最小值(因为$min_{1 \leq x \leq n}$)作为最后的$x$值。我们采用二分查找的方式,最终时间复杂度从$O(kn^2)$降低至$O(knlogn)$。
2.png


  1. class Solution {
  2.     unordered_map<int, int> memo;
  3.     int dp(int k, int n) {
  4.         if (memo.find(n * 100 + k) == memo.end()) {
  5.             int ans;
  6.             if (n == 0) {
  7.                 ans = 0;
  8.             } else if (k == 1) {
  9.                 ans = n;
  10.             } else {
  11.                 int lo = 1, hi = n;
  12.                 while (lo + 1 < hi) {
  13.                     int x = (lo + hi) / 2;
  14.                     int t1 = dp(k - 1, x - 1);
  15.                     int t2 = dp(k, n - x);

  16.                     if (t1 < t2) {
  17.                         lo = x;
  18.                     } else if (t1 > t2) {
  19.                         hi = x;
  20.                     } else {
  21.                         lo = hi = x;
  22.                     }
  23.                 }

  24.                 ans = 1 + min(max(dp(k - 1, lo - 1), dp(k, n - lo)),
  25.                                    max(dp(k - 1, hi - 1), dp(k, n - hi)));
  26.             }

  27.             memo[n * 100 + k] = ans;
  28.         }

  29.         return memo[n * 100 + k];
  30.     }
  31. public:
  32.     int superEggDrop(int k, int n) {
  33.         return dp(k, n);
  34.     }
  35. };
复制代码


时间复杂度:$O(knlogn)$。我们需要计算$O(kn)$个状态,每个状态计算时需要 $O(logn)$ 的时间进行二分查找。
空间复杂度:$O(kn)$。我们需要 $O(kn)$ 的空间存储每个状态的解。













回复

使用道具 举报

 楼主| YankeeDoodle 2021-6-30 10:26:32 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
丢鸡蛋问题

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

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

  1. 示例 1:
  2. 输入:k = 1, n = 2
  3. 输出:2
  4. 解释:鸡蛋从 1 楼掉落。如果它碎了,肯定能得出 f = 0 。 否则,鸡蛋从 2 楼掉落。如果它碎了,肯定能得出 f = 1 。
  5. 如果它没碎,那么肯定能得出 f = 2 。 因此,在最坏的情况下我们需要移动 2 次以确定 f 是多少。

  6. 示例 2:
  7. 输入:k = 2, n = 6
  8. 输出:3

  9. 示例 3:
  10. 输入:k = 3, n = 14
  11. 输出:4
复制代码
回复

使用道具 举报

pbw 2021-6-30 12:23:18 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (82)
 
 
0% (0)    👎
楼主真是功德无量🙏
回复

使用道具 举报

二哈最聪明了 2021-6-30 15:46:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
很有用,非常感谢
回复

使用道具 举报

lucinda0518 2021-7-1 01:35:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   73% (226)
 
 
26% (83)    👎
一开始想问楼主这么分享不怕被举报吗,然后LinkedIn一看,微软工作17年的principal manager,膜拜膜拜。感谢分享!
回复

使用道具 举报

avocadolover 2021-7-1 08:40:42 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   86% (79)
 
 
13% (12)    👎
请问楼主hiring event也是同样的高频题么?
回复

使用道具 举报

 楼主| YankeeDoodle 2021-7-3 08:42:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
接雨水问题

给定 $n$ 个非负整数 $a_1,a_2,…,a_n$,每个数代表坐标中的一个点 $(i, a_i)$ 。在坐标内画 $n$ 条垂直线,垂直线 $i$ 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$。找出其中的两条线,使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 $n$ 的值至少为 2。
1.jpg

  1. 示例1
  2. 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
  3. 输出:6
  4. 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
  5. 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

  6. 示例 2:
  7. 输入:height = [4,2,0,3,2,5]
  8. 输出:9
复制代码


回复

使用道具 举报

 楼主| YankeeDoodle 2021-7-4 08:49:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
接雨水问题解析

方法一:暴力法
首先最容易想到的就是暴力去搜索,检验每两个匹配形成的面积有多大,代码如下:
  1. public static int maxArea(int[] height) {

  2.     int max = 0;
  3.     int current;

  4.     for(int i =0; i<height.length - 1; i++){
  5.         for(int j = i+ 1; j< height.length; j++){
  6.             current = (j-i) * Math.min(height[i],height[j]);
  7.             max = Math.max(max,current);
  8.         }
  9.     }

  10.     return max;
  11. }
复制代码


复杂度分析:
时间复杂度:O(n2)。
空间复杂度:O(1)。
回复

使用道具 举报

 楼主| YankeeDoodle 2021-7-5 09:23:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
接雨水问题解析
方法二:双指针法
两线段之间形成的区域总是会受到其中较短那条长度的限制。我们使用两个指针,一个放在开始,一个置于末尾。 在每一步中,我们会计算指针所指向的两条线段形成的区域面积,并将指向较短线段的指针向较长线段那端移动一步。如下:
2.png


  1. public static int maxArea2(int[] height) {

  2.     int max = 0;
  3.     int current = 0;
  4.     int left = 0;
  5.     int right = height.length-1;

  6.     while(left < right){
  7.         current = (right - left) * Math.min(height[left],height[right]);
  8.         max = Math.max(max,current);

  9.         if(height[left] < height[right]){
  10.             left ++ ;
  11.         }else{
  12.             right -- ;
  13.         }
  14.     }

  15.     return max;
  16. }
复制代码



复杂度分析:
时间复杂度:O(n)。
空间复杂度:O(1)。

回复

使用道具 举报

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

本版积分规则

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