logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
公厕打这样的广告也太重口味了吧！！
avatar
公厕打这样的广告也太重口味了吧！！# Joke - 肚皮舞运动
s*s
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) 像这次面我的两个人在出题之前都说了句，要是题目我碰到过的话就和他们说，他
们可以换一个题目。那是不是每次碰到做过的题目，是不是实际中都是都要老实交代呢
，还是可以慢慢讲思路？
avatar
n*g
2 楼
看旅游版推荐说这个fidelity出国取现很方便.
来本版已经看过精华区了,但是是06年了,不知道现在政策有什么变化.
还是赠送AA里程+$100吗?链接有吗?
谢谢!
avatar
r*e
3 楼
avatar
p*2
4 楼
longest path前不久讨论过。没见过不太容易写好。
UW or UT? 其实题目见过能写好也不容易。
avatar
n*g
5 楼
送$100的那个链接已经不管用了.
avatar
s*s
6 楼

longest path我到时也去搜过，但是好多solution,有的也没看懂，大神给点思路？

【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
avatar
l*b
8 楼
longest path怎么定义的啊？tree里面任何2个node之间的距离？
avatar
s*s
9 楼

恩，对的，就是这个意思。

【在 l**b 的大作中提到】
: longest path怎么定义的啊？tree里面任何2个node之间的距离？
avatar
p*2
10 楼

你这个path是可以任意点开始，任意点结束吧？

【在 s********s 的大作中提到】
:
: 恩，对的，就是这个意思。
avatar
s*s
11 楼

嗯，其实就是要求出任意两点之间的距离最长的那个吧

【在 p*****2 的大作中提到】
:
: 你这个path是可以任意点开始，任意点结束吧？
avatar
l*b
12 楼
那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？

【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
avatar
p*2
13 楼

老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
）。
然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）

【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
avatar
l*b
14 楼
BTW，赞面经，bless你快点找到工作。
1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。
avatar
s*s
15 楼

然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）
这个某一节点是哪个节点？

【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
avatar
d*x
16 楼
leetcode真是啥都有啊。
这是我当年在国内被G灭的面试题。。。
我对G的心理阴影是无穷大。。。

【在 l**b 的大作中提到】
: 那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
avatar
s*s
17 楼

Thanks 啦！ :)
那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
还没刷到这个题的说>_
【在 l**b 的大作中提到】
: BTW，赞面经，bless你快点找到工作。
: 1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。
avatar
l*a
18 楼
你上次就问人家学校，这次又问

【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
avatar
l*a
19 楼
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的工作又有点问题，
avatar
s*s
20 楼

大神也在加拿大的么？这个找工作的规划求建议啊！！

【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
avatar
g*e
21 楼
longest path难道不是肯定由两个leaf node组成的？

【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
avatar
s*s
22 楼

多谢多谢！！
你上次就问人家学校，这次又问
哈哈，恩恩,上次新人报道的时候其实就被问过了>_<

【在 l*****a 的大作中提到】
: bless
: 打算吧你的2个面经存下来以后慢慢看
:
: 路？
avatar
s*s
23 楼

对，这个后来我也想了想，应该是这样子的

【在 g**e 的大作中提到】
: longest path难道不是肯定由两个leaf node组成的？
avatar
c*a
24 楼
练一下 不知道对不对
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;
}
avatar
l*a
25 楼
你说的比他问的难多了
他那个不需要care结点的值

【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
avatar
g*e
26 楼
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;
: }
avatar
s*s
27 楼

嗯，我这个是没权值的，大神给个简单易懂的思路? :P

【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
avatar
c*s
28 楼
树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
avatar
s*s
29 楼

这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？

【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
avatar
f*7
30 楼
显然是用divide-and-conquer求diameter
最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
二叉树可以用modified post-order做，因为后序遍历的实质就是分治
n-ary tree，可以用两次BFS，证明很难，搜一下就有了
avatar
l*a
31 楼
最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
3种可能性递归

【在 s********s 的大作中提到】
:
: 这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？
avatar
g*e
32 楼
正解
这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
他们is_bst

【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
avatar
l*a
33 楼
你把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;
: }
avatar
c*a
34 楼
测试了下,是4
对不对

【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
avatar
g*e
35 楼
显然不对啊，longest path明明是5

【在 c*****a 的大作中提到】
: 测试了下,是4
: 对不对
avatar
c*a
36 楼
maximum sum of bst那种?

【在 l*****a 的大作中提到】
: 你把path跟深度混淆了
avatar
c*a
37 楼
哦，我以为是算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
avatar
s*s
38 楼

