2021 谷歌新鲜电面挂经

刚刚面完谷歌，还是觉得自己太挫。。。没做出来。。。直接上题目
I. 题目：
给一个函数 random(a, b) 这个函数随机generate 数字a到b inclusive.,  实现 generateLotteryCardFunction()

LotteryCard -> 5 x 5 2D Array
第1列 数字1到15

第2列 数字16到3

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

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

字。那我可以调用这个函数N次，然后N次都是一样的数字。我理想的结果应该是在当前那一列调用5次然后每次都给你不一样的数字，那时间复杂度就是 o(5), 但是这个咋实现啊？有大神能解答吗？欢迎大家讨论。

用长度为15的数组存1-15的数字，然后random取得是数组的下标，正常进行洗牌算法五次
random(0,15) 得到的index和数组index 0交换
random(1,15) 得到的index和数组index 1交换
random(2,15) 得到的index和数组index 2交换
。。。

感觉和 https://leetcode.com/problems/shuffle-an-array/ 有点像。 洗牌算法  只不过这次只需要把前5个数字 ”洗“ 出来就够了

可以这样做吗 比如第一次是random(1,15)返回5 下次就调用 random(1,4) + random(6,15), 得出来的两个数字可以用 random(1,2) 选择一下。以此类推，这样的话虽然还是调用次数多了点，但是总归最后能得出来 算下来也是常数？

洗牌算法 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

thorax 发表于 2021-1-21 04:26
洗牌算法 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

多谢大神。。。学习了。。。

何曾渡光 发表于 2021-1-21 05:41
可以这样做吗 比如第一次是random(1,15)返回5 下次就调用 random(1,4) + random(6,15), 得出来的两个数字可 ...

减少范围可以的，反正要跟面试官讨论。。

应该可以二分思维吧， 虽然分出来不一定是对称的。 每次[A. B] 摇出一个x,  然后recursion [A, X - 1], [X + 1,B] , 找到5个就停止。 复杂度应该是constant.

这题二分没问题

rubyfrea 发表于 2021-1-21 06:16
应该可以二分思维吧， 虽然分出来不一定是对称的。 每次[A. B] 摇出一个x,  然后recursion [A, X - 1], [X  ...

大神能具体说说这个二分思维怎么实现吗 感谢感谢 如果有相关链接感激不尽

tw_arthur 发表于 2021-1-21 09:32
感觉和 https://leetcode.com/problems/shuffle-an-array/ 有点像。 洗牌算法  只不过这次只需要把前5个数 ...

能具体讲讲怎么把前五个数字洗出来吗?感谢