Redian新闻
>
google onsite杯具+设计题怎么答
avatar
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,就算不上厕所也要去一趟洗手间让大脑休息一下,我就是到最后两
个有些晕了,没答好杯具了。
希望对大家面试有所帮助
avatar
l*8
2
感觉关于file system,他要你回答B+ tree.
希望有大牛能解答一下。

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

avatar
d*y
3
我胡说几句,可能说得不对,请别介意。
个人觉得,最后一个large scale题目其实答得挺好的,这题不会太失分
如果是我答的话,第一个问题可能不会直接问面试官“DHT,还是cluster”,
这一步可能跳的有点快了,
第一个问题可能会问,key 是什么样的key,value包含哪些(正常的话,面试官会说
key是string,或者什么都可以,value也是什么都可以,之类的,这问题虽然简单,包
含很多信息,问一下这个问题,面试官很轻松的回答你,就表明往这个方向走是对的)。
我的猜测是,这个题不是要考你BigTable是怎么design的,那个估计很多人面试前都准
备过,
其实估计他就是想问最简单的DHT原理,这个题面的设计,甚至于不expect你懂得DHT,
否则他就直接问你tell me something about DHT
(G倾向问比较基本的概念和问题,就算背景是large system,别被现有成熟技术束缚,
想一下不是每个人都有large scale system的研究和工作背景,但是每个人都会被问到
这样的题目,如果有一个人是学EE的,来了也会被问这道题的,他压根就没听过DHT,
他应该怎么答呢?Google就是想看看这个人是如何分析这个问题的。)
所以下面可以马上提到hash table,以及如何distribute key
再看他反应如何,
然后一般来说从一个机器说起,先解决简单问题。
一个机器上就是一个hash table,讲讲这个hash table如何如何
但是没必要提文件系统的事情,一方面memcached tablets和相应文件未必在一个机器
上,
再一方面,keep it simple也是有帮助的。
再说说多个机器之类的。
再说需要balance 不同机器的load,如何rehash
总之一步一步来。
然后code可能就是让写一个简单的读取数据过程?需要在过程中跟面试官确定
比如就是先map key to machine ID,然后fetch value from machine ID,

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

avatar
l*8
4
赞!

)。

【在 d*****y 的大作中提到】
: 我胡说几句,可能说得不对,请别介意。
: 个人觉得,最后一个large scale题目其实答得挺好的,这题不会太失分
: 如果是我答的话,第一个问题可能不会直接问面试官“DHT,还是cluster”,
: 这一步可能跳的有点快了,
: 第一个问题可能会问,key 是什么样的key,value包含哪些(正常的话,面试官会说
: key是string,或者什么都可以,value也是什么都可以,之类的,这问题虽然简单,包
: 含很多信息,问一下这个问题,面试官很轻松的回答你,就表明往这个方向走是对的)。
: 我的猜测是,这个题不是要考你BigTable是怎么design的,那个估计很多人面试前都准
: 备过,
: 其实估计他就是想问最简单的DHT原理,这个题面的设计,甚至于不expect你懂得DHT,

avatar
p*2
5
不知道你说简单程序出bug是什么样的bug?按道理说,简单程序确实应该bug free。这
方面可能还需要提高。
avatar
f*2
6
感谢lz分享,感觉设计题回答的还可以
avatar
w*x
7

和前面的面经有冲突啊, 前面的说允许有bug

【在 p*****2 的大作中提到】
: 不知道你说简单程序出bug是什么样的bug?按道理说,简单程序确实应该bug free。这
: 方面可能还需要提高。

avatar
p*2
8

运不允许是面试官决定的。

【在 w****x 的大作中提到】
:
: 和前面的面经有冲突啊, 前面的说允许有bug

avatar
r*g
9
我也觉得他们的设计题是有固定答案的。。。lz答的不错,但不是他们想要的。。。

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

