Dropbox

onsite 15 Mar 2018

https://www.careercup.com/page?pid=dropbox-interview-questions

High Frequent Question for Intern Onsite:

  • Hit Counter
  • Is File Done (can use Heap, someone use heap got offer)
  • Web Crawler
  • Allocate ID

We hope you’ll leave with:

A deeper understanding about what we do and the many challenging problems

we work on

An idea of what we’re building moving forward - we’re nowhere near done yet ;)

A sense of why we love working here

609.Find Duplicate File in System

1. Imagine you are given a real file system, how will you search files? DFS or BFS ?
In general, BFS will use more memory then DFS. However BFS can take advantage of the locality of files in inside directories, and therefore will probably be faster

*in a common user’s operating system, the depth of files is much smaller than the width?

2. If the file content is very large (GB level), how will you modify your solution?
In a real life solution we will not hash the entire file content, since it’s not practical. Instead we will first map all the files according to size. Files with different sizes are guaranteed to be different. We will than hash a small part of the files with equal sizes (using MD5 for example). Only if the md5 is the same, we will compare the files byte by byte

3. If you can only read the file by 1kb each time, how will you modify your solution?
This won’t change the solution. We can create the hash from the 1kb chunks, and then read the entire file if a full byte by byte comparison is required.

What is the time complexity of your modified solution? What is the most time consuming part and memory consuming part of it? How to optimize?
Time complexity is O(n^2 * k) since in worse case we might need to compare every file to all others. k is the file size

How to make sure the duplicated files you find are not false positive?
We will use several filters to compare: File size, Hash and byte by byte comparisons.

1. Would like to buy N bottles of soda.

// Let's assume sodas are sold in packages of 1, 2, 6, 12, 24.鐣欏􀀀璁哄潧-涓€浜¿-涓夊垎鍦¿

// e.g. if N = 10, you could buy 1 x 10, 6 + 2 + 2, 6 + 1 + 1 + 1 + 1, ....

// input : N

// output : all possible combinations, for instance N=10 { {1,1,...,1}, {6,2,2}, {6,1,1,1,1}, {6,2,1,1}, {2,1,..,1}, .... } (don't include {2,2,6} since we have {6,2,2})

combination sum (递归的时间复杂，如何减少递归的层数, dfs时间复杂度O(n!), 还要会用DP写)

39. Combination Sum

DFS(backtracking):

  • time complexity should be n! worst case
  • to reduce recursion depth, we can sort the candidates and terminate earlier in the for loop
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        combinationSum(result, new ArrayList(), candidates, target, 0);
        return result;
    }

    public void combinationSum(List<List<Integer>> result, List<Integer> list, int[] candidates, int target, int index) {
        if(target<0) return;
        if(target==0) {
            result.add(new ArrayList<Integer>(list)); return;
        } 

        for(int i=index; i<candidates.length && candidates[i]<=target; i++) {
            list.add(candidates[i]);
            combinationSum(result, list, candidates, target-candidates[i], i);
            list.remove(list.size()-1);
        }
    }
}

DP:

time complexity should be: R (average result set size for a number t) *N (total candidates num) *T(target num)

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<List<Integer>>> dp = new ArrayList<>();
        Arrays.sort(candidates);

        for(int t=1; t<=target; t++) {
            ArrayList<List<Integer>> newList = new ArrayList<>();
            for(int i=0; i<candidates.length && candidates[i]<=t; i++) {
                if(t==candidates[i]) {
                    newList.add(Arrays.asList(candidates[i]));
                } else {
                    for(List<Integer> list: dp.get(t-candidates[i]-1)) {
                        //this is to pick the list seq which is monotonic increasing
                        //this can avoid duplicates
                        if(candidates[i]>=list.get(0)) { 
                            List<Integer> cumList = new ArrayList<>();
                            cumList.add(candidates[i]); cumList.addAll(list);
                            newList.add(cumList);
                        }
                    }
                }
            }
            dp.add(newList);
        }

        return dp.get(target-1);
    }
}

2. coin change：

一个人去买罐装汽水，只能一罐一罐或者一箱一箱地买。箱子有几种不同大小，比如一箱12罐，一箱6罐等等。这个input是个list。让输出

所有买法（就是每种package买几个这样）DP一下就可以了。给了两种解法，问complexity，推了一下说exponential（画树），但是不是很紧的渐进，面

试官要求再紧一点，做不到…http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

4.phone number + dictionary：

leetcode 上的电话本问题的扩展。区别在于多了一个 dictionary，提供了一个函数 isWord（String word）返回 word 是否在 dictionary 中， 要求是只返回在 dictionary 中的 word。问了复杂度，问了优化方式，需要用 trie，对这个数据结构也不是很熟悉，简单说了一下怎么用，面试官也没细问

