微软onsite pass

今天面的微软 下午三点半收到email说过了

1. find most common words

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

U

终于上岸了 之后会把其他公司的相关面经也发出来 祝大家好运！

potplus 发表于 2018-12-31 17:09
楼主好！请问第二题可以稍微具体讲一下吗， 有没有什么思路， 是dp吗？

具体给一个例子讲一下吧
比如说 一串项链是 红（0）红（1）红（2）红（3）绿（4）绿（5）蓝（6）蓝（7）蓝（8）
你就需要在9这个位置上剪 这样的话总和最大是7 （4+3）
假如说你在2这个位置上剪 就不可以 因为总和是4 （3+1）

我一开始给的就是brute force
假设input是double linkedlist 所以在一个位置上都需要算一下总和 然后找到最大的cutting point
面试官要我优化 然后就给出了一个O（n）的解

同样以这个例子 我的想法是 从左到右找出累计的同色数量 再从右到左找出累计的同色数量
所以就是keep two extra arrays
一个array1从左到右就是 1 2 3 4 1 2 1 2 3
一个array2从右到左就是 4 3 2 1 2 1 3 2 1
然后找到那个cutting point that maximizes array1左边的element和array2右边的element

这个方法的问题就在于 会break在 红红红绿绿蓝蓝蓝红 这种头尾是相同颜色的input
所以我给出的解决办法是 cutting point肯定存在在两个不同颜色的分界那边
那这样的话 可以首先把input rearrange一下
比如 刚才记得例子里 红红红绿绿蓝蓝蓝红 就可以rearrange成 红红红红绿绿蓝蓝蓝再做

打字解释起来比较复杂 希望你能看懂 有问题欢迎再问！

补充内容 (2019-1-1 22:35):
好像写了个typo “你就需要在8这个位置上剪 这样的话总和最大是7 （4+3）“
（上面写错了）

kate8528577 发表于 2019-1-2 04:27
你好，我还是没有很看懂，是左边颜色最多的宝石数量加上右边颜色最多的宝石数量么，那这样的话，如果你在 ...

我可能没太说清楚 你想要找到那个cutting point它最大化左边开始连续的颜色+右边开始连续的颜色

这个例子里，红（0）红（1）红（2）红（3）绿（4）绿（5）蓝（6）蓝（7）蓝（8）
你如果在2这个位置上剪掉 它左边的颜色是红色 总共有3个连续的红色 右边的颜色是红色 总共有1个连续的红色
所以是3+1 = 4

芬达 发表于 2019-1-1 22:34
具体给一个例子讲一下吧
比如说 一串项链是 红（0）红（1）红（2）红（3）绿（4）绿（5）蓝（6）蓝（7） ...

你好，我还是没有很看懂，是左边颜色最多的宝石数量加上右边颜色最多的宝石数量么，那这样的话，如果你在2的地方剪掉，左边是3个红宝石，右边是3个蓝宝石，那这样的话和不应该是3+3是6么

请问你是12月14号面试，当天就收到通过的邮件了么

Congrats !!!

对的 两点半面完 三点半收到邮件说过了

求问楼主面的是哪个楼的哪个组

jiangxuanruo 发表于 2018-12-25 02:58
求问楼主面的是哪个楼的哪个组

building 121

补充内容 (2018-12-25 08:41):
intune应该是

芬达 发表于 2018/12/25 08:40:15


building 121

补充内容 (2018-12-25 08:41):
intune应该是

是在Redmond的Office嘛

jiangxuanruo 发表于 2018-12-26 02:52
是在Redmond的Office嘛

对的紫薯紫薯紫薯紫薯

芬达 发表于 2018/12/26 07:49:36


对的紫薯紫薯紫薯紫薯

感谢啦！！恭喜楼主！！

芬达 发表于 2018-12-21 10:28
对的 两点半面完 三点半收到邮件说过了

楼主是有其他的offer deadline么，为啥这么快收到offer