dropbox 面經

dropbox考題很少，準備方法就是把面經看熟就好了
因為是new grad準備很久的lock/concurrency都沒有被考到

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

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

4. Behavior
5. Project deep dive
6. 照片每次被view就會call View(photo id), 給top-k view photo. 一開始假設有整個oracle, 用heap解決。延伸如果view是一個個來，寫了一個很複雜的heap + hashmap。期待的最佳解應該是bucket sort

> 期待的最佳解應該是bucket sort

问题是如果有张照片的views特别高，比如10million。其他的都只有个几百。难道要建10million个bucket来存么？
另外如果一个新的view来了，views总数一变，不是又要从头建一次bucket？

bucket sort 应该是比较好的解法，应该就是 347. Top K Frequent Elements

请问楼主第二题的follow up中， linear update的意思是说 isCompleted（int n） 这个method的时间是O（n）吗？ 那还需要merge 吗

樓主 可否分享一下 關於 id allocator那道題的 binary tree解法 謝謝

马上要onsite 了很紧张，楼主请问你是怎么用binary tree 实现 allocated ID 这题的， TreeNode 是 包含 bitset(1), left TreeNode and right TreeNode.  没有想明白 leaf node 怎么存 0-max -1 ID 的。 详细讲讲你是怎么实现的， 万分感谢。

同new graduate, 刚到电面环节，求问楼主new graduate lock/concurrency 基本不会考嘛？从来没系统地了解过。。。

Why don't you use Queue + Bit array for Allocate id?

Bit array will store the state of the id, if its 1, its used vice versa
Queue will store the available numbers

allocate(): Retrieve from head of queue O(1), set in bit array the number is used O(1)
deallocate(): Add the number to the queue O(1), set bit array the number is free now O(1)

Want to ask how you achieved O(logn) space for allocate id too?