初始是7位号码，输出所有可能的单词，用dfs。

然后给一个api判断一个词是否在字典里，只输出在词典里的词，加一句代码，在结果里判断一下。

然后说结果可以是几个小词拼接起来的，小词最短长度是3，dfs函数中加一个变量表示当前词开始的下标。

然后说如果我能访问词典里所有词，能再怎么做？hashmap，key是长度为3或4或7的所有number String，value是这个number string对应的所有单词。

然后说这样还不行，让我另想一个数据结构，主动给hint说，我要判断一个词在不在词典里必须长度足够才行。就是用trie了，不用实现trie，给我两个方法，containpre和

containstr，用dfs再做一下。

然后剩几分钟了，他说可以了，我主动说还能再改进，这样的计算还有冗余的地方，假设前面的两个字符我已经判断出了在前缀树里了，下一层递归我还要在判断一次这两个字

符。改进的方法就是，不用trie的方法，而是直接拿trienode作为传参

8.Num of islands:

matrix是一行一行读进来的（用union find）

if matrix is a 2D grid: DFS/BFS (if BFS, becareful about the timing of the marking... we should mark visited before putting into the queue, otherwise, same cell might be added multiple times by its neighbors!)

  • Use union find id = i*n+j; (will it be very sparse if we use array..?? use hashmap??)

If have time, do num islands II, num of distinct islands, num of distinct islands II

------------------------------------ Onsite Preparation --------------------------------------------

https://instant.1point3acres.com/thread/315076

  1. find bytes in file，我也很紧张面试官美国小哥哥好像也很紧张的样子，不过后来因为他很nice，也很帅就面着面着放松下来了。先implement了string search，然后rolling hash，以及各种conceptual的follow up比如什么样的hash方法会比较理想

  2. lunch，国人小哥哥很温柔，午饭味道还可以，不过牛排竟然是全熟哈哈哈，早知道去吃烤鱼了，饮料很好喝

  3. demo，国人小姐姐很开朗，+hr带着逛building，感觉sf的office不是很大的样子，有个粉嫩嫩可以说非常少女心的library

  4. 亚裔美国小哥哥+国人shadow，刚吃过午饭有些困，加上demo听得太认真，有点精力不足。top k photo view，pq+hashmap，很多follow up包括time complexity和一些别的，中间有些波折，不过还好最后都解决了

  5. 美国好像manager的面试官+国人小哥哥reverse shadow。allocate id，可能是挂点，说了一个integer array解法（后来想想boolean array会更好），被要求优化，只知道可以用tree做所以现场想了一个大概非常规的做法，白板上implement了，其实还有一些问题比如如果backed by array应该bfs而不是dfs寻找下一个available id之类的没有解决，不过确实onsite还是比较intense，已经十分的累了。manager不是很信服，直接站起来说I don't think your method works，lz赶忙解释自己建的Node class，然后shadow小哥哥也帮忙和manager解释，最后好像结果也不是很理想的样子。问问题和送我下楼时manager全程绷着脸，也完全没有在听我问的问题，都是shadow小哥哥回答了我的问题，转头问manager你还有补充么？manager回过神问她说的什么？小哥哥重复我的问题，manager说没有了。。。

看最后一轮面试官的反应，结果应该凶多吉少，不过lz是学数学的大三才double cs，之前基本没有接触过编程，觉得能走到这一步已经很不容易了。究其根本还是自己能力不够强，至少这次感受了一下onsite是一种什么样的体验，以及知道了今后的努力方向。打算今年毕业之后读一个cs的master，来年肯定会再战的。

给大家的建议是多刷题，面经不要只看看要往深处思考。三轮面试都没有让跑code，这个公司应该更注重的还是你的思考过程，好好跟面试官沟通，明白他想让你做什么，以及自己清怎么做之后再说出来/敲出来。

https://instant.1point3acres.com/thread/314870

面经：

log hit：写了两种方法queue和circular array 分析各自利弊

web crawler：写了bfs的代码，问了很多很多thread相关问题，各种优化的follow-up

phone number：问到的follow-up是如何match到长度为3、4、7的单词

allocate id：先写了hashset的解法，然后讨论segment tree并实现了代码

虽然遇到的都是面经题，但每一轮都有发挥不好的地方，写完代码总有些小bug，还是基本功不够好，最后悔的是第三轮明明知道有trie tree的更优解法，但是时间不够，压根没跟面试官提起来……后悔万分

