google onsite杯具＋设计题怎么答# JobHunting - 待字闺中
a*q
1 楼
一共5个人，其中3.5个人考coding，数据结构和算法。1.5个人考设计。
coding考了recursion, DP, 二叉树bfs，简单的hash一类的。因为写程序比较快，一共
答了7,8道coding题，难度不超过cracking the code，感觉基本答得还可以，难一点的
题bug还算少，而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法，
除了最后一个面试官很变态。考了两个很简单无难度的code让写，顺序写完（不给时间
检查）以后叫不许动，拍照，然后说你的code有bug，虽然我很快给找出来了，但是给
拍照了。其实最后一个面试官的时候已经有点晕了，他早点说需要一次写对我就会写慢
些，可是他也没有说。。。
然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥，有的
人心里装了一个答案，问的很模糊，你不答到他那个答案他就是不满意。不知道如何解
决这种情况。大概问答过程如下：
He: how would you design a distributed key-value store
Me: DHT or just using clusters
He: details?
Me: we have a large number of machines. first we use a hash function to
retrieve machine ID from the key. Then we connect to the machine and use
another hash function to retrieve the address from the key. Then fetch data
from that address.
He (seems not satisfied): how much space do you need on the master machine?
Me: It depends. If we can use a hash function to derive the IP address of
the machine, we don't need extra space. Otherwise, we need a table to store
key-IP pairs which is XXX large.
He: say more about how you would get the value on one machine
Me: we have two levels of cache, then memory, then disk. We go down to lower
levels if we can't retrieve the value on higher levels. (seems like not
what he expected)
He: how would you fetch the value on the disk? Please fill in a function
char* getData(char *key) { ... }
Me: don't know what he asked is different from what I answered. Ask him a
lot of questions, but haven't got anything useful
He: Think about what the file system is like
Me: Talked about things I know about file systems. Ask him whether he would
like me to write that function based on file system or redesign everything.
He: should be based on file systems.
Me: go from "/", keep iteratively searching for the current directory using
the key, until we hit a file not a directory. Then open that file and read
value and return the value.
整个过程，感觉跟他预想的不一样，跟我预想的也不一样。一直觉得key-value pairs
应该是用分布式的no sql的DB来实现的，没想到要去读file。另外自己对于disk读取的
底层API也不了解，所以答题的时候基本凭想象来答，觉得怎样应该算是reasonable的
。这可能是导致杯具的原因。
有两点教训就是。一，不要觉得自己是new grad就可以只写code，答两道数学题，他们
真的什么都考，特别是这种large scale的，什么问题都可以问。二，两个面试之间一
定要take a break，就算不上厕所也要去一趟洗手间让大脑休息一下，我就是到最后两
个有些晕了，没答好杯具了。
希望对大家面试有所帮助
coding考了recursion, DP, 二叉树bfs，简单的hash一类的。因为写程序比较快，一共
答了7,8道coding题，难度不超过cracking the code，感觉基本答得还可以，难一点的
题bug还算少，而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法，
除了最后一个面试官很变态。考了两个很简单无难度的code让写，顺序写完（不给时间
检查）以后叫不许动，拍照，然后说你的code有bug，虽然我很快给找出来了，但是给
拍照了。其实最后一个面试官的时候已经有点晕了，他早点说需要一次写对我就会写慢
些，可是他也没有说。。。
然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥，有的
人心里装了一个答案，问的很模糊，你不答到他那个答案他就是不满意。不知道如何解
决这种情况。大概问答过程如下：
He: how would you design a distributed key-value store
Me: DHT or just using clusters
He: details?
Me: we have a large number of machines. first we use a hash function to
retrieve machine ID from the key. Then we connect to the machine and use
another hash function to retrieve the address from the key. Then fetch data
from that address.
He (seems not satisfied): how much space do you need on the master machine?
Me: It depends. If we can use a hash function to derive the IP address of
the machine, we don't need extra space. Otherwise, we need a table to store
key-IP pairs which is XXX large.
He: say more about how you would get the value on one machine
Me: we have two levels of cache, then memory, then disk. We go down to lower
levels if we can't retrieve the value on higher levels. (seems like not
what he expected)
He: how would you fetch the value on the disk? Please fill in a function
char* getData(char *key) { ... }
Me: don't know what he asked is different from what I answered. Ask him a
lot of questions, but haven't got anything useful
He: Think about what the file system is like
Me: Talked about things I know about file systems. Ask him whether he would
like me to write that function based on file system or redesign everything.
He: should be based on file systems.
Me: go from "/", keep iteratively searching for the current directory using
the key, until we hit a file not a directory. Then open that file and read
value and return the value.
整个过程，感觉跟他预想的不一样，跟我预想的也不一样。一直觉得key-value pairs
应该是用分布式的no sql的DB来实现的，没想到要去读file。另外自己对于disk读取的
底层API也不了解，所以答题的时候基本凭想象来答，觉得怎样应该算是reasonable的
。这可能是导致杯具的原因。
有两点教训就是。一，不要觉得自己是new grad就可以只写code，答两道数学题，他们
真的什么都考，特别是这种large scale的，什么问题都可以问。二，两个面试之间一
定要take a break，就算不上厕所也要去一趟洗手间让大脑休息一下，我就是到最后两
个有些晕了，没答好杯具了。
希望对大家面试有所帮助
