车版热帖:大家对买豪车怎么看

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 1558|回复: 16
收起左侧

Pocket Gems二面

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

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

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

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

x
电面二:

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

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

代码基本上是这样的,. Waral 鍗氬鏈夋洿澶氭枃绔,

给一个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面试官倒是挺详细的...连下一步是干嘛,最后是干嘛都说得很清楚,还说独立日放假,这轮结果可能会有点晚出。.鏈枃鍘熷垱鑷1point3acres璁哄潧
提供一个他说的process给大家参考吧: 电1->电2->hiring manager电面(问兴趣之类的)->on-site(4~5轮)->offer

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

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

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

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

使用道具 举报

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

使用道具 举报

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

补充内容 (2017-6-30 09:12):.鏈枃鍘熷垱鑷1point3acres璁哄潧
是之前看过蓄水池算法,但没悟到核心思想,被表面的数学搞烦了就没看下去了
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| newgod2500 发表于 2017-7-19 01:16:43 | 显示全部楼层
xihanvhai001 发表于 2017-7-19 01:13
请问楼主电面一后多久拿到了电面二呀,谢谢!

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

使用道具 举报

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
是的。这样每次概率就是原来概率,而不是1/max.

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

使用道具 举报

一家衬衣厂 发表于 2017-12-10 00:23:58 | 显示全部楼层
楼主不知道你还记不记得题目,想请问下follow up:. visit 1point3acres.com for more.
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)
回复 支持 反对

使用道具 举报

 楼主| newgod2500 发表于 2017-12-13 05:48:24 | 显示全部楼层
一家衬衣厂 发表于 2017-12-10 00:23. 鍥磋鎴戜滑@1point 3 acres
楼主不知道你还记不记得题目,想请问下follow up:
follow up1 是用自己写getRangeRandom(int max)得到ran ...

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-23 21:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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