丢盒子onsite

[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

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ion。
[color=rgba(0, 0, 0, 0.870588)]

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





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

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)...又说错了...

幻灭天神 发表于 2016-11-29 00:17
楼主有结果了吗？

刚拿到offer!

今年很多人面db啊。（其实原本就很多人，只不过不发帖子。。
下周又有一个~

我是纯粹来围观lz标题的 233

congrats!! db还是那么慷慨。。。

可否麻烦楼主详细说一下allocate id这题题目是什么？没看懂问得是什么  谢谢了！

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

恭喜楼主！能不能透露一下包裹