狗家onsite面试题

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

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

我覺得用linkedlist + hashMap + Random 解
類似LFU cache

要搞清楚重复的定义，到底是每一堆怎么算不重复。比如牌的种类不一样，数目一样的话，算不算重复？like aabbcc 和 bbccdd 算重复么？ 从我的理解来看，这不算重复。所以才考虑greedy先用掉同一种牌。不过牌a的数量太大，超过了2 * x/y的话， 必须用另外一种策略，就是建立heap, 第一堆用x/y -1张牌啊 , 第二堆用x/y-2张牌a, 直到用完，对后续的牌采用相同的策略

简单来说，如果牌a的数量太大，等于x-1的话，肯定会有重复的。所以一定要把所有的数字assumption先说清楚

匿名用户 发表于 2021-04-15 16:25:59
想问下面试官有啥具体要求吗？不然按greedy，先分完种类一，再分种类二，以此类推就好了。或者一个heap，按每类牌余牌数量挨个分

具体要求就是尽量不选同一种组合，所以你的意思是，11111，11112，2222，22233类似这种吗？那如果k很小，第一堆先都取1，第二堆也都取1，那不就重复了么？

想问下面试官有啥具体要求吗？不然按greedy，先分完种类一，再分种类二，以此类推就好了。或者一个heap，按每类牌余牌数量挨个分

x, y, k有数量限制的吧？

同意楼上的，按种类分配可以最大程度避免重复可能性。如果k种牌的数量都是一样的话， 按照 x/y的数字来取,就是尽量先用掉同一种牌, 保证后面没有重复。

假设有X Y Z 三种牌，因此每一堆牌其实都是由(X, Y, Z)这样的tuple组成
比如第一堆牌(X:1, Y:1, Z:1), 代表 X, Y, Z各一张， (X:1, Y:2, Z:0) 以此类推
其实就是一个backtrack, 对每一堆牌，先挑X有几张，然后Y有几张，然后Z有几张。这样一直到Z结束后，就是一堆牌，并且这样generate出来的牌堆，彼此之间一定不相等，比如(X:1, Y:1, Z:1) 和  (X:1, Y:2, Z:0)一定不相等

lllxin37 发表于 2021-04-15 17:09:06
x, y, k有数量限制的吧？

同意楼上的，按种类分配可以最大程度避免重复可能性。如果k种牌的数量都是一样的话， 按照 x/y的数字来取,就是尽量先用掉同一种牌, 保证后面没有重复。

x是远大于k的数

yueyingjuesha 发表于 2021-04-15 23:35:44
假设有X Y Z 三种牌，因此每一堆牌其实都是由(X, Y, Z)这样的tuple组成
比如第一堆牌(X:1, Y:1, Z:1), 代表 X, Y, Z各一张， (X:1, Y:2, Z:0) 以

随便挑的话，每种牌的数量不一样呀，有可能都挑完了，最后就剩下一种牌分很多堆，这样是不是就重复了？

匿名者 发表于 2021-4-16 14:36
具体要求就是尽量不选同一种组合，所以你的意思是，11111，11112，2222，22233类似这种吗？那如果k很小， ...

是的，有道理。感觉这个考的是洗牌算法，楼主看看384，感觉可能算法上类似只是那个没有重复牌

感觉狗家最近好爱考各种随机算法，太难了 :(