微软onsite pass

chenghungma 发表于 2018-12-27 14:57
楼主是有其他的offer deadline么，为啥这么快收到offer

我也不太清楚 可能人品比较好？但是我听说他们最近在疯狂面试 可能缺人吧

楼主好！请问第二题可以稍微具体讲一下吗， 有没有什么思路， 是dp吗？

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）“
（上面写错了）

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

谢谢楼主！

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

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

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

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

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

potplus 发表于 2019-1-2 00:38
谢谢楼主！

我的想法是，这个题就是找相邻连续两个数的和最大，比如楼主给的例子，可以转化成数组：4（红），2（绿），3（蓝），注意由于是项链4和3也是相邻的。结果就是4+3最大等于7.

楼主，想问一下你从口头offer到正式offer等了多久呀

jiangxuanruo 发表于 2019-1-10 14:07
楼主，想问一下你从口头offer到正式offer等了多久呀

一天 紫薯紫薯紫薯

芬达 发表于 2019/01/10 15:29:31


一天 紫薯紫薯紫薯

效率好高的！面完之后毫无反应的心好累呜呜呜，说了有offer deadline的结果也毫无用处