昨天刚面的dropbox onsite，今天来发个帖子希望可以帮到大家，楼主是新人，求。。。
10-11第一轮：在一个很大的file里找一个str，第一个考点在于file很大不能一下子读进内存，所以需要自己写一个nextByte()来一个byte一个byte的读。第二个考点在于优化时间复杂度，用rolling hash可以把时间复杂度从O(NK)优化到O(N)，N是file的长度，K是str的长度，面试官没有让我实现rolling hash（可能是因为我时间不够了）
11-12第二轮：首先是实现isDownloadComplete(chunks, filesize)，chunks表示已经下载好的区间，filesize表示文件大小。比如chunks=[[0,3],[5,8]], filesize=8, 那么isDownloadComplete应该返回FALSE。这里楼主用了排序chunks然后一个个merge的方法，时间复杂度是O(logN)。写完以后followup：chunk是一个一个进来的，所以要实现一个class，支持addChunk(chunk)和isComplete()两个API，楼主当时想法是在class里维持一个sorted的chunks，在addChunk里用python bisect来做binary search然后进行merge，这样的话时间复杂度应该是O(logN)。但是面试官一直想要引导我用heap来做，楼主无法理解为什么要用heap，为此浪费了十多分钟，导致我最后代码没写完。。。。
12-1午饭: 一个刚入职几个月的小姐姐来带着吃饭，不知道吃午饭算不算面试？楼主当时没有太在意，跟小姐姐聊天的时候开了几次小差，因为脑子里还在想上午没面好的题目。。。
1-2 demo：介绍一些dropbox产品
2-3第三轮：allocate id，三种做法：1) set 2)bit array 3)segment tree，每种做法都要分析时间和空间复杂度。前两种面试官只让我说了思路，然后直接实现第三种。
3-4第四轮：多线程web crawl，是一个白人小姐姐面的。楼主之前没写过多线程，所以这一轮就是面试官手把手教我多线程了。。。楼主已经无法记得完整的逻辑，只记得需要用到condition variable, thread pool, notify_all, wait等操作
总结：dropbox每道题都会有很多followup，楼主答题速度太慢，好几轮都有点没面完的感觉，所以建议大家面试的时候注意时间，加快节奏，争取多答点followup的话feedback应该会比较好
最后，。。。。