这个很make sense！！

【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
avatar
s*s
39 楼

is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？

【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
avatar
l*i
40 楼
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; ipair 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);
}
avatar
g*e
41 楼
银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
化一般就都挂了。
唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
当然,人家把我们的offer据了

【在 s********s 的大作中提到】
:
: is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？
avatar
d*x
42 楼
两次bfs没什么难的啊
我记得是反证法解决
找个高中小孩来证肯定三下五除二就出来了

【在 f*****7 的大作中提到】
: 显然是用divide-and-conquer求diameter
: 最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
: 二叉树可以用modified post-order做，因为后序遍历的实质就是分治
: n-ary tree，可以用两次BFS，证明很难，搜一下就有了
avatar
l*a
43 楼

用的是MAX_VALUE/MIN_VALUE那种解法？
嫌你们给的少？

【在 g**e 的大作中提到】
: 银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
: 化一般就都挂了。
: 唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
: 当然,人家把我们的offer据了
avatar
g*e
44 楼
面SDE2，给的SDE3，应该还不错吧
这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
水平相当高

何优
了。

【在 l*****a 的大作中提到】
:
: 用的是MAX_VALUE/MIN_VALUE那种解法？
: 嫌你们给的少？
avatar
l*a
45 楼
这牛人哪国的？原来什么厂
估计半路出家，但是很聪明

【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
avatar
s*s
46 楼

gate是在？Amazon?

【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
avatar
g*e
47 楼
某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
很多，所以在bar raiser的强烈要求下，给了SDE3

【在 l*****a 的大作中提到】
: 这牛人哪国的？原来什么厂
: 估计半路出家，但是很聪明
avatar
p*2
48 楼

那就相当于每个节点的值都是1吧。

【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
avatar
p*2
49 楼

没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？

【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
avatar
l*b
50 楼
tree 有parent指针哪里都可以当root吧。嗯
或者有第一次搜索得到的路径也够用了

【在 p*****2 的大作中提到】
:
: 没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？
avatar
p*2
51 楼

题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。

【在 l*******b 的大作中提到】
: tree 有parent指针哪里都可以当root吧。嗯
: 或者有第一次搜索得到的路径也够用了
avatar
h*e
52 楼
拎兩次樹那道題。。
avatar
l*b
53 楼
想起来感觉还行，第一次的存在一个stack里，总是先搜child，需要朝parent方向搜索
的时候pop出来填到现在搜索的路径里就好了

【在 p*****2 的大作中提到】
:
: 题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。
avatar
s*l
54 楼
VP? 为什么他要转行做sde啊？

【在 g**e 的大作中提到】
: 某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
: 很多，所以在bar raiser的强烈要求下，给了SDE3
avatar
s*l
55 楼
你第一题用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的工作又有点问题，
avatar
s*s
56 楼
这个思路的确不错。 想了一下，可以反证，用cut-paste来证明第一次dfs的结果为最
长路径的端点。

【在 s********s 的大作中提到】
:
: gate是在？Amazon?
avatar
f*m
57 楼
感觉可以用类似于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的工作又有点问题，
avatar
l*a
58 楼
金融界的VP顶多是个小lead,甚至很多时候没有report
就算个Sr software engineer?

【在 s********l 的大作中提到】
: VP? 为什么他要转行做sde啊？
avatar
w*x
60 楼
等等，这题的最大路径不考虑权值把，那递归不久出来了？
avatar
f*m
61 楼
可以考虑所有节点相同的权值，所以sum为节点的个数。

【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
avatar
f*t
62 楼
这题还好吧，代码很简单：
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;
}
avatar
f*m
63 楼
这个思路和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;
: }
avatar
c*t
64 楼
思路差不多吧。
不过有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;
: }
avatar
c*t
65 楼
欢迎回来啊！
我也没明白为啥就变复杂了。

【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
avatar
f*m
66 楼
rp不行，呵呵。

or

【在 c********t 的大作中提到】
: 思路差不多吧。
: 不过有bug, maxPath = Math.max(left+right+2, maxPath);而且事先还要判断left or
: right是不是 0, 有0就不是left+right+2了，要分情况处理了。
: 还有哦，题目没说是二叉树。
: ls那些人为啥不赞同你啊？
avatar
x*0
67 楼
mark
avatar
s*s
68 楼
前天收到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) 像这次面我的两个人在出题之前都说了句，要是题目我碰到过的话就和他们说，他
们可以换一个题目。那是不是每次碰到做过的题目，是不是实际中都是都要老实交代呢
，还是可以慢慢讲思路？
avatar
p*2
69 楼
longest path前不久讨论过。没见过不太容易写好。
UW or UT? 其实题目见过能写好也不容易。
avatar
s*s
70 楼

