f*******7
发帖数: 943 | 1 自去年9月来，拖拖拉拉，今天才面上第三面。
估计终场前是1:1，这回是加时赛。
这回这哥们上来就扔题，没扯蛋，还好题是最近突击做过的，如果没做过当场那么短时
间肯定是想不出来。
1. 合并两个已排好序的数组
2. 判断一个树是不是搜索二叉树（BST）
3. 继续判断这个二叉树是不是平衡树
4. 优化3.
不知道communication会不会让我挂，他说啥我实在听不清，我说啥他也听不清， 有时
还有十多秒对面也没反应，估计是那哥们拿免提，而且还离的不太近。。。
新的一年祝大家找工作都顺利吧！ |
j*****y
发帖数: 1071 | 2 2. 是让判断是不是 搜索二叉树吧？
【在 f*******7 的大作中提到】
: 自去年9月来，拖拖拉拉，今天才面上第三面。
: 估计终场前是1:1，这回是加时赛。
: 这回这哥们上来就扔题，没扯蛋，还好题是最近突击做过的，如果没做过当场那么短时
: 间肯定是想不出来。
: 1. 合并两个已排好序的数组
: 2. 判断一个树是不是搜索二叉树（BST）
: 3. 继续判断这个二叉树是不是平衡树
: 4. 优化3.
: 不知道communication会不会让我挂，他说啥我实在听不清，我说啥他也听不清， 有时
: 还有十多秒对面也没反应，估计是那哥们拿免提，而且还离的不太近。。。
|
e****e
发帖数: 418 | |
f*******7
发帖数: 943 | 4 啊 sorry 对， 我得改过来。。。
【在 j*****y 的大作中提到】
: 2. 是让判断是不是 搜索二叉树吧？
|
l*****a
发帖数: 14598 | 5 第一题要求结果怎么放？
【在 f*******7 的大作中提到】
: 自去年9月来，拖拖拉拉，今天才面上第三面。
: 估计终场前是1:1，这回是加时赛。
: 这回这哥们上来就扔题，没扯蛋，还好题是最近突击做过的，如果没做过当场那么短时
: 间肯定是想不出来。
: 1. 合并两个已排好序的数组
: 2. 判断一个树是不是搜索二叉树（BST）
: 3. 继续判断这个二叉树是不是平衡树
: 4. 优化3.
: 不知道communication会不会让我挂，他说啥我实在听不清，我说啥他也听不清， 有时
: 还有十多秒对面也没反应，估计是那哥们拿免提，而且还离的不太近。。。
|
f*******7
发帖数: 943 | 6 他没说，我就老老实实弄个第三个数组放结果
【在 l*****a 的大作中提到】
: 第一题要求结果怎么放？
|
s***y
发帖数: 203 | |
f*******7
发帖数: 943 | 8 谢谢大牛，祝你早日拿offer
【在 s***y 的大作中提到】
: Bless，给个onsite
|
C******n
发帖数: 284 | |
a******e
发帖数: 5411 | 10 lz您真实高才生啊。我连题目都看部懂
好难啊。。。
我保证现在里面的民工有人不会做这些题目。
门槛就是高啊。 |
|
|
f*******7
发帖数: 943 | 11 之前我其实也看不懂，但是为了面试就得做题，还得做题。。。尽管平时工作用不上
有一次面试因为有道题写的稍微有点bug，结果人家反馈是 【木有编程经验】
从此以后我为了积累所谓的 【编程经验】， 于是我开始做题了
【在 a******e 的大作中提到】
: lz您真实高才生啊。我连题目都看部懂
: 好难啊。。。
: 我保证现在里面的民工有人不会做这些题目。
: 门槛就是高啊。
|
G****A
发帖数: 4160 | 12 :) 要厚道
【在 a******e 的大作中提到】
: lz您真实高才生啊。我连题目都看部懂
: 好难啊。。。
: 我保证现在里面的民工有人不会做这些题目。
: 门槛就是高啊。
|
d*********g
发帖数: 154 | |
s*****2
发帖数: 68 | |
f*******7
发帖数: 943 | 15 我一开始写的是 o(n2), 后来他要求我写o(n) 。。。
【在 d*********g 的大作中提到】
: 最后的优化有什么要求？
|
l**b
发帖数: 457 | 16 都是老题目了，第3个除了用个Map来cache一下depth，其他还能怎么优化？ |
f*******7
发帖数: 943 | 17 让大牛见笑了，这些题都给我折腾够呛，再稍微难一点，我就写不出来了。
因为平衡树那个我写的是o(n2), 所以他让我优化。。。
【在 l**b 的大作中提到】
: 都是老题目了，第3个除了用个Map来cache一下depth，其他还能怎么优化？
|
P*******b
发帖数: 1001 | 18 这个题怎么做？可以用递归吗？
【在 f*******7 的大作中提到】
: 让大牛见笑了，这些题都给我折腾够呛，再稍微难一点，我就写不出来了。
: 因为平衡树那个我写的是o(n2), 所以他让我优化。。。
|
f*******7
发帖数: 943 | 19 我只会递归写，往左右子树递归
不知道遍历写法怎么写，哪个大牛帮写个吧
【在 P*******b 的大作中提到】
: 这个题怎么做？可以用递归吗？
|
w********p
发帖数: 948 | 20 3. 继续判断这个二叉树是不是平衡树
A balanced binary tree is commonly defined as a binary tree in which the
depth of the two subtrees of every node differ by 1 or less,[3] although in
general it is a binary tree where no leaf is much farther away from the root
than any other leaf. (Different balancing schemes allow different
definitions of "much farther".[4]) Binary trees that are balanced according
to this definition have a predictable depth (how many nodes are traversed
from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ...
, depth).
http://en.wikipedia.org/wiki/Binary_tree
用递归算每个节点的从左边和从右边的depth, 如果有差度大于一，就不是balanced.
当前节点的depth ＝ max (depth of left child+1, depth of right child+ 1).
每个节点走一遍，所以是O(n) |
|
|
w********p
发帖数: 948 | 21 sudocode from online
IsHeightBalanced(tree, height)
if (tree is empty)
height = 0
return true
balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(
tree.right, heightright)
height = max(heightleft, heightright)+1
return balance and abs(heightleft - heightright) <= 1
More discussion here
http://stackoverflow.com/questions/742844/how-to-determine-if-b |
B**L
发帖数: 33 | 22 你的方法不是O（n）吧？
in
root
according
..
【在 w********p 的大作中提到】
: 3. 继续判断这个二叉树是不是平衡树
: A balanced binary tree is commonly defined as a binary tree in which the
: depth of the two subtrees of every node differ by 1 or less,[3] although in
: general it is a binary tree where no leaf is much farther away from the root
: than any other leaf. (Different balancing schemes allow different
: definitions of "much farther".[4]) Binary trees that are balanced according
: to this definition have a predictable depth (how many nodes are traversed
: from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ...
: , depth).
: http://en.wikipedia.org/wiki/Binary_tree
|
j*****y
发帖数: 1071 | 23 对的，这个是 O(n)
in
root
according
..
【在 w********p 的大作中提到】
: 3. 继续判断这个二叉树是不是平衡树
: A balanced binary tree is commonly defined as a binary tree in which the
: depth of the two subtrees of every node differ by 1 or less,[3] although in
: general it is a binary tree where no leaf is much farther away from the root
: than any other leaf. (Different balancing schemes allow different
: definitions of "much farther".[4]) Binary trees that are balanced according
: to this definition have a predictable depth (how many nodes are traversed
: from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ...
: , depth).
: http://en.wikipedia.org/wiki/Binary_tree
|
w********p
发帖数: 948 | 24 这个题目和隔壁M家on-site比实在是靠谱多了。
bless
【在 f*******7 的大作中提到】
: 自去年9月来，拖拖拉拉，今天才面上第三面。
: 估计终场前是1:1，这回是加时赛。
: 这回这哥们上来就扔题，没扯蛋，还好题是最近突击做过的，如果没做过当场那么短时
: 间肯定是想不出来。
: 1. 合并两个已排好序的数组
: 2. 判断一个树是不是搜索二叉树（BST）
: 3. 继续判断这个二叉树是不是平衡树
: 4. 优化3.
: 不知道communication会不会让我挂，他说啥我实在听不清，我说啥他也听不清， 有时
: 还有十多秒对面也没反应，估计是那哥们拿免提，而且还离的不太近。。。
|
w*****c
发帖数: 7276 | |
z*******a
发帖数: 858 | 26 那个tree balance的优化问题， 记得O(n)算法是recursive，return值是height，但如
果自己的左右tree是不balance的话，直接return -1，然后顶上就不用算了，全自动优
先return -1,所以就很简单。 |
G****A
发帖数: 4160 | 27 3. 判断这个二叉树是不是平衡树
recursive, top-down, O(n^2)
4. 优化3.
recursive, bottom-Up, O(n)
【在 l**b 的大作中提到】
: 都是老题目了，第3个除了用个Map来cache一下depth，其他还能怎么优化？
|
i********m
发帖数: 332 | 28 public static int height(Node root) {
if (root == null)
return 0;
return Math.max (height(root.left),height(root.right)) + 1;
}
public static boolean isBalance (Node root) {
if (root == null)
return true;
return Math.abs(height(root.left) - height(root.right)) > 1 ? false :
true && isBalance(root.left) && isBalance(root.right);
}
这个是O(n)么？
【在 f*******7 的大作中提到】
: 我一开始写的是 o(n2), 后来他要求我写o(n) 。。。
|
a***o
发帖数: 1182 | 29 no...
【在 i********m 的大作中提到】
: public static int height(Node root) {
: if (root == null)
: return 0;
: return Math.max (height(root.left),height(root.right)) + 1;
: }
:
: public static boolean isBalance (Node root) {
: if (root == null)
: return true;
: return Math.abs(height(root.left) - height(root.right)) > 1 ? false :
|
d*********g
发帖数: 154 | 30 第三题贴个刚写的java代码：
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return helper(root) != -1;
}
private int helper(TreeNode root)
{
if(root == null) return 0;
int leftHeight = helper(root.left);
int rightHeight = helper(root.right);
if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight -
rightHeight) <= 1)
return Math.max(leftHeight, rightHeight)+1;
return -1;
} |
|
|
T*********s
发帖数: 17839 | |
y********9
发帖数: 1417 | |
f*******7
发帖数: 943 | 33 这个靠谱 O(n)
【在 d*********g 的大作中提到】
: 第三题贴个刚写的java代码：
: public boolean isBalanced(TreeNode root) {
: if(root == null) return true;
: return helper(root) != -1;
: }
: private int helper(TreeNode root)
: {
: if(root == null) return 0;
:
: int leftHeight = helper(root.left);
|