所以总结了一下onsite答题的套路应该是：先clarify题意（go through an example） → propose所有能想到的解法，分析各自利弊/trade-off

→

再跟面试官确认要implememnt哪一种/或者选择自己最有把握的一种来写

→

写完以后先自己check代码 再go through a concrete example

→

分析时间空间

→ 解决

follow-up问题

https://instant.1point3acres.com/thread/314749

超级简单的一道题，给一个文件夹和一个list，list里面是文件夹和其对应的父亲文件夹，还有一个set，里面是哪些文件夹user可以访问，并且user可以访问当前文件夹下的所有文件夹。

现在给一个文件夹，问user能否访问。

很简单的一个递归，没有follow up，但要运行，思路没问题但写了两个typo。。整个流程不到20分钟

面试官是个美国老哥，之前开过公司，老江湖，感觉有点冷淡，没有大家说的那么热情

今天状态也不太好，感觉挂了

https://instant.1point3acres.com/thread/313697

妥妥挂了，跪经奉上。。。

这个新题怎么说呢，有点不按常理出牌, 第一次做这样的题，完全没心理准备，做的很蒙蔽, 一直当算法题总在琢磨考点，怀疑是不是要我在哪造个大轮子。。。全程像在写pseudocode，写的磕磕绊绊，最后问了两个followup就没时间了。。。

总结：更像个OOD + 一点system design 的题，感觉大家做的时候不要想太多，当设计题做，然后需要什么method，记得先问问面试官给不给API，不要像我一样埋头写。。。然后写一半面试官说我给你定义两个方法吧 ORZ。。。

原题如下：NASA 要 Dropbox manage 一个 university panorama, 假设有个 class Image{}，要implement 如下三个方法, 其中 (x, y) 是panorama 上的坐标, 每个坐标上有一个image

class panorama {

public:

panorama(int rows, int cols){

//

initializes the data structure

}

Image fetch (int x, in y){

// check the view on coord(x, y)

}

void update (int x, in y, Image image){

// update contents on (x, y)

}

};

followup:

  1. 如果Image很大怎么办？内存存不下怎么办？如果再大，disk都存不下怎么办？注意考虑IO消耗，怎样存, 读写每个image最高效。

  2. How to get the latest updated image? How to get the oldest updated image？

最后求大米宽慰卤煮受伤的心灵。。。

题目疑似新题 Space Panoram

大意就是实现一个class用来存放image，同时支持update image和fetch image。最开始并没有给File的class，都是后来问了才说我们有这些api。期间会要你计算自己方法占用的内存是多少。

followup要求支持获得oldest的image，也就是最长时间没有更新的image，给了Sector的class，返回image对应的Sector，也就是坐标了。

今天下午面的熱騰騰面經(估計跪了) 就一題李課劉令久和元題不同的事 輸入並不是 String數組而是單一字串, 給的結構是資料夾, 下面在資料夾, 最後有些檔案

要自己判斷檔案是相同的 (檔名可能不同) 問了些Linux的語法和指令

和面觀要了好幾個API來呼叫 最後是給寫出來了 但總覺得要跪 給後面的小夥伴們分享下

https://instant.1point3acres.com/thread/310367

有点像李扣遛灵久，输入是一个list of string表示的是每个file的path，这些file可能有重复的file，输出是list of list of string，重复的file被group在一个利斯特里。

和面试官交流的不太好，全程都是我在说思路他不怎么回答，ask for classification和tradeoff 也会愣个一秒再问我我问了什么（了好几次），最终得到的assumption是这些file可能不能fit in memory，不会给你判断两个文件相同的方法，提到了用hash method他会给你一个interface

Interface SHA256 {

public void update(char

[] byte);[br]

public String compute();

}

然后可以用这个计算最后的hash。

楼主的解法对所有文件先算一遍hashcode, 对所有不能fit in memory的文件做一遍partition，然后对于每个partition通过以上的interface来计算大文件对应的hashcode。所有hash计算完成后再对于每一组hashcode相同的文件路径去判断是否文件相等最后group他们。

https://instant.1point3acres.com/thread/201428

今天刚在丢盒子面了他们家onsite。之前本来压力很大，感觉他家题太难bar太高，实习还要面四轮，简直是去丢人现眼的。但面完感觉还很好，对这个公司印象也超棒。

1.duplicate files，说了用DFS用size hash一轮，再用MD5 hash一轮。follow up的时候又问了文件太大怎么办，答不用md5 hash整个文件，而是一部分一部分地hash。又有follow up是有symlink怎么办，说了存文件absolute path的方法.....就没继续问，不知道有没有更好的方法。

  1. 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方法的两倍。没有见识的我表示好厉害！！没见过！！（好像在地里看到有人提过一句这个题用树做，但没看懂）不过那个时候已经没时间具体写这个方法的码了...要跪。

  2. Lunch interview，一边吃饭一边闲扯一些.......他们家餐厅号称永远不做重样的??? 吓傻简直

  3. Project demo

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