longest path我到时也去搜过，但是好多solution,有的也没看懂，大神给点思路？

【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
avatar
l*b
71 楼
longest path怎么定义的啊？tree里面任何2个node之间的距离？
avatar
s*s
72 楼

恩，对的，就是这个意思。

【在 l**b 的大作中提到】
: longest path怎么定义的啊？tree里面任何2个node之间的距离？
avatar
p*2
73 楼

你这个path是可以任意点开始，任意点结束吧？

【在 s********s 的大作中提到】
:
: 恩，对的，就是这个意思。
avatar
s*s
74 楼

嗯，其实就是要求出任意两点之间的距离最长的那个吧

【在 p*****2 的大作中提到】
:
: 你这个path是可以任意点开始，任意点结束吧？
avatar
l*b
75 楼
那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？

【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
avatar
p*2
76 楼

老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
）。
然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）

【在 s********s 的大作中提到】
:
: 嗯，其实就是要求出任意两点之间的距离最长的那个吧
avatar
l*b
77 楼
BTW，赞面经，bless你快点找到工作。
1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。
avatar
s*s
78 楼

然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
（负数要多考虑一些）
这个某一节点是哪个节点？

【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
avatar
d*x
79 楼
leetcode真是啥都有啊。
这是我当年在国内被G灭的面试题。。。
我对G的心理阴影是无穷大。。。

【在 l**b 的大作中提到】
: 那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
avatar
s*s
80 楼

Thanks 啦！ :)
那我觉得是不是可以套用leetcode上面的Binary Tree Max Path Sum的思路啊？
还没刷到这个题的说>_
【在 l**b 的大作中提到】
: BTW，赞面经，bless你快点找到工作。
: 1）越快有工作越好，这个是肯定的，H1-B什么的有工作了都好说。
avatar
l*a
81 楼
你上次就问人家学校，这次又问

【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
avatar
l*a
82 楼
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的工作又有点问题，
avatar
s*s
83 楼

大神也在加拿大的么？这个找工作的规划求建议啊！！

【在 p*****2 的大作中提到】
: longest path前不久讨论过。没见过不太容易写好。
: UW or UT? 其实题目见过能写好也不容易。
avatar
g*e
84 楼
longest path难道不是肯定由两个leaf node组成的？

【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
avatar
s*s
85 楼

多谢多谢！！
你上次就问人家学校，这次又问
哈哈，恩恩,上次新人报道的时候其实就被问过了>_<

【在 l*****a 的大作中提到】
: bless
: 打算吧你的2个面经存下来以后慢慢看
:
: 路？
avatar
s*s
86 楼

对，这个后来我也想了想，应该是这样子的

【在 g**e 的大作中提到】
: longest path难道不是肯定由两个leaf node组成的？
avatar
c*a
87 楼
练一下 不知道对不对
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;
}
avatar
l*a
88 楼
你说的比他问的难多了
他那个不需要care结点的值

【在 p*****2 的大作中提到】
:
: 老算法。用dfs，返回从输入节点开始的子树的最长路径 （输入节点到子树的任意节点
: ）。
: 然后对某一节点的所有孩子做这个操作。最长的发生就是两个最长的子树＋节点本身。
: （负数要多考虑一些）
avatar
g*e
89 楼
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;
: }
avatar
s*s
90 楼

嗯，我这个是没权值的，大神给个简单易懂的思路? :P

【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
avatar
c*s
91 楼
树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
avatar
s*s
92 楼

这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？

【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
avatar
f*7
93 楼
显然是用divide-and-conquer求diameter
最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
二叉树可以用modified post-order做，因为后序遍历的实质就是分治
n-ary tree，可以用两次BFS，证明很难，搜一下就有了
avatar
l*a
94 楼
最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
3种可能性递归

【在 s********s 的大作中提到】
:
: 这个思路倒是简单而且清晰，只是怎么解释一下这样子为什么一定是最长呢？
avatar
g*e
95 楼
正解
这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
他们is_bst

【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
avatar
l*a
96 楼
你把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;
: }
avatar
c*a
97 楼
测试了下,是4
对不对

【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
avatar
g*e
98 楼
显然不对啊，longest path明明是5

【在 c*****a 的大作中提到】
: 测试了下,是4
: 对不对
avatar
c*a
99 楼
maximum sum of bst那种?

【在 l*****a 的大作中提到】
: 你把path跟深度混淆了
avatar
c*a
100 楼
哦，我以为是算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
avatar
s*s
101 楼

