查看: 4328|回复: 16
收起左侧

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

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

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

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

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

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

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

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


正题开始!

评分

参与人数 11大米 +16 收起 理由
tl2k3 + 3 很有用的信息!
桂生 + 1 赞一个
v1rar1v + 1 给你点个赞!
nzdwssm + 1 赞一个
sddlpeter + 1 赞一个
wandererSF + 2 给你点个赞!
rachelee + 1 赞一个
resco + 2 给你点个赞!

查看全部评分


上一篇:binarysearch.com开房间同场竞技
下一篇:最新AWS Machine Learning Specialty 证书备考经验
 楼主| YankeeDoodle 2021-4-28 10:45:20 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
区间问题肯定按照区间的起点或者终点进行排序
这道题的思路是先按照起点升序排序,如果起点相同的话按照终点降序排序

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

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

使用道具 举报

 楼主| YankeeDoodle 2021-4-26 10:19:52 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
解题思路见下图


这道题的数学解法太秀了,简单说下我的理解:
思路及算法
预备知识:贝祖定理
我们认为,每次操作只会让桶里的水总量增加 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 是否是它的倍数即可。
无标题.png

评分

参与人数 1大米 +1 收起 理由
桂生 + 1 赞一个

查看全部评分

回复

使用道具 举报

伊evaY 2021-4-23 10:25:37 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (848)
 
 
1% (16)    👎
谢谢🙏 顺便请问下楼主 约好了面试时间下周,现在想把面试时间推到一个月后,这种可以跟HR 说么? 感觉自己还没有准备好 😭
回复

使用道具 举报

 楼主| YankeeDoodle 2021-4-23 10:28:20 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
24 点游戏

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

使用道具 举报

milanism 2021-4-23 10:36:14 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (606)
 
 
2% (17)    👎
楼主你好,在Linkedin上发消息一直没有回音啊?
回复

使用道具 举报

milanism 2021-4-23 10:37:06 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (606)
 
 
2% (17)    👎
楼主,行不行的linkedin上麻烦回个消息呗
回复

使用道具 举报

Shubin_ren 2021-4-23 11:31:29 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (3984)
 
 
4% (203)    👎
YankeeDoodle 发表于 2021-04-22 19:28:20
24 点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *,/,+,-,(,) 的运算得到 24。
动态规划确定dp[j]的值集?

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

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

使用道具 举报

 楼主| YankeeDoodle 2021-4-24 11:06:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
回溯

一共有 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。

评分

参与人数 3大米 +3 收起 理由
flyfreely + 1 很有用的信息!
fas + 1 赞一个
JYKSsss + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| YankeeDoodle 2021-4-25 09:01:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
水壶问题

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

使用道具 举报

 楼主| YankeeDoodle 2021-4-25 09:19:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
milanism 发表于 2021-4-23 10:36
楼主你好,在Linkedin上发消息一直没有回音啊?

抽空回复哈,人太多了

评分

参与人数 1大米 +1 收起 理由
Wendell_tt + 1 赞一个

查看全部评分

回复

使用道具 举报

 楼主| YankeeDoodle 2021-4-25 09:20:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
milanism 发表于 2021-4-23 10:37
楼主,行不行的linkedin上麻烦回个消息呗

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

使用道具 举报

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

本版积分规则

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