avatar
b*o
10
说说我看到你答案的感想吧:
He: how would you design a distributed key-value store
Me: DHT or just using clusters
我不知道这一问一答是你简化过了还是实际就这么简单。如果实际就这么简单,
回答就很有问题。一般问一个设计题,是先要把问题的各种要求先和面试官讨
论清楚。你这么回答就好像考官问如果搜索速度太慢怎么办,你回答说用
cache一样(正确的回应是先讨论哪个环节慢了)。而对于这个问题我觉得首
先应该问清楚这个系统有多大,有多少Machine,有没有balance的要求,会
不会add或者delete整个machine,等等。
然后,即使在问清楚条件的情况下,也不要马上给一个specific的方案,而是
依旧泛泛地谈大致有几类思路。然后根据考官的反应,再说具体的技术细节。
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.
因为你之前没有问清楚考官到底想问你什么,所以我也不好评价你这个答案是
不是对。但是,如果要求相邻的key存在一个machine上(这是个很合理的要
求),第一层找machine就不能用hash实现的。 你这样的设计"king"和
“kingdom”所hash的值可能就完全不一样,可能会被存在两个完全不同的
machine上,尽管这两个字在排序上是很相似的。 当然你可以说考官没有这
么要求,但是因为你一个问题迅速进入技术细节,让考官没有机会说出这个要
求。如果考官就是要问如何根据key快速找machine,你把这个考点给跳过了~
He (seems not satisfied): how much space do you need on the master
machine?
我觉得他是在提醒你的答案有问题:你hash的值很可能和任何一个machine
都不吻合,而如果要求每个key所hash的值都对应一个存在的machine的话,
这其实就不是hash而是一个巨大的sstable了。你下面的回答倒是对的,只
是没有意识到hash的desgin存在的问题。
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
根据我前面的分析,你回答如何找machine这个问题可能完全出乎考官的意料。
可能他也懒得把题目条件说清楚(你不问他何必说),所以就直接进入到
centralized file system的问题。我想这时候他就是想问你具体的数据结
构了,比如B tree。但是你下面的回答还是在说你的两层hash的结构:(
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.
这个回答其实和你前面找machine的回答有同样的问题(你把考点给跳过了):
假设你根目录下有文件夹A,B,C,你要找的文件叫xxx,你如何知道是在哪个
文件夹呢?如果你想避免穷举(即搜索A,B,C以及他们下面所有的子目录)的
话,必须有某种数据结构让你快速的搜索。而这种数据结构就是考点呀~

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

avatar
a*q
11
谢谢大家的回复!因为确实没有太多的经验,很多知识也是零散存放在大脑里的,对于
面试官的提问如果没有想到所有的情况,是很难组织出有效提问的。另外因为是面试,
面试官对于这种问题都希望得到一个迅速的回答,如果一个简单问题自己没有马上作答
也是会减分的。
设计题我只是大概写了一下,中途有一些交流我省略了没有写,比如面试官对题目有所
阐释,我自己也问了一些相关问题,根据后面的结果来看不一定有多到位。我只写了触
发面试官问下一个问题的一些步骤。B tree神马的我也说了,但是面试官并没有move
forward,显然不是他想要的答案。DHT怎么work我也简单说了一下,但是他问再详细的
我确实不知道怎么说了,因为没有implement过。这个面试官整个过程只问了我这一道
题,花了很多时间,在他走的时候我明显感觉得到他没有其他面试官走时那么高兴。
关于简单题bug的问题,我有一个bug是把 == null写成 != null了,笔误。。另外一个
bug是一个边界条件写错了的问题,不过也是马上纠正了。这是同一个面试官的。另外
还有一个被指出的bug是DP题最后反着trace回来打印忘记写i = a[i]的那一步了,也是
马上找出来。其余的题就没有被指出来的bug了。我主要想说的是,会有那么一些面试
官,会要求你写上去的就不能更改了,不给你机会检查。。。
对于所有的面试,包括其他公司的,有不少面试官是很执着于他心目中的标准答案的,
他们会把你往那个答案上生拉硬拽,而不考虑你的思维。很少有面试官会真心explore
你到底知道什么。比如那道DP题,我写了一个s.substring(i+1, j+1),面试官问我为
什么不是i是i+1,我说其实两者皆可,但是都需要考虑一个特殊情况,所以其实是差不
多的,他想了一下才认可我的回答,所以我认为i是他预想的答案。我遇到的另外一个
跟binary tree next node很类似的问题,没有parent pointer,我想到用一个栈来存
放当前访问节点的所有祖先的方法,通过比较栈里的父子关系是左是右来决定怎么做,
面试官打断说你不用比较,需要我立即想出比我想的方法更优的方法才让我开始写程序
。后来我请求他让我先写再说,我写了一会儿就发现他那么说是什么意思了,最后也写
出了他认为的那个优化的解,这题不是google考的。另外还有一道不是google考的题也
遇到了类似情况,问如何随机生成一个n行的file,每行有很多bytes,需要行与行之间
有序。我答了一个方法,在我说的途中面试官就不停的说这有问题那有问题,最后他问
清楚了说这可能也work,不过还是一直皱着眉头,因为这不是他预想的标准答案。。。
因为很多面试官都这样,更加激励大家去k题背标准答案,因为靠自己想即使想对了但
是跟标准答案不一样,也很大概率同样杯具。。。

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

avatar
d*a
12
楼主可以读篇论文 Dynamo: Amazon's Highly Available Key-value Store
看下人家是怎么设计的。
avatar
w*y
13
你们都太牛了
我面的题很弱智, 我还都只做了一题。。。。。
我真心决定move on了
avatar
d*l
14
mark

【在 b*****o 的大作中提到】
: 说说我看到你答案的感想吧:
: He: how would you design a distributed key-value store
: Me: DHT or just using clusters
: 我不知道这一问一答是你简化过了还是实际就这么简单。如果实际就这么简单,
: 回答就很有问题。一般问一个设计题,是先要把问题的各种要求先和面试官讨
: 论清楚。你这么回答就好像考官问如果搜索速度太慢怎么办,你回答说用
: cache一样(正确的回应是先讨论哪个环节慢了)。而对于这个问题我觉得首
: 先应该问清楚这个系统有多大,有多少Machine,有没有balance的要求,会
: 不会add或者delete整个machine,等等。
: 然后,即使在问清楚条件的情况下,也不要马上给一个specific的方案,而是

avatar
h*n
15
我感觉你那个设计题答得没啥大问题啊,要是我面,肯定让你过了。。。
如果真是这道题卡你,只能说这个面试官太变态了。
cmft,move on吧,面试其实就是看运气,看谁面你了。

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

avatar
h*e
16
从你的帖子看,我觉得你基本功还不错,也应该挺聪明的,但是显然缺少经验,包括面
试的经验,对design问题的经验和对System方面的经验。所以有两点想提醒你一下,希
望对你有点帮助。
第一,关于面试。面试对于公司来说,就是面试官对你百般提问,最后对你做一个判断
的过程。所以不管他问的问题或者方式你喜不喜欢,你都要去适应。不要觉得没有按照
自己的意思讲完,或者被追究一些看似不重要的细节,好像很无聊。从面试官的角度去
理解,你就会明白他为什么这么做。
在45分钟内,他有明确的目的和期望,想了解你某些方面的知识或者能力。比如你很快
讲出一个关键的算法思想,那么他可能就觉得这个点上已经okay了,不用长篇大论。所
以就很可能打断你然后进行下一项,比如写code。
对于coding,有些简单的题目,没有很复杂的算法,考察的点之一可能就是看你是否能
把基本的逻辑写对,是不是一个detail-oriented的人,是不是自己可以发现自己的错
误,不需要别人的提醒或者提示,等等。你可能觉得不就是==NULL写成!=NULL了么,有
什么大不了,但是如果你面了100个人,发现90个都是这么错在这里,你就明白这个差
别了。另外,不要指望或者等待面试官明确告诉你,你要尽量写能编译通过的,优质无
错的code。这就好比去考试,你指望老师提醒你你要写正确答案一样。
至于为什么面试官要处处为难你,让你转到既定答案上,这也很好理解。面试不是要看
你答对了没有,而是看你和其他面试的人比较,谁更好。为了有可比性,就不可能让你
随心所欲,而是有参照的标准。另外,有时候面试官会故意问一些看似很无聊或者弱智
的问题,比如明明算法work,还是要问为什么work。很多时候,这是为了确定面试者充
分理解这个算法,另外也可以看出不同人的思维方式特点和insights。能够理解题目,
能够给出一个直观算法,能够改进一个直观算法,能够给出一个最优算法,能够给出一
个最优算法并证明最优性,这都是不同的层次,需要不同的insights。
甚至对于细节的在乎程度,对看似很简单的面试问题的态度(比如,有些有多年工作经
验的人看不起简单的coding question,觉得大材小用了,好像都要问设计题才行,但
是事实是大部分人都是眼高手低)都是面试官考察的范围。
第二,关于系统类设计题。
设计题很多人有一些误区,一个是以为就是随心所欲地设计,天马星空。另一个是以为
就是给出一个可行的设计方案。
我的理解是,设计题虽然很多是open-ended,相对算法和coding来说没有固定的答案,
但是考察的点也是很明确的。基本上就是三个点,对整个CS的知识了解的广度和理解的
深度, 专门领域知识和经验,运用CS基本知识和经验分析、解决问题的能力。其中我觉
得,最重要的是第三个(逻辑性,洞察力,应变能力,学习能力,分析能力,直觉,
etc.),其次是第一个(基本功,知识面,理解层次, etc.),第二个Domain
knowledge是最容易培养的,所以大部分地方都并不要求你非常有经验。这个最重要的
第三点,就是所谓的make sense.
比如,你的设计题的答案,前面也有一位朋友说了一些具体的问题,大部分我也比较同
意。你回答出B-tree, DHT之类的名词,并能解释是什么,怎么work,这说明你的基本
功和知识面不错,可能也做过或者学过system相关的方向。但是你的答案不够理想,因
为你的设计就在描述一个可行的方案,而不是一个充满了疑问的make sense的过程,这
是大部分人回答设计类题目的最根本问题。因为没有哪一个好的distributed keyVal
store是可以在不确定requirement的情况下,在没有对不同的design choices的分析对
比之下设计出来的。B-Tree, DHT等等,都是Technique,都有pros and cons,并不是
每个系统都要照搬的。System这个领域的精髓,不是用什么Technique让它work,而是
为什么做这样子的design choices和tradeoff最make sense。
所以窍门呢,也很简单,就是一个不断question的过程。多问问自己为什么这么设计,
多给面试官讲讲为什么这样子make sense.
最后是积累经验。这方面,没有经验的人最大的问题,不是给了一个问题不会提出解决
方案,而是不明白什么才是好和坏,什么才是真正的问题。一般情况下,这方面对
fresh grad也不会要求很高,基本上利用基本的CS知识,有些起码的sense或者
intuition,做到基本make sense就可以了。对工作过的人,一般期望就会高一些,尤
其是有相关经历的。所以没有经验的,要多看看别人都在尝试解决什么问题,这有时候
比怎么解决的更有用。
对于你的面试题来说,面试官一上来其实就是在等你问问题,问出一个requirement或
者scenario来。问的过程,就是考察你的experience的过程,明白这类系统关键问题所
在的人,就会问到点子上。后面就是看你讲的那些设计到底make sense不make sense的
过程。他会不断加或者改constraints,就是看你是不是能做出合理的方案。

【在 a**q 的大作中提到】
: 谢谢大家的回复!因为确实没有太多的经验,很多知识也是零散存放在大脑里的,对于
: 面试官的提问如果没有想到所有的情况,是很难组织出有效提问的。另外因为是面试,
: 面试官对于这种问题都希望得到一个迅速的回答,如果一个简单问题自己没有马上作答
: 也是会减分的。
: 设计题我只是大概写了一下,中途有一些交流我省略了没有写,比如面试官对题目有所
: 阐释,我自己也问了一些相关问题,根据后面的结果来看不一定有多到位。我只写了触
: 发面试官问下一个问题的一些步骤。B tree神马的我也说了,但是面试官并没有move
: forward,显然不是他想要的答案。DHT怎么work我也简单说了一下,但是他问再详细的
: 我确实不知道怎么说了,因为没有implement过。这个面试官整个过程只问了我这一道
: 题,花了很多时间,在他走的时候我明显感觉得到他没有其他面试官走时那么高兴。

avatar
f*n
17
我觉得lz答的挺好的啊。而且分析技术问题和心理问题都挺得体的。
lz现在定了去哪了了么?多发点经验和感想给大家参考下。

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

avatar
t*3
18
这种设计题好难啊,lz 加油
avatar
p*m
19
这个回答很中肯。这种设计题,一需要经验,二需要交流
这种开放式题目有很多东西可以分析讨论,所以从一开头就要跟面试官好好交流,
不然不知道他想要的key point,你回答的再多也没用,越到后面越觉得是鸡同鸭讲。

【在 b*****o 的大作中提到】
: 说说我看到你答案的感想吧:
: He: how would you design a distributed key-value store
: Me: DHT or just using clusters
: 我不知道这一问一答是你简化过了还是实际就这么简单。如果实际就这么简单,
: 回答就很有问题。一般问一个设计题,是先要把问题的各种要求先和面试官讨
: 论清楚。你这么回答就好像考官问如果搜索速度太慢怎么办,你回答说用
: cache一样(正确的回应是先讨论哪个环节慢了)。而对于这个问题我觉得首
: 先应该问清楚这个系统有多大,有多少Machine,有没有balance的要求,会
: 不会add或者delete整个machine,等等。
: 然后,即使在问清楚条件的情况下,也不要马上给一个specific的方案,而是

avatar
g*m
20
我觉得distributed system要考虑的挺多的吧,包括容错性、load balance什么的。你
如果每个key-value只存一个备份,应该是不行的。一般需要在3-5个机器上都存copy吧
。这里就有一个保持数据一致性的问题,如果只读还好,如果还有写(包括删除),
data flow也是考点,另外还需要保存每台机器存储空间的使用情况。还有就是load
balance,如果有很多query同时来,怎么能最快的读取。只从一台机器上读肯定就慢了。
另外像ls说的,key-value的格式是什么?如果key是GUID之类的没有任何额外限制,
hash table不是很现实吧。另外如果value没有任何大小限制,比如是文档,从一行到
一本康熙词典都叫一个value,那简单的hash table也不行啊,你得给分配多大的空间
?这样可能就得把所有value单独存,key-value里的value更新成地址之类的。
反正我觉得你的回答太简略了,很教科书,感觉不是特别实用:-)

【在 a**q 的大作中提到】
: 一共5个人,其中3.5个人考coding,数据结构和算法。1.5个人考设计。
: coding考了recursion, DP, 二叉树bfs,简单的hash一类的。因为写程序比较快,一共
: 答了7,8道coding题,难度不超过cracking the code,感觉基本答得还可以,难一点的
: 题bug还算少,而且跟面试官解释了一些边界情况为什么没有比这么写更简洁的方法,
: 除了最后一个面试官很变态。考了两个很简单无难度的code让写,顺序写完(不给时间
: 检查)以后叫不许动,拍照,然后说你的code有bug,虽然我很快给找出来了,但是给
: 拍照了。其实最后一个面试官的时候已经有点晕了,他早点说需要一次写对我就会写慢
: 些,可是他也没有说。。。
: 然后栽在一道large scale的设计题上。绝对不是所有的面试官都让你随意发挥,有的
: 人心里装了一个答案,问的很模糊,你不答到他那个答案他就是不满意。不知道如何解

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。