因为有一轮bug多到飞起，我被加面：

加面： n*n matrix, 里面是0到1的double代表格子的高度。开始往matrix里倒水，直到matrix从左到右只有一条路（格子的高度大于等于水高，就是有路）的时候，现在水多高？ 讨论了n^4, n^3，logn*n^2，都不满意，面试官最后直接说n^2，你快写。但是我写出了像一坨翔的DP。最后我和面试官两个人都不想说话了。。。。

https://instant.1point3acres.com/thread/316511

Onsite：

跟indeed比起来，轻松很多。indeed是从早上8点到下午4点，上中午三轮面试一过，大脑就停转了。。。这也是算是indeed的一种考察吧，毕竟工作时也是这个强度。

回归正题，丢盒子上午一轮面试，中午和一小哥吃午饭，下午接着两轮，但是丢盒子的onsite却是我面的最痛苦的一次。由于听说丢盒子对多线程的要求比较高，LZ花了两天时间，把JAVA书多线程部分看了不下5遍，导致面经也没看完。。。

第一轮是五分钟内的点击率，被问了多线程。面试小哥那天感冒了，声音比较低沉，好几次没听清楚他说啥，感觉交流的不是很好。 先写queue，再被问到如果点击次数非常多，怎么办？给出最优解后，还被面试官问是否还有更好的办法。当时lz是惊出一声汗，怎么可能还有更好的解法？！其实面试官是看你是否对自己的解法的肯定。分析了一下复杂度，表示没有更好的了。最后小哥还问了这个解法的名字。。。又是一生冷汗，这个问题怎么准备？！那时脑海里突然出现了面经里看到的一个词,弱弱的说出circle array，怕这个是错的，又加了个move window。。。

中午吃饭的时候，一开始和小哥边吃边聊，挺开心的。聊到一半，indeed来电话把我拒了。瞬间LZ脸就黑了，笑容消失，受到一万点暴击。。。小哥估计也是看出来我悲剧了，于是就各种鼓励我。带我看窗外风景，聊聊西雅图。（丢盒子的人真的都很 nice，期间我也不停地问他当年面试的经验，从中学到了许多。非常感谢那个小哥给我的帮助。）

下午第一轮是文件下载，这题lz没有准备，真的是一点一点和面试官讨论出来的，从理解到找到解题方法。其中也有不少次想错了方向，面试小哥也很快的指出。follow up是实现实时追踪。由于LZ花了太多的时间在第一步上，做follow up时只有大概15分钟左右。。。很快的给出heap的解法，面试官也没跟我细聊就让写代码，其实当时lz的解法有漏洞（不是代码bug），估计面试官当时也没看出来，不然肯定会被指出。lz在第三轮开始的时候才发现。。。

最后一轮是爬虫问题，这题不难，标准的bfs/dfs查找的实际运用问题。也问了多线程，多线程部分也卡了一会儿，在面试小哥帮助下也写出来了。做完后，开始聊天，并提出了第二轮中的bug。小哥说不用担心，那个不是什么大问题。但是LZ还是不放心，面试结束后又给HR发了封感谢信，并提出了第二轮中的bug。。。毕竟当时indeed的挂了，LZ是想尽一切可能抓住这一个机会。

原本不抱希望的，毕竟看到地里其他大神的贴都说丢盒子的bar很高，加上第二轮写出了一个bug。。。但是很幸运的在面试后的第四天拿到offer。

  1. all round - 比较behavioral

  2. design logging system + how to scale

设计分布式日志系统

Implement（假设单线程，一台机器）

  1. OpenTransaction

  2. read( transactionId, key)

  3. write( transactionId, key, value)

  4. commit( transactionId)

假设 key ‘a’ -> 1

小明open transaction 1， write ‘a’ =2, 小明读transactionId ==1 的 Key ‘a’, 应该返回 2

小刚此时open transaction 2, 读transactionId==2 的key ‘a’, 应该返回1 ， 因为小明没有commit

  1. write a ID generator, supports

  2. Constructor ( given the maximum ID number )

  3. alloc() return an unused ID 0-max

  4. release( ID )

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=311489&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

电面：

Sharpness value 和地里面有一个帖子里的题目描述基本一致，直接粘过来了

