1.15 新鲜狗家店面

面试官国人老大哥，挺nice的一道题，是地里的marbles那题，面试前刚扫过一眼面试时候怎么都找不到了。。

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

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

祝大家都找工顺利！！！！

安吉拉鸡 发表于 2019-1-17 10:23
面试官给我的思路是这样的：把marbles分成不同的组，每个组都是share共同的x或共同的y，每个组都可以remo ...

我又想了下，感觉这答案不唯一吧，一个联通量里面的任意一个都可以成为剩下的那个吧，这样在每个组里任选一个就行了

安吉拉鸡 发表于 2019-1-18 03:59
不一定的，ex如果你先删掉第二行最后一个，max num to remove就是2，因为没办法删掉第二行第一个了

第二行跟第四行是一个联通的，但是却有可能第二行的第一个或者第四行的都成为剩下的最后一个，那结果不是唯一的啊

安吉拉鸡 发表于 2019-1-17 10:23
面试官给我的思路是这样的：把marbles分成不同的组，每个组都是share共同的x或共同的y，每个组都可以remo ...

如何选取x和y进行分组呢

sad…我不会隐藏
大家看的开心～

刷题网947吗 楼主用dfs 还是union find 做的啊

input给的怎么这么绕

这题怎么还在用。。。= =

请问follow up怎么做啊

juliawhr 发表于 2019/01/16 07:38:40
刷题网947吗 楼主用dfs 还是union find 做的啊

都不是…面试官给的提示用grouping做的 感觉复杂度要比lc上的高

shaonan 发表于 2019/01/17 09:24:02
请问follow up怎么做啊

面试官给我的思路是这样的：把marbles分成不同的组，每个组都是share共同的x或共同的y，每个组都可以remove到只剩一个marble，所以只求groups的个数就可以了，这种思路的followup只要把每个组的marbles存下来，然后从share的x或y最少的marble开始remove就可以了，最后剩下的一定是share x或y最多的marble，这样是为了保证可以remove掉max num of marbles

shaonan 发表于 2019/01/17 14:57:10


我又想了下，感觉这答案不唯一吧，一个联通量里面的任意一个都可以成为剩下的那个吧，这样在每个组里任选一个就行了

不一定的，ex如果你先删掉第二行最后一个，max num to remove就是2，因为没办法删掉第二行第一个了