l****p
发帖数: 397 | 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。不过也有可能因为第一通电话实在
太差，直接给我拒了 |
h****n
发帖数: 1093 | 2 第二题不就是那个water container的问题么 O(n) 就行了
先找到最高点，然后分别从最左，从最右向最高点方向更新积水即可。 |
l*****a
发帖数: 559 | 3 打个岔，O(N*N)就是polynomial time，他应该想要linear time的解法。 |
g**u
发帖数: 583 | 4 为啥 “广度优先需要一个queue，这是O(N)的空间”, 任何时候 queue里面可以只存目
前level和下一个level的节点，目标节点就是BFS最后一个一个节点。
哪里理解错了吗？ |
K*********n
发帖数: 2852 | 5 当前level就是O(N)
【在 g**u 的大作中提到】
: 为啥 “广度优先需要一个queue，这是O(N)的空间”, 任何时候 queue里面可以只存目
: 前level和下一个level的节点，目标节点就是BFS最后一个一个节点。
: 哪里理解错了吗？
|
b*****u
发帖数: 648 | |
h****n
发帖数: 1093 | 7 不管是哪个题，都可以O（n） 贴下我的代码：
Container with most water：
class Solution {
public:
int maxArea(vector &height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int i = 0;
int j = height.size()-1;
int res = INT_MIN;
while(i
{
int minHeight = height[i]>=height[j]?height[j]:height[i];
int area = (j-i)*minHeight;
if(area >= res) res = area;
if(height[i]
else j--;
}
return res;
}
};
Trapping water：
class Solution {
public:
int trap(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int h=0,total=0,i;
if(n<=2) return 0;
//Find the highest bar
for(i=0;i
{
if(A[i]>A[h]) h = i;
}
int left = 0;
for(i=1;i
{
if(A[i]>=A[left])left = i;
else total += A[left]-A[i];
}
int right = n-1;
for(i=n-1;i>h;i--)
{
if(A[i]>=A[right])right = i;
else total += A[right]-A[i];
}
return total;
}
};
【在 b*****u 的大作中提到】
:
: 两码事，他说的应该是
: http://www.leetcode.com/groups/google-interview/forum/topic/rai
: 你说的是
: http://www.leetcode.com/groups/google-interview/forum/topic/con
|
d**e
发帖数: 6098 | 8 1 - 应该是O(1)空间吧，前缀递归遍历
【在 l****p 的大作中提到】
: 第一通电话：
: 听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
: 上来没寒暄几句就写代码：
: 找出一个树中最深的结点。
: 明显留了好多细节让我问，于是我开始clarify:
: 1. 是不是binary tree。答：good question, yes, assume it's a binary tree
: 2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
: 然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
: 问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
: 然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
|
h****n
发帖数: 1093 | 9 第一题，随手写了DFS和BFS，请指教
TreeNode* GetDeepestNode(TreeNode* root)
{
TreeNode* res=NULL;
int curLevel=1,preLevel=0;
DFSHelper(root, res, curLevel, preLevel);
//BFSHelper(root, res);
return res;
}
//Time O(n) space 不算递归栈则O（1） 算的话 O(lgn)
void DFSHelper(TreeNode* root, TreeNode* &res, int & curLevel, int &
preLevel)
{
if(root)
{
if(curLevel>preLevel)
{
res = root;
preLevel++;
}
curLevel++;
DFSHelper(root->right, res, curLevel, preLevel);
DFSHelper(root->left, res, curLevel, preLevel);
curLevel--;
}
}
//Time O(n) space O(n)
void BFSHelper(TreeNode* root, TreeNode* &res)
{
int curLevelNum,nextLevelNum;
queue q;
TreeNode* tmp;
if(!root) return;
q.push(root);
curLevelNum = 1;
nextLevelNum = 0;
while(!q.empty())
{
tmp = q.front();
q.pop();
curLevelNum--;
if(tmp->left)
{
q.push(tmp->left);
nextLevelNum++;
}
if(tmp->right)
{
q.push(tmp->right);
nextLevelNum++;
}
if(!curLevelNum)
{
if(nextLevelNum)
{
curLevelNum=nextLevelNum;
nextLevelNum=0;
}
else
{
res = tmp;
}
}
}
}
【在 l****p 的大作中提到】
: 第一通电话：
: 听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
: 上来没寒暄几句就写代码：
: 找出一个树中最深的结点。
: 明显留了好多细节让我问，于是我开始clarify:
: 1. 是不是binary tree。答：good question, yes, assume it's a binary tree
: 2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
: 然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
: 问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
: 然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
|
d*********g
发帖数: 154 | |
|
|
e******o
发帖数: 757 | 11 哪位能不用递归写一下DFS么？
【在 h****n 的大作中提到】
: 第一题，随手写了DFS和BFS，请指教
: TreeNode* GetDeepestNode(TreeNode* root)
: {
: TreeNode* res=NULL;
: int curLevel=1,preLevel=0;
: DFSHelper(root, res, curLevel, preLevel);
: //BFSHelper(root, res);
: return res;
: }
: //Time O(n) space 不算递归栈则O（1） 算的话 O(lgn)
|
h****n
发帖数: 1093 | 12 用个stack即可不过不太好记录depth
哪位能不用递归写一下DFS么？
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 e******o 的大作中提到】
: 哪位能不用递归写一下DFS么？
|
p*****2
发帖数: 21240 | 13 两道题都没答好。可见做leetcode是多么的重要了。 |
p*****2
发帖数: 21240 | 14
stack有size吧。
【在 h****n 的大作中提到】
: 用个stack即可不过不太好记录depth
:
: 哪位能不用递归写一下DFS么？
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
h*u
发帖数: 122 | |
h****n
发帖数: 1093 | 16 leetcode的题做过一遍了，最近想做点新题更新太慢了
【在 p*****2 的大作中提到】
: 两道题都没答好。可见做leetcode是多么的重要了。
|
p*****2
发帖数: 21240 | 17
做做其他OJ？
【在 h****n 的大作中提到】
: leetcode的题做过一遍了，最近想做点新题更新太慢了
|
h****n
发帖数: 1093 | 18 topcoder?
貌似很难啊。。。
【在 p*****2 的大作中提到】
:
: 做做其他OJ？
|
h********g
发帖数: 496 | |
s**********z
发帖数: 61 | 20 如果树是unbalanced，一条线，为什么DFS 空间是lgn?
【在 h****n 的大作中提到】
: 第一题，随手写了DFS和BFS，请指教
: TreeNode* GetDeepestNode(TreeNode* root)
: {
: TreeNode* res=NULL;
: int curLevel=1,preLevel=0;
: DFSHelper(root, res, curLevel, preLevel);
: //BFSHelper(root, res);
: return res;
: }
: //Time O(n) space 不算递归栈则O（1） 算的话 O(lgn)
|
|
|
l*******b
发帖数: 2586 | 21 递归本身就不是O(1)空间吧?
如果一个节点可以找到parent 并确定自己在左边还是右边。就不用记录任何信息了
【在 d**e 的大作中提到】
: 1 - 应该是O(1)空间吧，前缀递归遍历
|
l****p
发帖数: 397 | 22 确实是，本来第二道还答得沾沾自喜，一看版上的代码才知道原来还有差距。唉，不抱
希望了，再练一年，明年继续
【在 p*****2 的大作中提到】
: 两道题都没答好。可见做leetcode是多么的重要了。
|
l****p
发帖数: 397 | 23 嗯，没错，这是worst case。面试官问我balanced和unbalanced有什么影响时我居然答
不上来，又一个失分点啊
【在 s**********z 的大作中提到】
: 如果树是unbalanced，一条线，为什么DFS 空间是lgn?
|
h****n
发帖数: 1093 | 24 恩 疏忽了
如果树是unbalanced，一条线，为什么DFS 空间是lgn?
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 s**********z 的大作中提到】
: 如果树是unbalanced，一条线，为什么DFS 空间是lgn?
|
h****n
发帖数: 1093 | 25 size和depth的关系是什么的？想不出来二爷指教
stack有size吧。
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 p*****2 的大作中提到】
:
: 做做其他OJ？
|
c****7
发帖数: 13 | 26 写了个第一题的DFS的非递归解法， 请高手多指教
public static TreeNode findDeepestNode(TreeNode root){
if(root ==null) return root;
int maxDepth = 1;
TreeNode deepestNode = root;
// The previous node we just traversed
TreeNode preNode=null;
// The top item in the stack
TreeNode curNode;
Stack nodeStack = new Stack();
nodeStack.push(root);
// exit until the stack is empty
while(!nodeStack.isEmpty()){
// check the top item of the stack
curNode = nodeStack.peek();
// if it is traversing from parent
// to either leftChild or rightChild
if(preNode==null || preNode.left == curNode || preNode.right ==
curNode){
// if the curNode has leftChild
if(curNode.left!=null){
// push the leftChild to stack
nodeStack.push(curNode.left);
// every time when you push a node, check
// to see if the newly pushed node is
// the deepest node
if (nodeStack.size()>=maxDepth){
// update the variables
maxDepth = nodeStack.size();
deepestNode = curNode.left;
}
}
else if(curNode.right!=null){
nodeStack.push(curNode.right);
// every time when you push a node, do the check
if (nodeStack.size()>=maxDepth){
maxDepth = nodeStack.size();
deepestNode = curNode.right;
}
}else // if the curNode is a leaf, pop it from the stack
nodeStack.pop();
}else if(preNode==curNode.left){
// if the leftChild of the curNode
// has just been traversed, then move to rightChild
if(curNode.right!=null){
// push the rightChild to stack
nodeStack.push(curNode.right);
// check to see if the newly pushed
// node is the deepest node
if (nodeStack.size()>=maxDepth){
maxDepth = nodeStack.size();
deepestNode = curNode.right;
}
}
}else //(preNode==curNode.right){
// if both leftChild and rightChild
// have been visited
nodeStack.pop();
// update the preNode
preNode = curNode;
}
return deepestNode;
} |
r****c
发帖数: 2585 | 27 intern过了以后也要看运气，有没有组要你
有些组直接找合作教授的学生
【在 l****p 的大作中提到】
: 第一通电话：
: 听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
: 上来没寒暄几句就写代码：
: 找出一个树中最深的结点。
: 明显留了好多细节让我问，于是我开始clarify:
: 1. 是不是binary tree。答：good question, yes, assume it's a binary tree
: 2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
: 然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
: 问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
: 然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
|
l****p
发帖数: 397 | 28 Host matching失败是直接拒了还是等下一个quarter再match?
【在 r****c 的大作中提到】
: intern过了以后也要看运气，有没有组要你
: 有些组直接找合作教授的学生
|
b***u
发帖数: 61 | 29 如果你用iterative的post order，每push一个tree node，stack的size对应就是当前
tree node的depth
【在 h****n 的大作中提到】
: size和depth的关系是什么的？想不出来二爷指教
:
: stack有size吧。
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
l****p
发帖数: 397 | 30 今天接到通知，我通过了这轮的面试，尽管有上述诸多失分点。看来Google的第一轮面
试果然很随机 |
