s********s
发帖数: 49 | 1 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
后开始做题，让merge k 个 sorted list，用heap做了。
第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
。顺便请教一下大家两个困扰我挺久的问题：
(1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
因为我想明年一毕业就能直接去美国工作，这样的话势必要在明年三四月的时候找好
full time了吧，不然的话h1b神马的是不是会有问题？我这样的情况怎么样规划好一点
？求建议啊！
(2) 像这次面我的两个人在出题之前都说了句，要是题目我碰到过的话就和他们说，他
们可以换一个题目。那是不是每次碰到做过的题目，是不是实际中都是都要老实交代呢
，还是可以慢慢讲思路？ |
p*****2
发帖数: 21240 | 2 longest path前不久讨论过。没见过不太容易写好。
UW or UT? 其实题目见过能写好也不容易。 |
s********s
发帖数: 49 | 3
longest path我到时也去搜过，但是好多solution,有的也没看懂，大神给点思路？
【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
|
l**b
发帖数: 457 | 4 longest path怎么定义的啊？tree里面任何2个node之间的距离？ |
s********s
发帖数: 49 | 5
恩，对的，就是这个意思。
【在 l**b 的大作中提到】
: longest path怎么定义的啊？tree里面任何2个node之间的距离？
|
p*****2
发帖数: 21240 | 6
你这个path是可以任意点开始，任意点结束吧？
【在 s********s 的大作中提到】
:
: 恩，对的，就是这个意思。
|
s********s
发帖数: 49 | 7
嗯，其实就是要求出任意两点之间的距离最长的那个吧
【在 p*****2 的大作中提到】
:
: 你这个path是可以任意点开始，任意点结束吧？
|
l**b
发帖数: 457 | 8 那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
|
p*****2
发帖数: 21240 | 9
老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
）。
然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）
【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
|
l**b
发帖数: 457 | 10 BTW，赞面经，bless你快点找到工作。
1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。 |
|
|
s********s
发帖数: 49 | 11
然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）
这个某一节点是哪个节点？
【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
|
d**********x
发帖数: 4083 | 12 leetcode真是啥都有啊。
这是我当年在国内被G灭的面试题。。。
我对G的心理阴影是无穷大。。。
【在 l**b 的大作中提到】
: 那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
|
s********s
发帖数: 49 | 13
Thanks 啦！ :)
那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
还没刷到这个题的说>_<看来还是刷题不够多 555
【在 l**b 的大作中提到】
: BTW，赞面经，bless你快点找到工作。
: 1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。
|
l*****a
发帖数: 14598 | 14 你上次就问人家学校，这次又问
【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
|
l*****a
发帖数: 14598 | 15 bless
打算吧你的2个面经存下来以后慢慢看
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
s********s
发帖数: 49 | 16
大神也在加拿大的么？这个找工作的规划求建议啊！！
【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
|
g**e
发帖数: 6127 | 17 longest path难道不是肯定由两个leaf node组成的？
【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
|
s********s
发帖数: 49 | 18
多谢多谢！！
你上次就问人家学校，这次又问
哈哈，恩恩,上次新人报道的时候其实就被问过了>_<
【在 l*****a 的大作中提到】
: bless
: 打算吧你的2个面经存下来以后慢慢看
:
: 路？
|
s********s
发帖数: 49 | 19
对，这个后来我也想了想，应该是这样子的
【在 g**e 的大作中提到】
: longest path难道不是肯定由两个leaf node组成的？
|
c*****a
发帖数: 808 | 20 练一下 不知道对不对
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right, maxPath);
return Math.max(left, right)+1;
} |
|
|
l*****a
发帖数: 14598 | 21 你说的比他问的难多了
他那个不需要care结点的值
【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
|
g**e
发帖数: 6127 | 22 o
/
o
/ \
o o
/ \
o o
【在 c*****a 的大作中提到】
: 练一下 不知道对不对
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right, maxPath);
: return Math.max(left, right)+1;
: }
|
s********s
发帖数: 49 | 23
嗯，我这个是没权值的，大神给个简单易懂的思路? :P
【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
|
c**s
发帖数: 159 | 24 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。 |
s********s
发帖数: 49 | 25
这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？
【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
|
f*****7
发帖数: 92 | 26 显然是用divide-and-conquer求diameter
最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
二叉树可以用modified post-order做，因为后序遍历的实质就是分治
n-ary tree，可以用两次BFS，证明很难，搜一下就有了 |
l*****a
发帖数: 14598 | 27 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
3种可能性递归
【在 s********s 的大作中提到】
:
: 这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？
|
g**e
发帖数: 6127 | 28 正解
这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
他们is_bst
【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
|
l*****a
发帖数: 14598 | 29 你把path跟深度混淆了
【在 c*****a 的大作中提到】
: 练一下 不知道对不对
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right, maxPath);
: return Math.max(left, right)+1;
: }
|
c*****a
发帖数: 808 | 30 测试了下,是4
对不对
【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
|
|
|
g**e
发帖数: 6127 | 31 显然不对啊，longest path明明是5
【在 c*****a 的大作中提到】
: 测试了下,是4
: 对不对
|
c*****a
发帖数: 808 | 32 maximum sum of bst那种?
【在 l*****a 的大作中提到】
: 你把path跟深度混淆了
|
c*****a
发帖数: 808 | 33 哦，我以为是算edges,这样就5了
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right+1, maxPath);
return Math.max(left, right)+1;
}
【在 g**e 的大作中提到】
: 显然不对啊，longest path明明是5
|
s********s
发帖数: 49 | 34
这个很make sense！！
【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
|
s********s
发帖数: 49 | 35
is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？
【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
|
l***i
发帖数: 1309 | 36 Given root of tree, longest path either uses root or not.
struct Node {
vector children;
};
int longest_path(Node *root)
{
return longest(root).first;
}
// returns (first, second)
// first is longest path length within subtree at root
// second is longest path length from any leaf to root
pair longest(Node *root)
{
if (root == NULL) return make_pair(0,0);
// best is length of longest path fully contained in this subtree,
// single is length of longest path from a leaf to root
int best = 0, single = 0;
int nchild = root->children.size();
vector child_len(nchild, 0);
for (int i=0; i
pair p = longest(root->children[i]);
child_len[i] = p.second;
best = max(best, p.first);
}
if (nchild == 0) return make_pair(1, 1);
sort(child_len.begin(), child_len.end(), greater());
single = 1 + child_len[0];
if (nchild == 1) {
best = max(best, single);
} else {
best = max(best, single + child_len[1]);
}
return make_pair(best, single);
} |
g**e
发帖数: 6127 | 37 银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
化一般就都挂了。
唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
当然,人家把我们的offer据了
【在 s********s 的大作中提到】
:
: is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？
|
d**********x
发帖数: 4083 | 38 两次bfs没什么难的啊
我记得是反证法解决
找个高中小孩来证肯定三下五除二就出来了
【在 f*****7 的大作中提到】
: 显然是用divide-and-conquer求diameter
: 最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
: 二叉树可以用modified post-order做，因为后序遍历的实质就是分治
: n-ary tree，可以用两次BFS，证明很难，搜一下就有了
|
l*****a
发帖数: 14598 | 39
用的是MAX_VALUE/MIN_VALUE那种解法？
嫌你们给的少？
【在 g**e 的大作中提到】
: 银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
: 化一般就都挂了。
: 唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
: 当然,人家把我们的offer据了
|
g**e
发帖数: 6127 | 40 面SDE2，给的SDE3，应该还不错吧
这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
水平相当高
何优
了。
【在 l*****a 的大作中提到】
:
: 用的是MAX_VALUE/MIN_VALUE那种解法？
: 嫌你们给的少？
|
|
|
l*****a
发帖数: 14598 | 41 这牛人哪国的？原来什么厂
估计半路出家，但是很聪明
【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
|
s********s
发帖数: 49 | 42
gate是在？Amazon?
【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
|
g**e
发帖数: 6127 | 43 某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
很多，所以在bar raiser的强烈要求下，给了SDE3
【在 l*****a 的大作中提到】
: 这牛人哪国的？原来什么厂
: 估计半路出家，但是很聪明
|
p*****2
发帖数: 21240 | 44
那就相当于每个节点的值都是1吧。
【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
|
p*****2
发帖数: 21240 | 45
没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？
【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
|
l*******b
发帖数: 2586 | 46 tree 有parent指针哪里都可以当root吧。嗯
或者有第一次搜索得到的路径也够用了
【在 p*****2 的大作中提到】
:
: 没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？
|
p*****2
发帖数: 21240 | 47
题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。
【在 l*******b 的大作中提到】
: tree 有parent指针哪里都可以当root吧。嗯
: 或者有第一次搜索得到的路径也够用了
|
h*******e
发帖数: 1377 | |
l*******b
发帖数: 2586 | 49 想起来感觉还行，第一次的存在一个stack里，总是先搜child，需要朝parent方向搜索
的时候pop出来填到现在搜索的路径里就好了
【在 p*****2 的大作中提到】
:
: 题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。
|
s********l
发帖数: 998 | 50 VP? 为什么他要转行做sde啊？
【在 g**e 的大作中提到】
: 某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
: 很多，所以在bar raiser的强烈要求下，给了SDE3
|
|
|
s********l
发帖数: 998 | 51 你第一题用heap? 一个k size的heap?
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
s**s
发帖数: 70 | 52 这个思路的确不错。 想了一下，可以反证，用cut-paste来证明第一次dfs的结果为最
长路径的端点。
【在 s********s 的大作中提到】
:
: gate是在？Amazon?
|
f*********m
发帖数: 726 | 53 感觉可以用类似于leetcode Binary Tree Maximum Path Sum的思路：不过每个node要
考虑有N个chidren，每个node包括的值为1。
大牛们有何见解？
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
l*****a
发帖数: 14598 | 54 金融界的VP顶多是个小lead,甚至很多时候没有report
就算个Sr software engineer?
【在 s********l 的大作中提到】
: VP? 为什么他要转行做sde啊？
|
h*******e
发帖数: 1377 | 55 算小組長吧 MD還是很牛的 http://blog.sina.com.cn/s/blog_4cf8aad30102dz44.html
【在 l*****a 的大作中提到】
: 金融界的VP顶多是个小lead,甚至很多时候没有report
: 就算个Sr software engineer?
|
w****x
发帖数: 2483 | 56 等等，这题的最大路径不考虑权值把，那递归不久出来了？ |
f*********m
发帖数: 726 | 57 可以考虑所有节点相同的权值，所以sum为节点的个数。
【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
|
f*******t
发帖数: 7549 | 58 这题还好吧，代码很简单：
class TreeNodeStatus {
int maxLength;
int maxDepth;
}
private TreeNodeStatus getTreeNodeStatus(TreeNode node) {
TreeNodeStatus status = new TreeNodeStatus();
if (node == null) {
status.maxLength = 0;
status.maxDepth = 0;
} else if (node.left == null && node.right == null) {
status.maxLength = 1;
status.maxDepth = 1;
} else {
TreeNodeStatus leftStatus = getTreeNodeStatus(node.left);
TreeNodeStatus rightStatus = getTreeNodeStatus(node.right);
status.maxDepth = Math.max(leftStatus.maxDepth + 1, rightStatus.
maxDepth + 1);
status.maxLength = Math.max(leftStatus.maxLength, rightStatus.
maxLength);
status.maxLength = Math.max(status.maxLength, leftStatus.
maxDepth + rightStatus.maxDepth + 1);
}
return status;
}
public int longestPath(TreeNode root) {
TreeNodeStatus status = getTreeNodeStatus(root);
return status.maxLength;
} |
f*********m
发帖数: 726 | 59 这个思路和leetcode的Binary Tree Maximum Path Sum一样吧。
【在 c*****a 的大作中提到】
: 哦，我以为是算edges,这样就5了
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right+1, maxPath);
: return Math.max(left, right)+1;
: }
|
c********t
发帖数: 5706 | 60 思路差不多吧。
不过有bug, maxPath = Math.max(left+right+2, maxPath);而且事先还要判断left or
right是不是 0, 有0就不是left+right+2了，要分情况处理了。
还有哦，题目没说是二叉树。
ls那些人为啥不赞同你啊？
【在 c*****a 的大作中提到】
: 练一下 不知道对不对
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right, maxPath);
: return Math.max(left, right)+1;
: }
|
|
|
c********t
发帖数: 5706 | 61 欢迎回来啊！
我也没明白为啥就变复杂了。
【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
|
f*********m
发帖数: 726 | 62 rp不行，呵呵。
or
【在 c********t 的大作中提到】
: 思路差不多吧。
: 不过有bug, maxPath = Math.max(left+right+2, maxPath);而且事先还要判断left or
: right是不是 0, 有0就不是left+right+2了，要分情况处理了。
: 还有哦，题目没说是二叉树。
: ls那些人为啥不赞同你啊？
|
x*****0
发帖数: 452 | |
s********s
发帖数: 49 | 64 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
后开始做题，让merge k 个 sorted list，用heap做了。
第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
。顺便请教一下大家两个困扰我挺久的问题：
(1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
因为我想明年一毕业就能直接去美国工作，这样的话势必要在明年三四月的时候找好
full time了吧，不然的话h1b神马的是不是会有问题？我这样的情况怎么样规划好一点
？求建议啊！
(2) 像这次面我的两个人在出题之前都说了句，要是题目我碰到过的话就和他们说，他
们可以换一个题目。那是不是每次碰到做过的题目，是不是实际中都是都要老实交代呢
，还是可以慢慢讲思路？ |
p*****2
发帖数: 21240 | 65 longest path前不久讨论过。没见过不太容易写好。
UW or UT? 其实题目见过能写好也不容易。 |
s********s
发帖数: 49 | 66
longest path我到时也去搜过，但是好多solution,有的也没看懂，大神给点思路？
【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
|
l**b
发帖数: 457 | 67 longest path怎么定义的啊？tree里面任何2个node之间的距离？ |
s********s
发帖数: 49 | 68
恩，对的，就是这个意思。
【在 l**b 的大作中提到】
: longest path怎么定义的啊？tree里面任何2个node之间的距离？
|
p*****2
发帖数: 21240 | 69
你这个path是可以任意点开始，任意点结束吧？
【在 s********s 的大作中提到】
:
: 恩，对的，就是这个意思。
|
s********s
发帖数: 49 | 70
嗯，其实就是要求出任意两点之间的距离最长的那个吧
【在 p*****2 的大作中提到】
:
: 你这个path是可以任意点开始，任意点结束吧？
|
|
|
l**b
发帖数: 457 | 71 那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
|
p*****2
发帖数: 21240 | 72
老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
）。
然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）
【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
|
l**b
发帖数: 457 | 73 BTW，赞面经，bless你快点找到工作。
1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。 |
s********s
发帖数: 49 | 74
然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）
这个某一节点是哪个节点？
【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
|
d**********x
发帖数: 4083 | 75 leetcode真是啥都有啊。
这是我当年在国内被G灭的面试题。。。
我对G的心理阴影是无穷大。。。
【在 l**b 的大作中提到】
: 那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
|
s********s
发帖数: 49 | 76
Thanks 啦！ :)
那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
还没刷到这个题的说>_<看来还是刷题不够多 555
【在 l**b 的大作中提到】
: BTW，赞面经，bless你快点找到工作。
: 1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。
|
l*****a
发帖数: 14598 | 77 你上次就问人家学校，这次又问
【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
|
l*****a
发帖数: 14598 | 78 bless
打算吧你的2个面经存下来以后慢慢看
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
s********s
发帖数: 49 | 79
大神也在加拿大的么？这个找工作的规划求建议啊！！
【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
|
g**e
发帖数: 6127 | 80 longest path难道不是肯定由两个leaf node组成的？
【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
|
|
|
s********s
发帖数: 49 | 81
多谢多谢！！
你上次就问人家学校，这次又问
哈哈，恩恩,上次新人报道的时候其实就被问过了>_<
【在 l*****a 的大作中提到】
: bless
: 打算吧你的2个面经存下来以后慢慢看
:
: 路？
|
s********s
发帖数: 49 | 82
对，这个后来我也想了想，应该是这样子的
【在 g**e 的大作中提到】
: longest path难道不是肯定由两个leaf node组成的？
|
c*****a
发帖数: 808 | 83 练一下 不知道对不对
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right, maxPath);
return Math.max(left, right)+1;
} |
l*****a
发帖数: 14598 | 84 你说的比他问的难多了
他那个不需要care结点的值
【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
|
g**e
发帖数: 6127 | 85 o
/
o
/ \
o o
/ \
o o
【在 c*****a 的大作中提到】
: 练一下 不知道对不对
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right, maxPath);
: return Math.max(left, right)+1;
: }
|
s********s
发帖数: 49 | 86
嗯，我这个是没权值的，大神给个简单易懂的思路? :P
【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
|
c**s
发帖数: 159 | 87 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。 |
s********s
发帖数: 49 | 88
这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？
【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
|
f*****7
发帖数: 92 | 89 显然是用divide-and-conquer求diameter
最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
二叉树可以用modified post-order做，因为后序遍历的实质就是分治
n-ary tree，可以用两次BFS，证明很难，搜一下就有了 |
l*****a
发帖数: 14598 | 90 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
3种可能性递归
【在 s********s 的大作中提到】
:
: 这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？
|
|
|
g**e
发帖数: 6127 | 91 正解
这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
他们is_bst
【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
|
l*****a
发帖数: 14598 | 92 你把path跟深度混淆了
【在 c*****a 的大作中提到】
: 练一下 不知道对不对
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right, maxPath);
: return Math.max(left, right)+1;
: }
|
c*****a
发帖数: 808 | 93 测试了下,是4
对不对
【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
|
g**e
发帖数: 6127 | 94 显然不对啊，longest path明明是5
【在 c*****a 的大作中提到】
: 测试了下,是4
: 对不对
|
c*****a
发帖数: 808 | 95 maximum sum of bst那种?
【在 l*****a 的大作中提到】
: 你把path跟深度混淆了
|
c*****a
发帖数: 808 | 96 哦，我以为是算edges,这样就5了
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right+1, maxPath);
return Math.max(left, right)+1;
}
【在 g**e 的大作中提到】
: 显然不对啊，longest path明明是5
|
s********s
发帖数: 49 | 97
这个很make sense！！
【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
|
s********s
发帖数: 49 | 98
is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？
【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
|
l***i
发帖数: 1309 | 99 Given root of tree, longest path either uses root or not.
struct Node {
vector children;
};
int longest_path(Node *root)
{
return longest(root).first;
}
// returns (first, second)
// first is longest path length within subtree at root
// second is longest path length from any leaf to root
pair longest(Node *root)
{
if (root == NULL) return make_pair(0,0);
// best is length of longest path fully contained in this subtree,
// single is length of longest path from a leaf to root
int best = 0, single = 0;
int nchild = root->children.size();
vector child_len(nchild, 0);
for (int i=0; i
pair p = longest(root->children[i]);
child_len[i] = p.second;
best = max(best, p.first);
}
if (nchild == 0) return make_pair(1, 1);
sort(child_len.begin(), child_len.end(), greater());
single = 1 + child_len[0];
if (nchild == 1) {
best = max(best, single);
} else {
best = max(best, single + child_len[1]);
}
return make_pair(best, single);
} |
g**e
发帖数: 6127 | 100 银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
化一般就都挂了。
唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
当然,人家把我们的offer据了
【在 s********s 的大作中提到】
:
: is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？
|
|
|
d**********x
发帖数: 4083 | 101 两次bfs没什么难的啊
我记得是反证法解决
找个高中小孩来证肯定三下五除二就出来了
【在 f*****7 的大作中提到】
: 显然是用divide-and-conquer求diameter
: 最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
: 二叉树可以用modified post-order做，因为后序遍历的实质就是分治
: n-ary tree，可以用两次BFS，证明很难，搜一下就有了
|
l*****a
发帖数: 14598 | 102
用的是MAX_VALUE/MIN_VALUE那种解法？
嫌你们给的少？
【在 g**e 的大作中提到】
: 银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
: 化一般就都挂了。
: 唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
: 当然,人家把我们的offer据了
|
g**e
发帖数: 6127 | 103 面SDE2，给的SDE3，应该还不错吧
这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
水平相当高
何优
了。
【在 l*****a 的大作中提到】
:
: 用的是MAX_VALUE/MIN_VALUE那种解法？
: 嫌你们给的少？
|
l*****a
发帖数: 14598 | 104 这牛人哪国的？原来什么厂
估计半路出家，但是很聪明
【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
|
s********s
发帖数: 49 | 105
gate是在？Amazon?
【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
|
g**e
发帖数: 6127 | 106 某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
很多，所以在bar raiser的强烈要求下，给了SDE3
【在 l*****a 的大作中提到】
: 这牛人哪国的？原来什么厂
: 估计半路出家，但是很聪明
|
p*****2
发帖数: 21240 | 107
那就相当于每个节点的值都是1吧。
【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
|
p*****2
发帖数: 21240 | 108
没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？
【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
|
l*******b
发帖数: 2586 | 109 tree 有parent指针哪里都可以当root吧。嗯
或者有第一次搜索得到的路径也够用了
【在 p*****2 的大作中提到】
:
: 没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？
|
p*****2
发帖数: 21240 | 110
题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。
【在 l*******b 的大作中提到】
: tree 有parent指针哪里都可以当root吧。嗯
: 或者有第一次搜索得到的路径也够用了
|
|
|
h*******e
发帖数: 1377 | |
l*******b
发帖数: 2586 | 112 想起来感觉还行，第一次的存在一个stack里，总是先搜child，需要朝parent方向搜索
的时候pop出来填到现在搜索的路径里就好了
【在 p*****2 的大作中提到】
:
: 题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。
|
s********l
发帖数: 998 | 113 VP? 为什么他要转行做sde啊？
【在 g**e 的大作中提到】
: 某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
: 很多，所以在bar raiser的强烈要求下，给了SDE3
|
s********l
发帖数: 998 | 114 你第一题用heap? 一个k size的heap?
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
s**s
发帖数: 70 | 115 这个思路的确不错。 想了一下，可以反证，用cut-paste来证明第一次dfs的结果为最
长路径的端点。
【在 s********s 的大作中提到】
:
: gate是在？Amazon?
|
f*********m
发帖数: 726 | 116 感觉可以用类似于leetcode Binary Tree Maximum Path Sum的思路：不过每个node要
考虑有N个chidren，每个node包括的值为1。
大牛们有何见解？
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
l*****a
发帖数: 14598 | 117 金融界的VP顶多是个小lead,甚至很多时候没有report
就算个Sr software engineer?
【在 s********l 的大作中提到】
: VP? 为什么他要转行做sde啊？
|
h*******e
发帖数: 1377 | 118 算小組長吧 MD還是很牛的 http://blog.sina.com.cn/s/blog_4cf8aad30102dz44.html
【在 l*****a 的大作中提到】
: 金融界的VP顶多是个小lead,甚至很多时候没有report
: 就算个Sr software engineer?
|
w****x
发帖数: 2483 | 119 等等，这题的最大路径不考虑权值把，那递归不久出来了？ |
f*********m
发帖数: 726 | 120 可以考虑所有节点相同的权值，所以sum为节点的个数。
【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
|
|
|
f*******t
发帖数: 7549 | 121 这题还好吧，代码很简单：
class TreeNodeStatus {
int maxLength;
int maxDepth;
}
private TreeNodeStatus getTreeNodeStatus(TreeNode node) {
TreeNodeStatus status = new TreeNodeStatus();
if (node == null) {
status.maxLength = 0;
status.maxDepth = 0;
} else if (node.left == null && node.right == null) {
status.maxLength = 1;
status.maxDepth = 1;
} else {
TreeNodeStatus leftStatus = getTreeNodeStatus(node.left);
TreeNodeStatus rightStatus = getTreeNodeStatus(node.right);
status.maxDepth = Math.max(leftStatus.maxDepth + 1, rightStatus.
maxDepth + 1);
status.maxLength = Math.max(leftStatus.maxLength, rightStatus.
maxLength);
status.maxLength = Math.max(status.maxLength, leftStatus.
maxDepth + rightStatus.maxDepth + 1);
}
return status;
}
public int longestPath(TreeNode root) {
TreeNodeStatus status = getTreeNodeStatus(root);
return status.maxLength;
} |
f*********m
发帖数: 726 | 122 这个思路和leetcode的Binary Tree Maximum Path Sum一样吧。
【在 c*****a 的大作中提到】
: 哦，我以为是算edges,这样就5了
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right+1, maxPath);
: return Math.max(left, right)+1;
: }
|
c********t
发帖数: 5706 | 123 思路差不多吧。
不过有bug, maxPath = Math.max(left+right+2, maxPath);而且事先还要判断left or
right是不是 0, 有0就不是left+right+2了，要分情况处理了。
还有哦，题目没说是二叉树。
ls那些人为啥不赞同你啊？
【在 c*****a 的大作中提到】
: 练一下 不知道对不对
: static int maxPath=0;
: private static int longestPath(BSTNode node){
: if(node==null) return 0;
: int left = longestPath(node.left);
: int right = longestPath(node.right);
: maxPath = Math.max(left+right, maxPath);
: return Math.max(left, right)+1;
: }
|
c********t
发帖数: 5706 | 124 欢迎回来啊！
我也没明白为啥就变复杂了。
【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
|
f*********m
发帖数: 726 | 125 rp不行，呵呵。
or
【在 c********t 的大作中提到】
: 思路差不多吧。
: 不过有bug, maxPath = Math.max(left+right+2, maxPath);而且事先还要判断left or
: right是不是 0, 有0就不是left+right+2了，要分情况处理了。
: 还有哦，题目没说是二叉树。
: ls那些人为啥不赞同你啊？
|
x*****0
发帖数: 452 | |
j********x
发帖数: 2330 | |
b*****g
发帖数: 145 | |
s****y
发帖数: 503 | |
j*********g
发帖数: 36 | 130 For 2, for each edge (u,v) find the longest path from u to a leaf that doesn
't contain (u,v); do the same for v. You can do this in linear time,
starting from leaves. |
|
|
s********x
发帖数: 914 | 131 抛砖引玉写了一个哈
// return [farthest path from root, longest path]
public static int[] getLongestPathInTree(TreeNode p) {
int farthestPathFromRoot = 0, secondFarthestPathFromRoot = 0,
longestPath = 0;
for (TreeNode child : p.getChildren()) {
int[] result = getLongestPathInTree(child);
int pathToFarthestChild = result[0] + child.weightToParent;
if (pathToFarthestChild > farthestPathFromRoot) {
secondFarthestPathFromRoot = farthestPathFromRoot;
farthestPathFromRoot = pathToFarthestChild;
}
if (result[1] > longestPath) {
longestPath = result[1];
}
}
if (secondFarthestPathFromRoot + farthestPathFromRoot > longestPath)
{
longestPath = secondFarthestPathFromRoot + farthestPathFromRoot;
}
return new int[] {farthestPathFromRoot, longestPath};
}
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
p*****2
发帖数: 21240 | 132
没说一定是从root开始吧？
【在 s********x 的大作中提到】
: 抛砖引玉写了一个哈
: // return [farthest path from root, longest path]
: public static int[] getLongestPathInTree(TreeNode p) {
: int farthestPathFromRoot = 0, secondFarthestPathFromRoot = 0,
: longestPath = 0;
: for (TreeNode child : p.getChildren()) {
: int[] result = getLongestPathInTree(child);
: int pathToFarthestChild = result[0] + child.weightToParent;
: if (pathToFarthestChild > farthestPathFromRoot) {
: secondFarthestPathFromRoot = farthestPathFromRoot;
|
s********x
发帖数: 914 | 133 对的，在recursion中的某个root，即longestPath可以经过任意node
【在 p*****2 的大作中提到】
:
: 没说一定是从root开始吧？
|
r****c
发帖数: 2585 | 134 给两个不同算法吧，就不写code了
1. 第一种，比较容易懂。longest path可能很多，但是所有longest path只有一个点
是largest depth from root，也就是tree depth。（用反证法来证明这个observation
）。先找任意一个叶子节点是largest distance from root，然后用这个点作为root，
找largest distance from root
2. 第二种，写程序比较方便，recursive，找到longest path AND largest depth of
the tree
say d(T) and L(T)
then d(T) = max (d(T->left), d(d-right))
L(T) = max( L(T->left), L(T->right), d(T->left) + d(T->Right) + 1) |
p*****2
发帖数: 21240 | 135
observation
of
没说是二叉树吧？
【在 r****c 的大作中提到】
: 给两个不同算法吧，就不写code了
: 1. 第一种，比较容易懂。longest path可能很多，但是所有longest path只有一个点
: 是largest depth from root，也就是tree depth。（用反证法来证明这个observation
: ）。先找任意一个叶子节点是largest distance from root，然后用这个点作为root，
: 找largest distance from root
: 2. 第二种，写程序比较方便，recursive，找到longest path AND largest depth of
: the tree
: say d(T) and L(T)
: then d(T) = max (d(T->left), d(d-right))
: L(T) = max( L(T->left), L(T->right), d(T->left) + d(T->Right) + 1)
|
s********x
发帖数: 914 | 136 我的思路基本上就是二叉树的变种罢了。我写的code就是楼上说的思路
【在 p*****2 的大作中提到】
:
: observation
: of
: 没说是二叉树吧？
|
x*******i
发帖数: 26 | 137 跟那个二叉树最大path sum思路差不多吧。
递归所有子树，每个返回两个值（包括根节点的最长路径 a_i， 所有的最长路径b_i）
，然后把这些值归总来算当前的两个值( max(a_i)+1, max(all b_i's ， 1+最大的两
个a_i))
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
p*****2
发帖数: 21240 | 138
应该比那个还简单一点
【在 x*******i 的大作中提到】
: 跟那个二叉树最大path sum思路差不多吧。
: 递归所有子树，每个返回两个值（包括根节点的最长路径 a_i， 所有的最长路径b_i）
: ，然后把这些值归总来算当前的两个值( max(a_i)+1, max(all b_i's ， 1+最大的两
: 个a_i))
:
: 路？
|
h**o
发帖数: 548 | 139 the same as Diameter of a Binary Tree 吧。
longest path(LP) of root = max(LP of root->left, LP of root->right, height(
root->left)+height(root->right)+1).
height 和 LP of children 可以一起算。
多子的情况一样。
路？
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
h**o
发帖数: 548 | 140 贴一个多子的代码。请指正
int LP(Node* root, int& hroot){ //h: height
if(!root) { hroot = 0; return 0;}
int max_hchild1 = INT_MIN, max_hchild2 = INT_MIN, maxlen = INT_MIN;
int length;
Node* cur_child = root->children;
while(cur_child){
maxlen = max(maxlen, LP(cur_child, hchild));//找child中最长path长.
if (hchild>=maxlen2){ //从child中找两个最长height,其中maxlen1>=
maxlen2
if (hchild>=maxlen1) { maxlen2 =maxlen1; maxlen1 = hchild; }
else maxlen2 = hchild;
}
cur_child = cur_child->next;
}
hroot= max(max_hchild1, max_hchild2)+1;
return max(maxlen, max_hchild1+max_hchild2+2);
} |
|
|
w******g
发帖数: 189 | 141
路？
请问第一题你是直接实现一个heap吗？还是用std::multiset？但是std::multiset在内
部是用binary search tree实现的哦。
【在 s********s 的大作中提到】
: 前天收到hr的邮件通知被拒了，奉上面经攒点人品吧
: 这是第二轮面试，共两个人，第一个是中国人吧，然后先示扯了扯之前做过的东西，然
: 后开始做题，让merge k 个 sorted list，用heap做了。
: 第二个上来应该是美国人了，一个manager，直接开始做题，让找一棵树(不一定是二叉
: 树)里面的longest path,没什么很好的思路，我说了一个找出所有节点对应的子树中的
: longest path然后比较这些得出global的最长，感觉回答的不好。大家有没有好的思路？
: 问hr要feedback说是我写的code效率不高，应该是挂在第二个人上了。哎。move on吧
: 。顺便请教一下大家两个困扰我挺久的问题：
: (1) 我是在加拿大读研，明年毕业，我之前是有想先找个实习什么的，觉得有个实习经
: 验找full time会容易些，但是如果明年暑假去实习，找full time的工作又有点问题，
|
s********x
发帖数: 914 | 142 那我写一下吧
public static Node mergeKSortedLists(Node[] l) {
// heapify: Make it a heap: Trickling Down in Place: start at node n
/2-1, the rightmost node with children
// O(n)
for (int i = (l.length / 2 - 1); i >= 0; i--)
trickleDown(l, i, l.length);
int heapSize = l.length; // size of the heap
// use an extra dummy node as the head
Node dummy = new Node();
Node pre = dummy;
while (heapSize > 0) {
Node heapRoot = l[0];
l[0] = l[0].getNext();
pre.setNext(heapRoot);
pre = heapRoot;
if (l[0] == null) { // empty list found, remove current list
from heap
removeHeapRoot(l, heapSize--);
}
else {
trickleDown(l, 0, heapSize); // heap root is changed to l[0]
.next
}
}
return dummy.getNext();
}
private static Node removeHeapRoot(Node[] heapArray, int size){
Node root = heapArray[0];
heapArray[0] = heapArray[--size]; // last element is heapArray[size
- 1]
trickleDown(heapArray, 0, size);
return root;
}
private static void trickleDown(Node[] l, int i, int size) {
// the last element is a[size-1] and its parent is a[size/2-1]
while (i < size / 2) {
int leftChild = 2 * i + 1;
int rightChild = leftChild + 1;
int smallerChild;
if (rightChild < size // rightChild exists?
&& l[leftChild].getValue() > l[rightChild].getValue())
smallerChild = rightChild;
else
smallerChild = leftChild;
if (l[i].getValue() <= l[smallerChild].getValue())
break;
swap(l, i, smallerChild);
i = smallerChild;
}
}
【在 w******g 的大作中提到】
:
: 路？
: 请问第一题你是直接实现一个heap吗？还是用std::multiset？但是std::multiset在内
: 部是用binary search tree实现的哦。
|
w******g
发帖数: 189 | 143 多谢。我是问遇到merge k 个 sorted list这道题，一共就15到20分钟时间，真的够时
间先写一个heap再写主程序么？ |
s********x
发帖数: 914 | 144 trickleDown 和 removeHeapRoot 可以不用实现，先空在那里。
本来就是可以写pseudo code的。所以主要代码也就25行。
【在 w******g 的大作中提到】
: 多谢。我是问遇到merge k 个 sorted list这道题，一共就15到20分钟时间，真的够时
: 间先写一个heap再写主程序么？
|
c********p
发帖数: 1969 | |
