土耳其和中国审美相似 (转载)# Fashion - 美丽时尚
l*p
1 楼
第一通电话：
听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
上来没寒暄几句就写代码：
找出一个树中最深的结点。
明显留了好多细节让我问，于是我开始clarify:
1. 是不是binary tree。答：good question, yes, assume it's a binary tree
2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
然后找出最深的。他问复杂度，我说时间是O(N), 空间是O(N). 他说空间能优化吗？我
说能， 在遍历过程中只记录最深的就行。他问这下的空间复杂度，我说是O(1) 。然后
让我开始写代码，我说深度优先呢还是广度优先，他说有什么区别，我说差不多，然后
想想不对，广度优先需要一个queue，这是O(N)的空间，深度的只要O(lgN)的空间，这
才想起刚才说O(1)的空间是错的，又一个失分点。
接着开始写代码，居然花了好长时间，还犯了两个严重错误：
1. 返回的并不是最右的，而是最左的最深结点
2. 找到一个最深结点后没有记录当前的深度
一边说话一边写代码的能力还是不行啊，这种问题要是让我不说话一个人做，估计10分
钟就能搞定。这次居然花了40分钟，然后面试就结束了。
一点教训：应该把requirement记下来，写代码后对着查
我觉得这个老印肯定给我一个差评的
第二通电话：
谢天谢地， 是个老美的口音
先是对着简历问我的一篇论文，接着还是写代码：
结出一个数组，代表一个小岛的横切面，每个数字代码高度，求这个岛中的湖能积多少水
先是想着按数组的顺序一个个检查高度，找出各个湖的位置。想了会，没想出比较好的
解法。于是换成另一种思路，一层层地检查，从0到小岛的最高点，记录每层能容的水
量。这下就迅速把代码写出来了。然后问复杂度，我说是O(maxHeight*N*N)，如果
maxHeight是个相对小的数，那么就是O(N*N)。他说不错，是polynomial time，然后自
己说这个问题没法优化到O(N)，他以前试过。
接着问我以前做过的项目，最喜欢哪个项目，为什么，然后就结束了。
这次电话应该是个positive的评价，如果是这样的话，一次negative，一次positive，
我估计他们会再给我一次tie breaking interview。不过也有可能因为第一通电话实在
太差，直接给我拒了
听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
上来没寒暄几句就写代码：
找出一个树中最深的结点。
明显留了好多细节让我问，于是我开始clarify:
1. 是不是binary tree。答：good question, yes, assume it's a binary tree
2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
然后找出最深的。他问复杂度，我说时间是O(N), 空间是O(N). 他说空间能优化吗？我
说能， 在遍历过程中只记录最深的就行。他问这下的空间复杂度，我说是O(1) 。然后
让我开始写代码，我说深度优先呢还是广度优先，他说有什么区别，我说差不多，然后
想想不对，广度优先需要一个queue，这是O(N)的空间，深度的只要O(lgN)的空间，这
才想起刚才说O(1)的空间是错的，又一个失分点。
接着开始写代码，居然花了好长时间，还犯了两个严重错误：
1. 返回的并不是最右的，而是最左的最深结点
2. 找到一个最深结点后没有记录当前的深度
一边说话一边写代码的能力还是不行啊，这种问题要是让我不说话一个人做，估计10分
钟就能搞定。这次居然花了40分钟，然后面试就结束了。
一点教训：应该把requirement记下来，写代码后对着查
我觉得这个老印肯定给我一个差评的
第二通电话：
谢天谢地， 是个老美的口音
先是对着简历问我的一篇论文，接着还是写代码：
结出一个数组，代表一个小岛的横切面，每个数字代码高度，求这个岛中的湖能积多少水
先是想着按数组的顺序一个个检查高度，找出各个湖的位置。想了会，没想出比较好的
解法。于是换成另一种思路，一层层地检查，从0到小岛的最高点，记录每层能容的水
量。这下就迅速把代码写出来了。然后问复杂度，我说是O(maxHeight*N*N)，如果
maxHeight是个相对小的数，那么就是O(N*N)。他说不错，是polynomial time，然后自
己说这个问题没法优化到O(N)，他以前试过。
接着问我以前做过的项目，最喜欢哪个项目，为什么，然后就结束了。
这次电话应该是个positive的评价，如果是这样的话，一次negative，一次positive，
我估计他们会再给我一次tie breaking interview。不过也有可能因为第一通电话实在
太差，直接给我拒了
