《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 347|回复: 4
收起左侧

丢盒子昂赛特

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

2017(10-12月) 码农类 硕士 全职@Dropbox - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
全部都是面经题:
1. live game。 follow up是input如果1million*1million怎么办。
2. 午饭+demo,不知道算不算一轮,不过demo的时候会问大家问题也会叫你提问。产品感觉很厉害,不是科班出身,好多都没听懂。。。. 1point3acres.com/bbs
3. photo id. 会问时间空间复杂度,最后的follow up就是优化,最后用了一个doublelinklist+两个hashmap的解法。。。也不知道对不对。。。一个hashmap key 是photo id, value是frequency。 另一个hashmap key是frequency,value是doublelinkedlist里的node。node有一个frequency的attribute还有一个对应photoid的set.
4. allocate id。就是之前面经提到的用queue,然后bitset,然后segment tree。bitset没有叫我implement, 其他两个都需要implement出来。Segment就是参照leetcode一道segment tree的思路。
5. web crawler. 最开始就是DFS直接做。没有准备这题的multithreading。。。不太会。在小哥的引导下,大致写了一个用producer/consumer model的方法, 大致就是有个thread一直从queue里读出url, 然后其他thread去geturl然后把新得到的url push回queue。反正写到最后还是有些问题。不过也尽力了。

听闻他家bar很高,所以也是抱着试一试的心态。不过面完之后还挺喜欢他家的,突然有点想拿offer。求人品爆发!.1point3acres缃

评分

2

查看全部评分

Margaret601 发表于 2017-11-12 07:19:34 | 显示全部楼层
你好LZ,有几个小问题关于photo那个题:
1. 你说的“value是doublelinkedlist里的node”,这个node是你自己定义的类吗?为什么需要double linked list呢?
2. 我查了一下题目,意思是实现两个函数,一个是void view(int id), 一个是 List<Integer> getTopM(int m)(是这样的吗?)请问面试官会给ID的范围吗?
3. 我的做法是定义了一个photo的类,有ID和frequency两个attribute;然后自己定义了一个maxHeap, 最后写了一个view() - lgN, getTopM() - mlgN的解法,请问这能达到面试官想要的time不?. 1point 3acres 璁哄潧

不好意思问题有点多……先提前祝个offer!
回复 支持 反对

使用道具 举报

黑眼圈 发表于 2017-11-12 08:00:53 | 显示全部楼层
Margaret601 发表于 2017-11-12 07:19
你好LZ,有几个小问题关于photo那个题:. visit 1point3acres.com for more.
1. 你说的“value是doublelinkedlist里的node”,这个node是你自 ...

那个只是我自己想的方法。所以所有东西都是我自己定义的。我的那个想法有点类似bucket sort。感觉好像会比heap的方法快?应该view是O(1),getTopM是O(M)。然后面试官其实没有限定说要什么time。单纯只是叫你优化。只是最开始getTopM只call一次,followup是getTopM可以call很多次,然后iterator每次只能得到下一个view,不能从头开始再把所有记录再读一遍。
回复 支持 反对

使用道具 举报

Margaret601 发表于 2017-11-12 11:11:27 | 显示全部楼层
黑眼圈 发表于 2017-11-12 08:00
.1point3acres缃那个只是我自己想的方法。所以所有东西都是我自己定义的。我的那个想法有点类似bucket sort。感觉好像会 ...

哦哦这样啊;可是为什么bucket sort可以view O(1), getTopM() 是O(m)呢?我试了一下bucket sort来做getTopM(), 得出的是O(n) , n是当前出现过的所有frequency的种类,我是这么申明的:List<Photo>[] bucket = new List[n],然后遍历了一遍,最后输出K个,所以时间就是o(n)了,请问LZ是怎么优化的呀 真是快被逼疯了……

谢谢你的回复!

补充内容 (2017-11-12 11:19):. more info on 1point3acres.com
还有一个疑问就是 getTopM call一次和call多次有什么区别。。。我感觉啥也不影响哇 谢谢你!
回复 支持 反对

使用道具 举报

 楼主| victorlbb 发表于 2017-11-12 11:22:07 | 显示全部楼层
Margaret601 发表于 2017-11-12 11:11
哦哦这样啊;可是为什么bucket sort可以view O(1), getTopM() 是O(m)呢?我试了一下bucket sort来做getT ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我其实也不知道对不对。有个doublelinkedlist的话getTopM就直接tail往前开始得到top m的photoid吧就不需要new List[n]了。doublelinkedlist是要自己内部维护的。然后view是O(1)的话是因为有两个hashmap记录了啊,hm1记录了这个photoid是否出现过以及他出现过几次,而hm2可以找到相应frequency对应doublelinkedlist里面的node。如果node本来就在doublelinkedlist存在,直接把photoid加到对应node的set里面就好了,不在的话就新建出一个node, 然后改变prev,next指针。。。大致思路就是这样。不知道讲清楚没。。。

补充内容 (2017-11-12 11:25):. more info on 1point3acres.com
多次call可以想象成,会有源源不断的view进来,然后你要隔一段时间call一个gettopm
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 03:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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