给了一个二维数组， Find the path from left to right which has the highest minimum sharpness. 路径必须是从左往右，先有个起始点，然后每次要往右上，正右或右下跳一步。也就是说，路径长度是列数n，假设路径为(i1,1),(i2,2),...,(in,n)，路径必须满足每对i_k与i_{k-1}的距离不能大于1.

  • .5 .7 .2
  • .7 .5 .8
  • .9 .1 .5

  • 在这个例子中，理想路径是.7-
    >
    .7-
    >
    .8因为这条路径中的最小值.7在所有路径中最大。只需要返回这个值，不需要返回路径

  • 使用DP解决

  • Follow up

    a. 算 1 million个double数需要多少空间

    b. 问如果文件很大怎么办，如 1 million \* 1 million的矩阵。每次读3 \* 3大小的矩阵

    c. 每次读3 \* 3大小的矩阵怎么算结果的值

d. 问了怎么解决读写文件的disk access耗时的问题

跟hr视频：

hr跟我约了半小时的google hangout，问了问简历，还有一些bq问题，比如除了工作学习之外都有哪些爱好之类的。确定了一下onsite的各种事宜。

onsite：

  1. 第一轮：国人小哥，很nice，由于早去了半个小时，小哥先用中文和我聊了半小时，然后到开始时间了就转换成英文了。

coding：Find Duplicate Files，先提出了基本的做法hash整个文件，然后小哥问如果文件太大了怎么办，那就先算每个文件的size，然后对size相同的文件分块hash。小哥先让我写了hash整个文件的代码，给了个函数接口可以算文件的hash值。然后小哥说给了一个Hasher类，里面有两个函数 void feed(byte[] arr)和 String getHash()，如何实现getHash这个函数。

  1. 第二轮：国人小姐姐。

coding: Phone Number Combination那道题，电话号码的长度是7，先说了基本的dfs方式，问了问复杂度。小姐姐说如果字典里的词的长度为3或4怎么进行剪枝，让实现了代码。然后小姐姐又问如果字典中的词是有限的，怎么办，我说用trie。假设trie已经建好了，如何实现代码。

  1. 第三轮：abc小哥+ 白人叔叔(应该是manager)

coding: read write lock。 先实现了最基本的read write lock，其中包括condition variable的处理，锁的使用方法。然后问会有什么线程安全问题，我举了一个reentrance read lock的例子，然后又问了好多线程安全的问题，让改进代码，具体的lz已经失忆

后来问问题的时候，白人叔叔说dropbox是他工作几十年中，待过最好的最人性化的公司。。。

  1. hr面：我的hr超级nice，由于之前跟hr聊过了，所以没问什么问题，带我在楼里面转了转。丢盒子真是豪气加人性化，很有印象的是有一个很大的房间是供员工睡觉和休息的，里面也可以看电影。还有一个粉红色的图书馆，看得lz少女心爆棚。有一个房间是可以打台球玩乐器的房间。每个楼层都有咖啡室，一楼有一个很大的咖啡厅专门有人为你服务给你做咖啡。天台也是很美～onsite的时候就爱上了这个公司。

1.不一定非得读3 * 3的，可以根据内存大小读一个接近正方形的矩形，然后对第一行和最后一行做特殊处理就行了。如果每次读一整列的话，由于disk access每次读一列要跳转指针，每次指针都要跳转到下一行会产生时间消耗。

  1. 关于计算文件的哈希值（之前写的有误，已改正），由于文件很大，不能一次load到内存中，所以要写个while循环，每次读固定大小的数据。然后再把读取的byte数组传到feed函数中。这里要注意最后一次load的数据可能小于每次固定读的数据的大小，要做一下处理。等所有的数据都处理完之后，再调用getHash这个函数

onsite第一轮的follow up描述的有点问题，在此更正一下。小哥说给了一个Hasher类，里面有两个函数 void feed(byte[] arr)和 String getHash()，如何计算整个文件的哈希值，即实现getFileHashValue() 。 Hasher类中的函数如下使用，例如:第一次读文件的第一块得到byte数组arr1， 第二次读文件的第二块得到byte数组arr2，那么调用feed(arr1),feed(arr2)之后，再调用getHash()就可得到arr1+arr2的哈希值

因为要从文件中读，然后写入另一个文件。由于写指针或读指针跳转到下一行，需要消耗时间。读行输出列，写文件就很耗时，读列输出行，读文件就很耗时。所以选择读一个接近正方形的矩阵会保持这样的平衡。每一次读一块矩阵，然后下一次读的时候要和上一次读的矩阵有至少一行重合，每次要更新上次读的矩阵的最后一行。

第四轮是设计多线程的kv store

results matching ""

    No results matching ""