Pocket Gems二面

太阳与石 发表于 2017-10-16 11:26
楼主你好！谢谢你写这么多的分享。我有一个问题，你是怎么知道面试官是谁的？面试之前就知道了吗

所有比较正式一点的面试流程都会提前发confirm email， 里面会有面试官姓名，职位。

请问楼主，随机数那题，第一题的做法就是一直call那个API，知道落在[0, max- 1]这个范围吗？

zws1818918 发表于 2017-11-6 14:35
请问楼主，随机数那题，第一题的做法就是一直call那个API，知道落在[0, max- 1]这个范围吗？

是的。这样每次概率就是原来概率，而不是1/max.

newgod2500 发表于 2017-11-6 23:03
是的。这样每次概率就是原来概率，而不是1/max.

所以概率就是1/int.maxvalue？

楼主不知道你还记不记得题目，想请问下follow up：
follow up1 是用自己写getRangeRandom(int max)得到random的index，通过random index得到数组么？不知道这样理解对不对。
follow up2 楼主能分享下思路么？是不是除了长度为k的数组不能用其他存储空间。。应该要怎么做？


然后后续的follow up1 是完成一个function: int getKRandom(int[] nums, int k) 。 从nums中抽取k个数，组成一个数组res[k-1], 随机数只能用class XXX的两个函数枚举并返回.... Waral 鍗氬?鏈夋洿澶氭枃绔�,
楼主硬着头皮解出来了，基本上是使用LC上类似题目的做法，写完后面试官帮我纠正了swap的位置放错了，然后继续follow up 2

followup2 是 给你一个infinity stream， 然后你只能keep一个k长度的数组，要求你实时update这个k数组，这个数组里面的每个数字概率都是 1／（length of 已经出现的stream），而且只能使用原题的两个getRandom方法。 楼主此刻不行了脑袋基本浆糊， 面试官帮写了一个代码框架， 我死马当活马医，找了一个理由自圆其说，面试官看了很久.....然后说it works.... （当然楼主自己都不相信it work）

一家衬衣厂 发表于 2017-12-10 00:23
楼主不知道你还记不记得题目，想请问下follow up：
follow up1 是用自己写getRangeRandom(int max)得到ran ...

follow-up 1理解正确。 原谅我当初没组织好语言....
follow-up 2你理解也是正确的。好像是跟蓄水池算法有关，具体我事后没去看。

newgod2500 发表于 2017-12-13 05:48
follow-up 1理解正确。 原谅我当初没组织好语言....
follow-up 2你理解也是正确的。好像是跟蓄水池算法 ...

好的，已经在其他帖子里看到类似的
谢谢！