10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3333|回复: 21
收起左侧

丢盒子onsite

[复制链接] |试试Instant~ |关注本帖
asdf61 发表于 2016-11-23 13:14:47 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Dropbox - 校园招聘会 - Onsite |Otherfresh grad应届毕业生

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

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

x
[color=rgba(0, 0, 0, 0.870588)](一面之前写过,考的log hit)[color=rgba(0, 0, 0, 0.870588)]

[color=rgba(0, 0, 0, 0.870588)]今天刚在丢盒子面了他们家onsite。之前本来压力很大,感觉他家题太难bar太高,实习还要面四轮,简直是去丢人现眼的。但面完感觉还很好,对这个公司印象也超棒。[color=rgba(0, 0, 0, 0.870588)]
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
[color=rgba(0, 0, 0, 0.870588)] 1.duplicate files,说了用DFS用size hash一轮,再用MD5 hash一轮。follow up的时候又问了文件太大怎么办,答不用md5 hash整个文件,而是一部分一部分地hash。又有follow up是有symlink怎么办,说了存文件absolute path的方法.....就没继续问,不知道有没有更好的方法。
[color=rgba(0, 0, 0, 0.870588)]

[color=rgba(0, 0, 0, 0.870588)]2. allocate deallocate ID。先说了用queue存deallocate下来的id的办法,又说了用boolean array存每个ID是否被占用的方法,后来第二个方法又进化成用bit array存......这个时候,bitarray的方法 allocate是O(n), deallocate是O(1)。他space complexity问的很详细,要算多少个byte。 然后这个时候面试官说内存是没法比bit array更小了,但可以牺牲一点内存来让allocate更快。然后提示啊提示,讨论啊讨论,最后一秒我终于领会了他的方法....用tree来表示,root node的left child是一个bit,如果是1的话说明整个array的左半部分有available ID,0表示没有。right child表示右半边有没有available ID。这样一层层partition下去,最后bottom level就是代表整个0-max_id有没有被占用的bit array。这样allocate就是O(n),内存是原来bit array linear search方法的两倍。没有见识的我表示好厉害!!没见过!!(好像在地里看到有人提过一句这个题用树做,但没看懂)不过那个时候已经没时间具体写这个方法的码了...要跪。
[color=rgba(0, 0, 0, 0.870588)]

[color=rgba(0, 0, 0, 0.870588)] 3. Lunch interview,一边吃饭一边闲扯一些.......他们家餐厅号称永远不做重样的??? 吓傻简直
[color=rgba(0, 0, 0, 0.870588)].1point3acres缃

[color=rgba(0, 0, 0, 0.870588)]4. Project demo
[color=rgba(0, 0, 0, 0.870588)]

[color=rgba(0, 0, 0, 0.870588)]5. 电话号码转单词与word break的结合......提出了如果有isPrefix(string)来确认string是不是valid单词的开头这样的API,如何optimize。然后又问了isPrefix()这样的方法怎么implement,说了一下Trie的implementation。
[color=rgba(0, 0, 0, 0.870588)]

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴[color=rgba(0, 0, 0, 0.870588)]总体来说感觉虽然我面的不怎么样,但是这个公司超棒的! 所有的interviewers都很友善,帮着我做题........而且有介绍很多关于自己的工作,都听上去很开心的样子 :D 办公室也超好看,给丢盒子点一个赞

.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


补充内容 (2016-11-30 09:26):
刚拿到了offer :D 他们家在DT SF竟然给housing..

评分

2

查看全部评分

