Google电面跪惨了经

最近刚参加google面试，见识到了谷歌难度真不是盖的。目前我也没想出来解法，所以这个是希望大家帮忙提供一下解题思路和方法，就不要求分数了：

Round 1：
中国小哥，输入是一个array的一堆sublists，比如[1,2,3,4,5,6], 输入是[[1,2],[1,3,4],[2,3],[1,5],[4],

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

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

lor, category，输出是配好的pair.

完全没有思路，就是在暴力贪心做，也不知道对不对，最后也没写完，跪了。

第一轮面完说不能决定，临时又加了一轮，结果跪了。

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

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

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

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]

新人，看不了题
乍一看以为是利口司司司
后来发现是构建序列，那就是拓扑排序

缺米，求走过路过的大爷们加米

第一轮的follow up 如果有重复的 那么面试官告知你答案依旧保证唯一？

额，没看懂题目。。第一题啥意思？sublist是[[1,2],[1,3,4],[2,3],[1,5],[4],[4,5]]，那原来的不就是所有元素都并起来，[1,2,3,4,5]么？我哪里理解错了？

第二题也没看懂。。。。题目有点绕，面试的时候理不清楚的啊，可能有个例子会好一些？

第二题 有一个一维的类似的题目
sort了 拿最多的 去match 第二多的
二维的…想破头 mark一下有人解答了踢我一脚

round1 followup如果把重复元素标记出不同呢, 例如1a, 1b, 1c, 然后继续正常拓扑排序可不可以呢. round2好难啊, 有点像max flow的题但又不是..

有没有同学帮忙解释一下第一题是什么意思啊？为啥是拓扑排序啊

是不是第一个题目要按照顺序排列？

qldx 发表于 2020-10-22 08:38
额，没看懂题目。。第一题啥意思？sublist是[[1,2],[1,3,4],[2,3],[1,5],[4],[4,5]]，那原来的不就是所有元 ...

第一题你可以把元素都找出来，但是顺序不能确定吧？需要子数列群来帮助确定元素的前后顺序。

zongmayuerenjia 发表于 2020-10-22 09:24
round1 followup如果把重复元素标记出不同呢, 例如1a, 1b, 1c, 然后继续正常拓扑排序可不可以呢. round2好 ...

我觉得难点是如何分辨出是重复元素，相同的元素出现在不同的子序列的时候不知道如何判断是否需要标记。

ND0406 发表于 2020-10-22 08:31
第一轮的follow up 如果有重复的 那么面试官告知你答案依旧保证唯一？

对，就是子序列足够充分，可以保证唯一性。