一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
电商初创公司Good Days
招聘SDE/UI/TPM等职位实习生
把贵司招聘信息放这里
查看: 1235|回复: 16
收起左侧

Pocket Gems二面

[复制链接] |试试Instant~ |关注本帖
newgod2500 发表于 2017-6-30 08:26:10 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@PoketGem - 内推 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
电面二:.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

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

代码基本上是这样的,. from: 1point3acres.com/bbs

给一个class XXX, 里面有一个getRandom(), 返回的是[0...int.MaxValue-1]的随机数,然后要你完成另外的一个getRangeRandom(int max), 返回[0....max-1],概率要相等, 并且强调一定要用getRandom()。。。楼主想了下,一开始说暴力用一个List存[0....max-1], 然后再在这个List随机返回。面试官听我说完,就叫我写代码,写完之后他说这是对的,但是不是他想要的,不能使用系统的Random。我想了很久都想不出来别的做法;

最后他直接点破说是用面经上的方法:call getRandom, 如果数字不落在[0..max-1]上,继续call....我想了下说这概率不是1/max, 而是1/int.maxvalue...跟面试官解释了下一开始我以为是1/max, 误会了意思.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后后续的follow up1 是完成一个function: int getKRandom(int[] nums, int k) 。 从nums中抽取k个数,组成一个数组res[k-1], 随机数只能用class XXX的两个函数枚举并返回...
楼主硬着头皮解出来了,基本上是使用LC上类似题目的做法,写完后面试官帮我纠正了swap的位置放错了,然后继续follow up 2

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

后来问问题时问hiring process面试官倒是挺详细的...连下一步是干嘛,最后是干嘛都说得很清楚,还说独立日放假,这轮结果可能会有点晚出。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
提供一个他说的process给大家参考吧: 电1->电2->hiring manager电面(问兴趣之类的)->on-site(4~5轮)->offer
. From 1point 3acres bbs
从暴力解第二题之后楼主基本完全处于要么被面试官带着思路(提示)..要么处于胡扯状态...虽然是个A3面试官,但是内推人说他人挺不错的..抱着一线希望吧..
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

 楼主| newgod2500 发表于 2017-6-30 09:13:58 | 显示全部楼层
JaneHang93 发表于 2017-6-30 09:10
. 1point 3acres 璁哄潧这个电面,和我面的题目完全一样,第二题应该是用蓄水池算法。。。

妹子方便问句为啥没发过面经么.......
回复 支持 1 反对 0

使用道具 举报

JaneHang93 发表于 2017-6-30 09:10:07 | 显示全部楼层
这个电面,和我面的题目完全一样,第二题应该是用蓄水池算法。。。
回复 支持 1 反对 0

使用道具 举报

 楼主| newgod2500 发表于 2017-6-30 09:11:37 | 显示全部楼层
JaneHang93 发表于 2017-6-30 09:10
这个电面,和我面的题目完全一样,第二题应该是用蓄水池算法。。。
. From 1point 3acres bbs
我当时也知道是蓄水池算法...奈何当时想拿是什么算法...分明就是数学....本着对数学的厌恶就放弃细看了..

补充内容 (2017-6-30 09:12):. more info on 1point3acres.com
是之前看过蓄水池算法,但没悟到核心思想,被表面的数学搞烦了就没看下去了
回复 支持 反对

使用道具 举报

xihanvhai001 发表于 2017-7-19 01:13:33 | 显示全部楼层
请问楼主电面一后多久拿到了电面二呀,谢谢!
回复 支持 反对

使用道具 举报

 楼主| newgod2500 发表于 2017-7-19 01:16:43 | 显示全部楼层
xihanvhai001 发表于 2017-7-19 01:13
请问楼主电面一后多久拿到了电面二呀,谢谢!
. 1point 3acres 璁哄潧
内推人基本上第二天就会知道消息。 我的也是内推人告诉我的,他们至今都没有官方发邮件给我消息呢,应该是默拒了
回复 支持 反对

使用道具 举报

hackenkreuz 发表于 2017-7-20 12:35:58 | 显示全部楼层
感觉各家的面经已经很久没有出现reservoir sampling 了,居然专门考这个
回复 支持 反对

使用道具 举报

雪海轻舞 发表于 2017-9-7 05:03:00 | 显示全部楼层
感觉这家题好难!
回复 支持 反对

使用道具 举报

FF-Ti 发表于 2017-9-7 06:43:19 | 显示全部楼层
lz方便发一下总结的面经题嘛?
回复 支持 反对

使用道具 举报

太阳与石 发表于 2017-10-16 11:26:16 | 显示全部楼层
楼主你好!谢谢你写这么多的分享。我有一个问题,你是怎么知道面试官是谁的?面试之前就知道了吗
回复 支持 反对

使用道具 举报

 楼主| newgod2500 发表于 2017-10-16 22:20:16 | 显示全部楼层
太阳与石 发表于 2017-10-16 11:26
楼主你好!谢谢你写这么多的分享。我有一个问题,你是怎么知道面试官是谁的?面试之前就知道了吗

所有比较正式一点的面试流程都会提前发confirm email, 里面会有面试官姓名,职位。
回复 支持 反对

使用道具 举报

zws1818918 发表于 2017-11-6 14:35:14 | 显示全部楼层
请问楼主,随机数那题,第一题的做法就是一直call那个API,知道落在[0, max- 1]这个范围吗?
回复 支持 反对

使用道具 举报

 楼主| newgod2500 发表于 2017-11-6 23:03:13 | 显示全部楼层
zws1818918 发表于 2017-11-6 14:35
请问楼主,随机数那题,第一题的做法就是一直call那个API,知道落在[0, max- 1]这个范围吗?

是的。这样每次概率就是原来概率,而不是1/max.
回复 支持 反对

使用道具 举报

zws1818918 发表于 2017-11-7 09:12:58 | 显示全部楼层
newgod2500 发表于 2017-11-6 23:03-google 1point3acres
是的。这样每次概率就是原来概率,而不是1/max.

所以概率就是1/int.maxvalue?
回复 支持 反对

使用道具 举报

一家衬衣厂 发表于 2017-12-10 00:23:58 | 显示全部楼层
楼主不知道你还记不记得题目,想请问下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. visit 1point3acres.com for more.
. From 1point 3acres bbs
followup2 是 给你一个infinity stream, 然后你只能keep一个k长度的数组,要求你实时update这个k数组,这个数组里面的每个数字概率都是 1/(length of 已经出现的stream),而且只能使用原题的两个getRandom方法。 楼主此刻不行了脑袋基本浆糊, 面试官帮写了一个代码框架, 我死马当活马医,找了一个理由自圆其说,面试官看了很久.....然后说it works.... (当然楼主自己都不相信it work)
回复 支持 反对

使用道具 举报

 楼主| newgod2500 发表于 5 天前 | 显示全部楼层
一家衬衣厂 发表于 2017-12-10 00:23
楼主不知道你还记不记得题目,想请问下follow up:
follow up1 是用自己写getRangeRandom(int max)得到ran ...

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

使用道具 举报

一家衬衣厂 发表于 5 天前 | 显示全部楼层
newgod2500 发表于 2017-12-13 05:48
follow-up 1理解正确。 原谅我当初没组织好语言....
follow-up 2你理解也是正确的。好像是跟蓄水池算法 ...

好的,已经在其他帖子里看到类似的
谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-18 07:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表