Google电面跪惨了经

匿名者 发表于 2020-10-23 10:56
首先我不确定面试官是不是希望我往有多个可能解的方向想，我当时确实没往这方面想，另外就这个例子而言， ...

问题是如果 不限制重复，你给再多个子序列也没法（在不使用ad hoc限制条件下）确定唯一啊。。。

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

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

huorili 发表于 2020-10-22 09:52
有没有同学帮忙解释一下第一题是什么意思啊？为啥是拓扑排序啊

就是根据子序列建立元素的前后关系，然后解。

lei8845 发表于 2020-10-23 23:59
我也觉得你这个是子序列不充分，比如给定【1,1,2,1,1,1,1】，【1,1,1,1,2,1】，在给定长度是9，应该就能 ...

啊。。。唯一吗？我在没看到你答案之前立马想到的其实是[1,1,1,1,2,1,1,1,1]

第二题， 如果是贪心， 应该是先找category和颜色不同的匹配。没有了就找category相同或者颜色相同的中数量多的匹配。 如果再找不到，就直接在完全相同中匹配。 不知道这个是不是最优解。

说实话，就算按这个思路， 代码也不是很好写。 感觉还是要用到max heap, 而且每一次match都可能要搜索所以不同的groups。

大家还有什么更好的思路吗？

好像不太对。我先删了

突然不紧张了，之前怕做不出题丢人，破罐子破摔

freeaccount 发表于 2020-10-25 11:57
啊。。。唯一吗？我在没看到你答案之前立马想到的其实是[1,1,1,1,2,1,1,1,1]

我去，暴露智商了。。。好尴尬，这么讲的话确实不是唯一的解了，可能当初往这个方向聊楼主就过了。

第二题是最大匹配吧，匈牙利算法，无法满足时用KM算法，这也太难了吧

lei8845 发表于 2020-10-26 21:34
我去，暴露智商了。。。好尴尬，这么讲的话确实不是唯一的解了，可能当初往这个方向聊楼主就过了。

其实。。我也以为我想到的那个是唯一😭