Pocket Gems二面

电面二：

第一道题是 BST继承者，看了面经的都懂。只问了原题（有parent,无value）问了下复杂度 ,楼主本来还期待他在这题疯狂follow up,结果并没有 很快就Move到下一道新题了。

还有40分钟，基本上都纠结在随机取数那道题上，楼主准备了快20道常见电面题，结果没准备那道，要是挂了就是在这题上。

代码基本上是这样的，

给一个class XXX, 里面有一个getRandom(), 返回的是[0...int.MaxValue-1]的随机数，然后要你完成另外的一个getRangeRandom(int max), 返回[0....max-1]，概

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

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

果可能会有点晚出。
提供一个他说的process给大家参考吧： 电1->电2->hiring manager电面(问兴趣之类的)->on-site（4~5轮）->offer

从暴力解第二题之后楼主基本完全处于要么被面试官带着思路(提示）..要么处于胡扯状态...虽然是个A3面试官，但是内推人说他人挺不错的..抱着一线希望吧..

JaneHang93 发表于 2017-6-30 09:10
这个电面，和我面的题目完全一样，第二题应该是用蓄水池算法。。。

妹子方便问句为啥没发过面经么.......

这个电面，和我面的题目完全一样，第二题应该是用蓄水池算法。。。

楼主不知道你还记不记得题目，想请问下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）

JaneHang93 发表于 2017-6-30 09:10
这个电面，和我面的题目完全一样，第二题应该是用蓄水池算法。。。

我当时也知道是蓄水池算法...奈何当时想拿是什么算法...分明就是数学....本着对数学的厌恶就放弃细看了..

补充内容 (2017-6-30 09:12):
是之前看过蓄水池算法，但没悟到核心思想，被表面的数学搞烦了就没看下去了

请问楼主电面一后多久拿到了电面二呀，谢谢！

xihanvhai001 发表于 2017-7-19 01:13
请问楼主电面一后多久拿到了电面二呀，谢谢！

内推人基本上第二天就会知道消息。 我的也是内推人告诉我的，他们至今都没有官方发邮件给我消息呢，应该是默拒了

感觉各家的面经已经很久没有出现reservoir sampling 了，居然专门考这个

感觉这家题好难！

lz方便发一下总结的面经题嘛？

楼主你好！谢谢你写这么多的分享。我有一个问题，你是怎么知道面试官是谁的？面试之前就知道了吗