G****A
发帖数: 4160 | 1 都是大家熟悉的题
Q1, nth Fibonacci number. 要求尽可能多的解法。
follow-up, 每种解法的time/space complexity (要求function call的stack
overhead也看做space complexity).
Q2: c++基本概念。static, reference vs pointer, what is OOD, ...
Q3：列举并比较你常用的几种design patterns的作用和特点。
Q4: tree traversal, 要求level by level,按从底向上的顺序。同个level从左到右。
当我说要用DFS实现print by level的时候，此senior engineer先说“How could you
possibly print in level-order using DFS?”
解释完之后，senior engineer说：“ In the worst case, this will have
quadratic run time (if the tree is unbalanced). I was wondering about your
motivation to use DFS instead. It is quite a counter-intuitive
implementation.”
感觉是要被黑的套路，也就不想说什么了。尽管我记得以前推过：用DFS print in
level-order, average case 也是O(n).
update: 一点教训，尽量顺着面试官的思路说。这个小印senior在他认为“impossible
”的方法被证明“possible”之后态度明显有变化，变得很不nice。搞得我都开始犹
豫纠正不纠正他complexity分析的错误了。 |
F******F
发帖数: 63 | 2 Q4 用 dfs 是常见套路吧。此sr是啥意思？
you
【在 G****A 的大作中提到】
: 都是大家熟悉的题
: Q1, nth Fibonacci number. 要求尽可能多的解法。
: follow-up, 每种解法的time/space complexity (要求function call的stack
: overhead也看做space complexity).
: Q2: c++基本概念。static, reference vs pointer, what is OOD, ...
: Q3：列举并比较你常用的几种design patterns的作用和特点。
: Q4: tree traversal, 要求level by level,按从底向上的顺序。同个level从左到右。
: 当我说要用DFS实现print by level的时候，此senior engineer先说“How could you
: possibly print in level-order using DFS?”
: 解释完之后，senior engineer说：“ In the worst case, this will have
|
d**********x
发帖数: 4083 | 3 确实有点反直觉。。
you
【在 G****A 的大作中提到】
: 都是大家熟悉的题
: Q1, nth Fibonacci number. 要求尽可能多的解法。
: follow-up, 每种解法的time/space complexity (要求function call的stack
: overhead也看做space complexity).
: Q2: c++基本概念。static, reference vs pointer, what is OOD, ...
: Q3：列举并比较你常用的几种design patterns的作用和特点。
: Q4: tree traversal, 要求level by level,按从底向上的顺序。同个level从左到右。
: 当我说要用DFS实现print by level的时候，此senior engineer先说“How could you
: possibly print in level-order using DFS?”
: 解释完之后，senior engineer说：“ In the worst case, this will have
|
d**********x
发帖数: 4083 | 4 level order按直觉不应该是bfs吗。。
【在 F******F 的大作中提到】
: Q4 用 dfs 是常见套路吧。此sr是啥意思？
:
: you
|
l*****a
发帖数: 14598 | 5 什么厂？
you
【在 G****A 的大作中提到】
: 都是大家熟悉的题
: Q1, nth Fibonacci number. 要求尽可能多的解法。
: follow-up, 每种解法的time/space complexity (要求function call的stack
: overhead也看做space complexity).
: Q2: c++基本概念。static, reference vs pointer, what is OOD, ...
: Q3：列举并比较你常用的几种design patterns的作用和特点。
: Q4: tree traversal, 要求level by level,按从底向上的顺序。同个level从左到右。
: 当我说要用DFS实现print by level的时候，此senior engineer先说“How could you
: possibly print in level-order using DFS?”
: 解释完之后，senior engineer说：“ In the worst case, this will have
|
G****A
发帖数: 4160 | 6 嘿嘿。看来我2了。
主要感觉BFS要用一个额外的queue，而且从bottom level向上的方向对BFS来说不合适。
【在 d**********x 的大作中提到】
: 确实有点反直觉。。
:
: you
|
G****A
发帖数: 4160 | 7 东北的M
【在 l*****a 的大作中提到】
: 什么厂？
:
: you
|
l*********y
发帖数: 1431 | 8 还是用bfs，把结果放在stack里，然后再取出来不就是从底向上么？
他们有没有限制memory overhead? |
c********t
发帖数: 5706 | 9 用DFS实现print by level，我只会先求depth, 然后传level = depth to 1,到dfs函数
来打印。那样肯定不能做到O(n) 应该是 O(n*depth) worst case O(n^2) 也没那个
engineer说的那么离谱吧。你说的O(n)怎么做？
you
【在 G****A 的大作中提到】
: 都是大家熟悉的题
: Q1, nth Fibonacci number. 要求尽可能多的解法。
: follow-up, 每种解法的time/space complexity (要求function call的stack
: overhead也看做space complexity).
: Q2: c++基本概念。static, reference vs pointer, what is OOD, ...
: Q3：列举并比较你常用的几种design patterns的作用和特点。
: Q4: tree traversal, 要求level by level,按从底向上的顺序。同个level从左到右。
: 当我说要用DFS实现print by level的时候，此senior engineer先说“How could you
: possibly print in level-order using DFS?”
: 解释完之后，senior engineer说：“ In the worst case, this will have
|
r**h
发帖数: 1288 | 10 如果二叉树是平衡的话
复杂度应该是1+2+4+8+...+N ~= O(2*N) = O(N)
【在 c********t 的大作中提到】
: 用DFS实现print by level，我只会先求depth, 然后传level = depth to 1,到dfs函数
: 来打印。那样肯定不能做到O(n) 应该是 O(n*depth) worst case O(n^2) 也没那个
: engineer说的那么离谱吧。你说的O(n)怎么做？
:
: you
|
|
|
G****A
发帖数: 4160 | 11 http://leetcode.com/2010/09/binary-tree-level-order-traversal-u
【在 c********t 的大作中提到】
: 用DFS实现print by level，我只会先求depth, 然后传level = depth to 1,到dfs函数
: 来打印。那样肯定不能做到O(n) 应该是 O(n*depth) worst case O(n^2) 也没那个
: engineer说的那么离谱吧。你说的O(n)怎么做？
:
: you
|
l*****a
发帖数: 14598 | 12 想了一下，对层而言，确实可以用DFS.
print bt level by level的一个做法就是用dummy node,每次用前一次的结果
求这次的。。。
TreeNode dummy=new TreeNode();
dummy.next=root;
func(dummy.next);
public void func(TreeNode list){
//generate list of next level;
func(nextlist);
//print list of current level;
}
这个甚至是O(1)space 吧(不考虑callstack)
【在 c********t 的大作中提到】
: 用DFS实现print by level，我只会先求depth, 然后传level = depth to 1,到dfs函数
: 来打印。那样肯定不能做到O(n) 应该是 O(n*depth) worst case O(n^2) 也没那个
: engineer说的那么离谱吧。你说的O(n)怎么做？
:
: you
|
l*****a
发帖数: 14598 | 13 博士屯？
【在 G****A 的大作中提到】
: 东北的M
|
G****A
发帖数: 4160 | 14 positive
【在 l*****a 的大作中提到】
: 博士屯？
|
l*****a
发帖数: 14598 | 15
这个要求logn的解法了吗
you
【在 G****A 的大作中提到】
: 都是大家熟悉的题
: Q1, nth Fibonacci number. 要求尽可能多的解法。
: follow-up, 每种解法的time/space complexity (要求function call的stack
: overhead也看做space complexity).
: Q2: c++基本概念。static, reference vs pointer, what is OOD, ...
: Q3：列举并比较你常用的几种design patterns的作用和特点。
: Q4: tree traversal, 要求level by level,按从底向上的顺序。同个level从左到右。
: 当我说要用DFS实现print by level的时候，此senior engineer先说“How could you
: possibly print in level-order using DFS?”
: 解释完之后，senior engineer说：“ In the worst case, this will have
|
r**h
发帖数: 1288 | 16 log n是直接拿通项公式算的那个方法？
【在 l*****a 的大作中提到】
:
: 这个要求logn的解法了吗
: you
|
d**********x
发帖数: 4083 | 17 或者矩阵
【在 r**h 的大作中提到】
: log n是直接拿通项公式算的那个方法？
|
l*****a
发帖数: 14598 | 18 其实我认为问logn的就没什么意思了，就有点偏离CS了
【在 d**********x 的大作中提到】
: 或者矩阵
|
d**********x
发帖数: 4083 | 19 用通项还好吧
【在 l*****a 的大作中提到】
: 其实我认为问logn的就没什么意思了，就有点偏离CS了
|
l*******t
发帖数: 100 | 20 哦， 原来是马特拉伯啊
【在 l*****a 的大作中提到】
: 博士屯？
|
|
|
c********t
发帖数: 5706 | 21 你这个难道不是bfs?
//generate list of next level; 要占空间的，就是push into queue啊
【在 l*****a 的大作中提到】
: 想了一下，对层而言，确实可以用DFS.
: print bt level by level的一个做法就是用dummy node,每次用前一次的结果
: 求这次的。。。
: TreeNode dummy=new TreeNode();
: dummy.next=root;
: func(dummy.next);
: public void func(TreeNode list){
: //generate list of next level;
: func(nextlist);
: //print list of current level;
|
l*****a
发帖数: 14598 | 22 不是啊，就是把pointer/refernce连在dummy后面
【在 c********t 的大作中提到】
: 你这个难道不是bfs?
: //generate list of next level; 要占空间的，就是push into queue啊
|
c********t
发帖数: 5706 | 23 嗯,多谢。
the best situation is balanced tree, O(n) 2N
the worst is unbalanced list like tree, O(n^2)
最鄙视那个senior，这种张嘴就拍，自以为是的人了。
【在 G****A 的大作中提到】
: http://leetcode.com/2010/09/binary-tree-level-order-traversal-u
|
c********t
发帖数: 5706 | 24 那我感觉会有问题啊，写一个试试吧。
【在 l*****a 的大作中提到】
: 不是啊，就是把pointer/refernce连在dummy后面
|
f********4
发帖数: 988 | 25 binary tree 那个。。
从下面来是不是可以把从上面来那个的result倒过来。。
我是指那个final result
这样答会被扁嘛。。 |
j********x
发帖数: 2330 | 26 dfs实现level order这种典型的奇巧淫技就不要说是啥常见套路了吧
【在 F******F 的大作中提到】
: Q4 用 dfs 是常见套路吧。此sr是啥意思？
:
: you
|
