一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 635|回复: 15
收起左侧

丢盒子onsite

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

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

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

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

x
[color=rgba(0, 0, 0, 0.870588)](一面之前写过,考的log hit)[color=rgba(0, 0, 0, 0.870588)]
. 1point 3acres 璁哄潧
[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)]-google 1point3acres

[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)]-google 1point3acres

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

[color=rgba(0, 0, 0, 0.870588)]4. Project demo . 1point 3acres 璁哄潧
[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..

评分

1

查看全部评分

Pony_s 发表于 2016-11-24 00:32:55 | 显示全部楼层
今年很多人面db啊。(其实原本就很多人,只不过不发帖子。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
下周又有一个~
回复 支持 反对

使用道具 举报

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

使用道具 举报

幻灭天神 发表于 6 天前 | 显示全部楼层
楼主有结果了吗?
回复 支持 反对

使用道具 举报

 楼主| asdf61 发表于 5 天前 | 显示全部楼层

刚拿到offer!
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 5 天前 | 显示全部楼层
congrats!! db还是那么慷慨。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

 楼主| asdf61 发表于 昨天 02:29 | 显示全部楼层
milolyfcmu 发表于 2016-12-4 00:02
可否麻烦楼主详细说一下allocate id这题题目是什么?没看懂问得是什么  谢谢了!
. visit 1point3acres.com for more.
给你一个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 发表于 昨天 03:36 | 显示全部楼层
恭喜楼主!能不能透露一下包裹
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

sf3 发表于 昨天 06:22 | 显示全部楼层
asdf61 发表于 2016-12-4 04:04
实习嘛,没什么包裹....7500/月,有cooperate housing

噢噢,估计住的挺奢华。。
回复 支持 反对

使用道具 举报

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


                               
登录/注册后可看大图


我表述的不大好,大意是图里这个样子。最底下一层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来存的方法相比内存是两倍(这个没说错)。

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

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

使用道具 举报

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

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

使用道具 举报

sf3 发表于 昨天 06:33 | 显示全部楼层
asdf61 发表于 2016-12-4 06:28. Waral 鍗氬鏈夋洿澶氭枃绔,
2B2B四个人住...所以有室友... 不过在DT那么贵,这样已经挺难为人家公司的了

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 16:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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