这个很make sense！！

【在 l*****a 的大作中提到】
: 最大路径可能在左子树，也可能在右子树，或者两子树最深结点（通过root)
: 3种可能性递归
avatar
s*s
102 楼

is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？

【在 g**e 的大作中提到】
: 正解
: 这个题我也尝试着Onsite的时候问几个哥们，完全没有clue。我后来还是老老实实的问
: 他们is_bst
avatar
l*i
103 楼
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; ipair 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);
}
avatar
g*e
104 楼
银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
化一般就都挂了。
唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
当然,人家把我们的offer据了

【在 s********s 的大作中提到】
:
: is_bst是让判断是不是bianry search tree?也是一个递归进行判断吧？
avatar
d*x
105 楼
两次bfs没什么难的啊
我记得是反证法解决
找个高中小孩来证肯定三下五除二就出来了

【在 f*****7 的大作中提到】
: 显然是用divide-and-conquer求diameter
: 最远的两个点一定是叶子，否则cut-and-paste，我们总能找到更长的
: 二叉树可以用modified post-order做，因为后序遍历的实质就是分治
: n-ary tree，可以用两次BFS，证明很难，搜一下就有了
avatar
l*a
106 楼

用的是MAX_VALUE/MIN_VALUE那种解法？
嫌你们给的少？

【在 g**e 的大作中提到】
: 银行来的哥们一般是in order traverse然后判断是不是单调递增，再补问一句如何优
: 化一般就都挂了。
: 唯一一个用递归解出来的哥们不知道什么是BST，我给他举了几个例子他就写出来了。
: 当然,人家把我们的offer据了
avatar
g*e
107 楼
面SDE2，给的SDE3，应该还不错吧
这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
水平相当高

何优
了。

【在 l*****a 的大作中提到】
:
: 用的是MAX_VALUE/MIN_VALUE那种解法？
: 嫌你们给的少？
avatar
l*a
108 楼
这牛人哪国的？原来什么厂
估计半路出家，但是很聪明

【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
avatar
s*s
109 楼

gate是在？Amazon?

【在 g**e 的大作中提到】
: 面SDE2，给的SDE3，应该还不错吧
: 这哥们比较奇葩，不知道什么是BST，Heap。但是告诉他概念以后很快就能写出答案。
: 水平相当高
:
: 何优
: 了。
avatar
g*e
110 楼
某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
很多，所以在bar raiser的强烈要求下，给了SDE3

【在 l*****a 的大作中提到】
: 这牛人哪国的？原来什么厂
: 估计半路出家，但是很聪明
avatar
p*2
111 楼

那就相当于每个节点的值都是1吧。

【在 l*****a 的大作中提到】
: 你说的比他问的难多了
: 他那个不需要care结点的值
avatar
p*2
112 楼

没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？

【在 c**s 的大作中提到】
: 树里longest path是个经典问题，经典解法是两次dfs。第一次dfs记录最深那个节点。
: 第二次从这个节点出发再dfs到最深的那个节点，这两个节点的距离最长。
avatar
l*b
113 楼
tree 有parent指针哪里都可以当root吧。嗯
或者有第一次搜索得到的路径也够用了

【在 p*****2 的大作中提到】
:
: 没看明白，第二次dfs怎么搞？第一次找到的是叶子吧？怎么从这个开始dfs呢？
avatar
p*2
114 楼

题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。

【在 l*******b 的大作中提到】
: tree 有parent指针哪里都可以当root吧。嗯
: 或者有第一次搜索得到的路径也够用了
avatar
h*e
115 楼
拎兩次樹那道題。。
avatar
l*b
116 楼
想起来感觉还行，第一次的存在一个stack里，总是先搜child，需要朝parent方向搜索
的时候pop出来填到现在搜索的路径里就好了

【在 p*****2 的大作中提到】
:
: 题目没说有parent吧？把路径存下来的话，coding感觉也没有简单吧。
avatar
s*l
117 楼
VP? 为什么他要转行做sde啊？

【在 g**e 的大作中提到】
: 某英国银行VP，之前在IBM。确实如你所说，非常聪明，而且大规模分布式计算的经验
: 很多，所以在bar raiser的强烈要求下，给了SDE3
avatar
s*l
118 楼
你第一题用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的工作又有点问题，
avatar
s*s
119 楼
这个思路的确不错。 想了一下，可以反证，用cut-paste来证明第一次dfs的结果为最
长路径的端点。