Pony_s 发表于 2016-11-24 00:32:55 | 显示全部楼层
今年很多人面db啊。(其实原本就很多人,只不过不发帖子。。. more info on 1point3acres.com
下周又有一个~
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-24 00:33:35 | 显示全部楼层
我是纯粹来围观lz标题的 233
回复 支持 反对

使用道具 举报

头像被屏蔽
幻灭天神 发表于 2016-11-29 00:17:18 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| asdf61 发表于 2016-11-30 09:24:43 | 显示全部楼层

刚拿到offer!
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-30 09:29:14 | 显示全部楼层
congrats!! db还是那么慷慨。。。
回复 支持 反对

使用道具 举报

milolyfcmu 发表于 2016-12-4 00:02:49 | 显示全部楼层
可否麻烦楼主详细说一下allocate id这题题目是什么?没看懂问得是什么  谢谢了!
回复 支持 反对

使用道具 举报

在浙里 发表于 2016-12-4 00:33:25 | 显示全部楼层
恭喜,楼主拿到offer
回复 支持 反对

使用道具 举报

 楼主| asdf61 发表于 2016-12-4 02:29:09 | 显示全部楼层
milolyfcmu 发表于 2016-12-4 00:02
可否麻烦楼主详细说一下allocate id这题题目是什么?没看懂问得是什么  谢谢了!

给你一个max_id的值,然后写两个function分别是allocate_id和deallocate_id。

allocate_id每次call的时候要返回一个没有被allocate过的available id。如果从1到max_id所有id都被占用了那要做error handling。
deallocate_id(int id)要release被allocate过的这个id,让这个id重新变得available。如果pass in的ID没有被allocate过要做error handling
回复 支持 反对

使用道具 举报

sf3 发表于 2016-12-4 03:36:28 | 显示全部楼层
恭喜楼主!能不能透露一下包裹
回复 支持 反对

使用道具 举报

 楼主| asdf61 发表于 2016-12-4 04:04:00 | 显示全部楼层
sf3 发表于 2016-12-4 03:36
恭喜楼主!能不能透露一下包裹

实习嘛,没什么包裹....7500/月,有cooperate housing
回复 支持 反对

使用道具 举报

duorme 发表于 2016-12-4 06:07:34 | 显示全部楼层
用了树之后,allocate时间是O(n),内存是两倍这句话是不是说错了。。求问这个树该怎么构造还是没看懂,root left child是怎么会是bit而不是node。。
回复 支持 反对

使用道具 举报

sf3 发表于 2016-12-4 06:22:03 | 显示全部楼层
asdf61 发表于 2016-12-4 04:04
实习嘛,没什么包裹....7500/月,有cooperate housing
.1point3acres缃
噢噢,估计住的挺奢华。。
回复 支持 反对

使用道具 举报

 楼主| asdf61 发表于 2016-12-4 06:26:23 | 显示全部楼层
duorme 发表于 2016-12-4 06:07
用了树之后,allocate时间是O(n),内存是两倍这句话是不是说错了。。求问这个树该怎么构造还是没看懂,ro ...
. 鍥磋鎴戜滑@1point 3 acres

                               
登录/注册后可看大图


我表述的不大好,大意是图里这个样子。最底下一层bit array表示那个index所代表的id有没有被占用。然后每往上一层array也是用bit存,是指左边或右边的subarray里有没有available id。如果root是0,就说明整个array里都没有available ID;如果root是1,那就可以继续顺着他是1的child往下找.....这样allocate的时间就是.....O(logN)?对我好像确实说错了。找到以后在bottom up都update一遍,allocate的时间还是O(n)吧

这样假设最下面一层是N bit,每一层加起来可以用geometric series sum算出来(差不多)是2N,所以和之前只用一个bit array来存的方法相比内存是两倍(这个没说错)。. from: 1point3acres.com/bbs

每个bit array之间是树的关系,但在date structure里不一定要有树的结构。因为可以算出每个bit在下一个array里refer to的index,所以我觉得可以直接access,不需要存pointer什么的(如果存了pointer内存就不止大两倍了)

补充内容 (2016-12-4 06:27):. more info on 1point3acres.com
allocate时间是O(logN)...又说错了...
回复 支持 反对

使用道具 举报

 楼主| asdf61 发表于 2016-12-4 06:28:56 | 显示全部楼层
sf3 发表于 2016-12-4 06:22
噢噢,估计住的挺奢华。。

2B2B四个人住...所以有室友... 不过在DT那么贵,这样已经挺难为人家公司的了
回复 支持 反对

使用道具 举报

sf3 发表于 2016-12-4 06:33:45 | 显示全部楼层
asdf61 发表于 2016-12-4 06:28. from: 1point3acres.com/bbs
2B2B四个人住...所以有室友... 不过在DT那么贵,这样已经挺难为人家公司的了

是,贵的不敢想
回复 支持 反对

使用道具 举报

Pony_s 发表于 2016-12-6 04:26:40 | 显示全部楼层
asdf61 发表于 2016-12-4 06:28
2B2B四个人住...所以有室友... 不过在DT那么贵,这样已经挺难为人家公司的了

四个人住有室友??啊那我得考虑下要不要房补。
我另一个实习室2b2b两个人住没有室友我以为dropbox只会更好就直接答应了。(哭
回复 支持 反对

使用道具 举报

milolyfcmu 发表于 2016-12-11 00:50:46 | 显示全部楼层
楼主,我下周去db onsite,还是不太明白allocate id这题,不知可否加微信向你请教一下?可以的话我微信Milolyf
谢谢了!
回复 支持 反对

使用道具 举报

tommyhahn 发表于 2017-2-23 04:28:46 | 显示全部楼层
楼主你好!请问一下allocate ID那个题你提到space complexity 问的比较细,要计算多少个byte, 想问一下能麻烦稍微详细点解释一下吗?谢谢啦
回复 支持 反对

使用道具 举报

 楼主| asdf61 发表于 2017-2-24 09:08:58 | 显示全部楼层
tommyhahn 发表于 2017-2-23 04:28
楼主你好!请问一下allocate ID那个题你提到space complexity 问的比较细,要计算多少个byte, 想问一下能麻 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是比如说你说要用array,每个element里存ID,那他会问你用什么variable存ID,这个variable多少byte,如果有100个ID的话这个array要用多少内存
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 19:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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