【在 s********s 的大作中提到】
:
: gate是在？Amazon?
avatar
f*m
120 楼
感觉可以用类似于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的工作又有点问题，
avatar
l*a
121 楼
金融界的VP顶多是个小lead,甚至很多时候没有report
就算个Sr software engineer?

【在 s********l 的大作中提到】
: VP? 为什么他要转行做sde啊？
avatar
w*x
123 楼
等等，这题的最大路径不考虑权值把，那递归不久出来了？
avatar
f*m
124 楼
可以考虑所有节点相同的权值，所以sum为节点的个数。

【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
avatar
f*t
125 楼
这题还好吧，代码很简单：
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;
}
avatar
f*m
126 楼
这个思路和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;
: }
avatar
c*t
127 楼
思路差不多吧。
不过有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;
: }
avatar
c*t
128 楼
欢迎回来啊！
我也没明白为啥就变复杂了。

【在 w****x 的大作中提到】
: 等等，这题的最大路径不考虑权值把，那递归不久出来了？
avatar
f*m
129 楼
rp不行，呵呵。

or

【在 c********t 的大作中提到】
: 思路差不多吧。
: 不过有bug, maxPath = Math.max(left+right+2, maxPath);而且事先还要判断left or
: right是不是 0, 有0就不是left+right+2了，要分情况处理了。
: 还有哦，题目没说是二叉树。
: ls那些人为啥不赞同你啊？
avatar
x*0
130 楼
mark
avatar
j*x
131 楼
楼主可惜了
avatar
b*g
132 楼
同问第二个问题。。
avatar
s*y
133 楼
H1B是个问题
avatar
j*g
134 楼
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.
avatar
s*x
135 楼
抛砖引玉写了一个哈
// 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的工作又有点问题，
avatar
p*2
136 楼

没说一定是从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;
avatar
s*x
137 楼
对的，在recursion中的某个root，即longestPath可以经过任意node

【在 p*****2 的大作中提到】
:
: 没说一定是从root开始吧？
avatar
r*c
138 楼
给两个不同算法吧，就不写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)
avatar
p*2
139 楼

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)
avatar
s*x
140 楼
我的思路基本上就是二叉树的变种罢了。我写的code就是楼上说的思路

【在 p*****2 的大作中提到】
:
: observation
: of
: 没说是二叉树吧？
avatar
x*i
141 楼
跟那个二叉树最大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的工作又有点问题，
avatar
p*2
142 楼

应该比那个还简单一点

【在 x*******i 的大作中提到】
: 跟那个二叉树最大path sum思路差不多吧。
: 递归所有子树，每个返回两个值（包括根节点的最长路径 a_i， 所有的最长路径b_i）
: ，然后把这些值归总来算当前的两个值( max(a_i)+1, max(all b_i's ， 1+最大的两
: 个a_i))
:
: 路？
avatar
h*o
143 楼
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的工作又有点问题，
avatar
h*o
144 楼
贴一个多子的代码。请指正
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);
}
avatar
w*g
145 楼

路？
请问第一题你是直接实现一个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的工作又有点问题，
avatar
s*x
146 楼
那我写一下吧
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实现的哦。
avatar
w*g
147 楼
多谢。我是问遇到merge k 个 sorted list这道题，一共就15到20分钟时间，真的够时
间先写一个heap再写主程序么？
avatar
s*x
148 楼
trickleDown 和 removeHeapRoot 可以不用实现，先空在那里。
本来就是可以写pseudo code的。所以主要代码也就25行。

【在 w******g 的大作中提到】
: 多谢。我是问遇到merge k 个 sorted list这道题，一共就15到20分钟时间，真的够时
: 间先写一个heap再写主程序么？
avatar
c*p
149 楼
mark
相关阅读
这个版好歹是学术版可否lobby trump的老婆？ (转载)象棋名局：你行你上啊每年大选前后，美帝的离婚率有多大变化？Trump今年最想删除的视频终于新鲜出炉了 (转载)复旦大学国际关系学院老师曾庆捷 (转载)愚公今年有一件亮眼事可能大家都没注意，就是透明提词板川普总统忙碌的白宫第一天臭笑话：麻麻这几日比较犯愁来扒一扒Trump的政见itunes真是烦人啊快来看看左派的丑态,白牛脱裤子。 (转载)董大小姐被格力罢免了，可惜了一个人才 (转载)除了加独，以前还有一个加分方案。老公的幽默 zzRe: 你们真不知道一万卡在国内有多红！ (转载)希拉里遛狗和薄西王喂鱼有异曲同工之意，看来 (转载)马喇主帅：我们就是罗马生死追逐， 小蜥蜴对群蛇 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。