NSC真tmd慢呀 - 未名空间MITBBS历史存档

s*n2013-02-20 08:02

1 楼

今天看到一道面试题，想不出很好的解法，请大牛们过过目，指点下，哈哈。
给定一个二叉树，所有的节点值（包括中间，叶子节点）有可能重复，题目要求找出所
有的没有重复节点的子树（包括叶子节点，这个算作一个节点的子树）。
e.g.
3
2 4
1 5 7 2
总共有6个这样的子树，即除了3之外，所有的节点所对应的子树都符合要求。

u*r2013-02-20 08:02

2 楼

发信人： friendshi(朋朋), 信区： Parenting
标题：你能够自己的孩子很平庸吗？
发信站： BBS未名空间站(Fri Oct 13 08:04:30 2017,GMT)
曾经在网上看到这样一个问题：“部分家长是否很难接受自家小孩的平庸？”点进去一
看，而排名最高的答案是一位妈妈写的。她有一儿一女，在儿子学游泳时，她告诉教练
，开心就好，学不学得会都没有关系。
结果玩了两天后，第三天儿子在教练的高压教学下学会了游泳，并且非常高兴和自豪。
她明显感到与纯粹玩乐相比，儿子更喜欢这种“征服困难获得前行的成就感”。
反观正在上幼儿园的女儿，与儿子完全不同。女儿“在偷懒的时候是发自内心的快乐，
和哥哥亲亲抱抱的时候是发自内心的快乐，上体操课单杠做的不好老师说那就去玩平衡
木不用继续练习时，她也是发自内心的快乐。”
相应地，在教育上，她和先生会告诉儿子做每一件事都要全力以赴，“可以不成功，但
一定要足够有效，足够努力”。但对女儿则降低期待值，开心就好。
刚读完时觉得她的观点很不错，每个人的成就动机的确是不一样的，成就动机高的人就
去追求卓越的人生，成就动机低的人就呆在舒适区，安于现状也没什么不好，关键是父
母要尊重并接受。
心理学里经常讲要接纳孩子，是不是“接纳孩子成就动机不高”这一项也应包含在内？

L*S2013-02-20 08:02

3 楼

我们招谁惹谁了呀？
本来NSC的EB1就比TSC难一点。
结果到了485更是慢的离谱。TSC11月基本都绿了吧。
NSC基本没见到什么行动！
靠！

c*62013-02-20 08:02

4 楼

不是大牛，来个naive的方法吧：
后续遍历二叉树，
建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
放到哈希表里
节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
的set，
因为是post order所以可以保证左右孩子都算完了再算父节点，
复杂度n2

B*l2013-02-20 08:02

5 楼

最可悲的就是把平庸的孩子当天才培养苦了孩子

u*e2013-02-20 08:02

6 楼

big bless,

s*n2013-02-20 08:02

7 楼

这个也是我想到的但是感觉树的题目应该有更好的解法哈哈

set
3

【在 c********6 的大作中提到】

: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
: 的set，
: 因为是post order所以可以保证左右孩子都算完了再算父节点，

I*r2013-02-20 08:02

8 楼

485要是也可以PP就好了。

l*82013-02-20 08:02

9 楼

nlogn time吧？

set
3

【在 c********6 的大作中提到】

: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
: 的set，
: 因为是post order所以可以保证左右孩子都算完了再算父节点，

s*u2013-02-20 08:02

10 楼

以前真不知道这回事啊，硬从ＴＳＣ区跑到了ＮＳＣ区，唉。
谁让ＮＳＣ还管批广大难民申请呢。
从发ＦＰ通知到ＥＡＤ批直到最后485批准，哪一步不比ＴＳＣ的平均速度要慢啊。本
来ＦＢＩ就慢，ＮＳＣ还要拖后腿，ＦＢＩ好不容易审完了，这边ＩＯ还要接着多拖一
到两个月。真是ＦＴ！
命苦只能怨政府。
bless us all.

【在 L**S 的大作中提到】

: 我们招谁惹谁了呀？
: 本来NSC的EB1就比TSC难一点。
: 结果到了485更是慢的离谱。TSC11月基本都绿了吧。
: NSC基本没见到什么行动！
: 靠！

M*M2013-02-20 08:02

11 楼

类似找最大BST subtree， bottom up.
bool findsubtree(TreeNode *node, unordered_set &set, vector
&vec) {
if(not node) {
return true;
}
unordered_set leftset;
unordered_set rightset;
bool left = findsubtree(node->left, leftset, vec);
bool right = findsubtree(node->right, rightset, vec);
if(left&&right) {
//leftset and rightset overlap
for(auto ele:leftset) {
if(rightset.find(ele)!=rightset.end()) {
return false;
}
}
//leftset and rightset no overlap, check node is in the two sets
if(leftset.find(node->val)!=leftset.end()||rightset.find(node->val)!
=rightset.end()) {
return false;
} else {
set.insert(node->val);
set.insert(leftset.begin(), leftset.end());
set.insert(rightset.begin(), rightset.end());
vec.push_back(node);
return true;
}
} else {
return false;
}
}
vector find(TreeNode *node) {
vector vec;
unordered_set set;
findsubtree(node, set, vec);
return vec;
}

s*u2013-02-20 08:02

12 楼

good idea. may be expensive (to ask FBI to expedite name check)
bless us all

【在 I********r 的大作中提到】

: 485要是也可以PP就好了。

a*42013-02-20 08:02

13 楼

a java solution:
import java.util.*;
public class FindNonDupeSubTree {
private class Node{
int val;
Node left;
Node right;
Node (int val){
this.val = val;
left = null;
right = null;
}
}

public boolean FindSubTree(Node root, Set nodeSet, ArrayList<
Integer> validTreeRoots){
if (root == null)
return true;
Set sleft = new HashSet();
Set sright = new HashSet();

boolean left = FindSubTree(root.left, sleft, validTreeRoots);
boolean right = FindSubTree(root.right, sright, validTreeRoots);
if (left && right){
// both are valid, let's check if left and right has any
overlaps.
for (Integer i : sleft){
if (sright.contains(i))
return false;
}
}

// now there's no overlap between left tree and right tree, check
root is in any of them or not
if (sleft.contains(root.val) || sright.contains(root.val))
return false;

// everything checked out as unique, merge root into all sets, and
add root to the validtreeroots
validTreeRoots.add(root.val);
nodeSet.addAll(sright);
nodeSet.addAll(sleft);
nodeSet.add(root.val);

return true;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
FindNonDupeSubTree ft = new FindNonDupeSubTree();
Node root = ft.new Node(3);
Node temp = null;
temp = ft.new Node(2);
root.left = temp;
temp = ft.new Node(4);
root.right = temp;
temp = ft.new Node(1);
root.left.left = temp;
temp = ft.new Node(5);
root.left.right = temp;
temp = ft.new Node(7);
root.right.left = temp;
temp = ft.new Node(2);
root.right.right = temp;
Set s = new HashSet();
ArrayList v = new ArrayList();

ft.FindSubTree(root, s, v);
System.out.println(v.size());

}
}

*>

【在 M*****M 的大作中提到】

: 类似找最大BST subtree， bottom up.
: bool findsubtree(TreeNode *node, unordered_set &set, vector
: &vec) {
: if(not node) {
: return true;
: }
: unordered_set leftset;
: unordered_set rightset;
: bool left = findsubtree(node->left, leftset, vec);
: bool right = findsubtree(node->right, rightset, vec);

S*t2013-02-20 08:02

14 楼

自我安慰一下：
NSC不会抽风，稳中求进，心理踏实点。
TSC偶尔会抽风，个别CASE拖上一年多，碰上了这个概率就惨了。

s*n2013-02-20 08:02

15 楼

the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree.

I*r2013-02-20 08:02

16 楼

我看google doc上TSC11月以前的都绿了，也没有哪个被落下了，倒是NSC还有10月没绿
的。

s*n2013-02-20 08:02

17 楼

the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree.

L*S2013-02-20 08:02

18 楼

我也是不知道呀。
硬从TSC跑到了NSC，tnnd

【在 s*********u 的大作中提到】

: 以前真不知道这回事啊，硬从ＴＳＣ区跑到了ＮＳＣ区，唉。
: 谁让ＮＳＣ还管批广大难民申请呢。
: 从发ＦＰ通知到ＥＡＤ批直到最后485批准，哪一步不比ＴＳＣ的平均速度要慢啊。本
: 来ＦＢＩ就慢，ＮＳＣ还要拖后腿，ＦＢＩ好不容易审完了，这边ＩＯ还要接着多拖一
: 到两个月。真是ＦＴ！
: 命苦只能怨政府。
: bless us all.

a*42013-02-20 08:02

19 楼

nodeset will remove dups, but that won't really impact the result. as long
as there's one copy of the presented nodes in the set, it will serve the
purpose of prevent dupe when comparing two sets. the result is stored in the
arraylist, which will maintain dup as is.

【在 s****n 的大作中提到】

: the nodeset will remove the duplicated elements in the subtree, which will
: affect the decision for the parent tree.

s*u2013-02-20 08:02

20 楼

偶觉得ＴＳＣ抽风的原因是ＦＢＩ的背景调查没过。ＮＳＣ也同样会有这样的情况。如
果没有搞错，著名的大蜜同学就是在ＮＳＣ惨遭不幸的，现在好像还没有绿，（12年2
月的ＲＤ）。
觉得现在情况是，ＮＳＣ据说有大量的难民绿卡处理，分散了大量的人力，导致他们在
ＦＢＩ背景调查完了后，还不能及时处理，导致了至少一个月的集压。而ＴＳＣ则要好
不少，人力充足些，ＦＢＩ调查一完就能继续处理，所以有大量的30－40天甚至20多天
就批下的神速ＣＡＳＥ；而这个在ＮＳＣ是绝对不可能发生的事情！
现在能做的只能是pray，ＮＳＣ能稍微集中精力，尽快批485。不求神速，能在3个月平
均时间内批就感谢不尽了。
bless us ALL!

【在 S*******t 的大作中提到】

: 自我安慰一下：
: NSC不会抽风，稳中求进，心理踏实点。
: TSC偶尔会抽风，个别CASE拖上一年多，碰上了这个概率就惨了。

r*k2013-02-20 08:02

21 楼

就是你这个方法，很好的
一点都不navie

set
3

【在 c********6 的大作中提到】

: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
: 的set，
: 因为是post order所以可以保证左右孩子都算完了再算父节点，

s*u2013-02-20 08:02

22 楼

不过ＴＳＣ区的同学更新并不及时，据我知道的至少还有一位同学（ＩＤ忘了）在ＴＳ
Ｃ，记得是11月中的ＲＤ，还没有绿。
bless us all!

【在 I********r 的大作中提到】

: 我看google doc上TSC11月以前的都绿了，也没有哪个被落下了，倒是NSC还有10月没绿
: 的。

s*n2013-02-20 08:02

23 楼

今天看到一道面试题，想不出很好的解法，请大牛们过过目，指点下，哈哈。
给定一个二叉树，所有的节点值（包括中间，叶子节点）有可能重复，题目要求找出所
有的没有重复节点的子树（包括叶子节点，这个算作一个节点的子树）。
e.g.
3
2 4
1 5 7 2
总共有6个这样的子树，即除了3之外，所有的节点所对应的子树都符合要求。

n*o2013-02-20 08:02

24 楼

485能够PP吗？不能的话，怎么才能让他们快点呢？

c*62013-02-20 08:02

25 楼

不是大牛，来个naive的方法吧：
后续遍历二叉树，
建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
放到哈希表里
节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
的set，
因为是post order所以可以保证左右孩子都算完了再算父节点，
复杂度n2

J*n2013-02-20 08:02

26 楼

bless~

s*n2013-02-20 08:02

27 楼

这个也是我想到的但是感觉树的题目应该有更好的解法哈哈

set
3

【在 c********6 的大作中提到】

: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
: 的set，
: 因为是post order所以可以保证左右孩子都算完了再算父节点，

I*r2013-02-20 08:02

28 楼

如果真能PP就好了。只能干等，如果超过平均处理时间，可以催一下，具体方法看置
顶绿卡申请流程及细节。

l*82013-02-20 08:02

29 楼

nlogn time吧？

set
3

【在 c********6 的大作中提到】

: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
: 的set，
: 因为是post order所以可以保证左右孩子都算完了再算父节点，

A*n2013-02-20 08:02

30 楼

big bless

a*42013-02-20 08:02

31 楼

a java solution:
import java.util.*;
public class FindNonDupeSubTree {
private class Node{
int val;
Node left;
Node right;
Node (int val){
this.val = val;
left = null;
right = null;
}
}

public boolean FindSubTree(Node root, Set nodeSet, ArrayList<
Integer> validTreeRoots){
if (root == null)
return true;
Set sleft = new HashSet();
Set sright = new HashSet();

boolean left = FindSubTree(root.left, sleft, validTreeRoots);
boolean right = FindSubTree(root.right, sright, validTreeRoots);
if (left && right){
// both are valid, let's check if left and right has any
overlaps.
for (Integer i : sleft){
if (sright.contains(i))
return false;
}
}

// now there's no overlap between left tree and right tree, check
root is in any of them or not
if (sleft.contains(root.val) || sright.contains(root.val))
return false;

// everything checked out as unique, merge root into all sets, and
add root to the validtreeroots
validTreeRoots.add(root.val);
nodeSet.addAll(sright);
nodeSet.addAll(sleft);
nodeSet.add(root.val);

return true;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
FindNonDupeSubTree ft = new FindNonDupeSubTree();
Node root = ft.new Node(3);
Node temp = null;
temp = ft.new Node(2);
root.left = temp;
temp = ft.new Node(4);
root.right = temp;
temp = ft.new Node(1);
root.left.left = temp;
temp = ft.new Node(5);
root.left.right = temp;
temp = ft.new Node(7);
root.right.left = temp;
temp = ft.new Node(2);
root.right.right = temp;
Set s = new HashSet();
ArrayList v = new ArrayList();

ft.FindSubTree(root, s, v);
System.out.println(v.size());

}
}

*>

【在 M*****M 的大作中提到】

: 类似找最大BST subtree， bottom up.
: bool findsubtree(TreeNode *node, unordered_set &set, vector
: &vec) {
: if(not node) {
: return true;
: }
: unordered_set leftset;
: unordered_set rightset;
: bool left = findsubtree(node->left, leftset, vec);
: bool right = findsubtree(node->right, rightset, vec);

r*i2013-02-20 08:02

32 楼

我这几天等485才想起以前听说的NSC的几件事。有个欧洲的同事因为485一年多不下来
和LD两地分居两个国家，我当时还很奇怪，问他欧洲不是没有排期吗，为什么还这么慢
。当时他跟我抱怨了一通美国政府的办事效率。还有个同事也是一年多才收到approval
，另一个是两年半。如果是平均时间下来，我也没话说，就怕掉到黑洞里出不来了。都
是NSC的。

2

【在 s*********u 的大作中提到】

: 偶觉得ＴＳＣ抽风的原因是ＦＢＩ的背景调查没过。ＮＳＣ也同样会有这样的情况。如
: 果没有搞错，著名的大蜜同学就是在ＮＳＣ惨遭不幸的，现在好像还没有绿，（12年2
: 月的ＲＤ）。
: 觉得现在情况是，ＮＳＣ据说有大量的难民绿卡处理，分散了大量的人力，导致他们在
: ＦＢＩ背景调查完了后，还不能及时处理，导致了至少一个月的集压。而ＴＳＣ则要好
: 不少，人力充足些，ＦＢＩ调查一完就能继续处理，所以有大量的30－40天甚至20多天
: 就批下的神速ＣＡＳＥ；而这个在ＮＳＣ是绝对不可能发生的事情！
: 现在能做的只能是pray，ＮＳＣ能稍微集中精力，尽快批485。不求神速，能在3个月平
: 均时间内批就感谢不尽了。
: bless us ALL!

s*n2013-02-20 08:02

33 楼

the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree.

r*i2013-02-20 08:02

34 楼

等得我绿装都过期了，手上拿了根鞭子就是抽NSC的。

s*n2013-02-20 08:02

35 楼

the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree.

d*72013-02-20 08:02

36 楼

这鞭子看着真痛快。

【在 r**i 的大作中提到】

: 等得我绿装都过期了，手上拿了根鞭子就是抽NSC的。

a*42013-02-20 08:02

37 楼

nodeset will remove dups, but that won't really impact the result. as long
as there's one copy of the presented nodes in the set, it will serve the
purpose of prevent dupe when comparing two sets. the result is stored in the
arraylist, which will maintain dup as is.

【在 s****n 的大作中提到】

: the nodeset will remove the duplicated elements in the subtree, which will
: affect the decision for the parent tree.

L*S2013-02-20 08:02

38 楼

哈哈，要狠狠的抽

【在 r**i 的大作中提到】

: 等得我绿装都过期了，手上拿了根鞭子就是抽NSC的。

r*k2013-02-20 08:02

39 楼

就是你这个方法，很好的
一点都不navie

set
3

【在 c********6 的大作中提到】

: 不是大牛，来个naive的方法吧：
: 后续遍历二叉树，
: 建一个哈希表 key是root节点，value是这颗树的所有节点的值包括root，
: 没访问一个节点，看他左右子树哈希表值有没有重复，有的话就不符合，
: 然后再把左右子树的set merge 加上他自己作为这个节点的值放到哈希表里，
: 比如说节点4 左边是 7 右边是 2 没有重合，符合要求，然后把 4 2 7 座位一个set
: 放到哈希表里
: 节点3 左边 1 2 5 右边 4 7 2 有重合不符合要求，然后把3 1 2 5 4 7作为节点3
: 的set，
: 因为是post order所以可以保证左右孩子都算完了再算父节点，

B*R2013-02-20 08:02

40 楼

Blessing all

f*t2013-02-20 08:02

41 楼

bool UniqueBTrees(Node *root, vector &res, unordered_set &us) {
unordered_set lus;
unordered_set rus;
if ((!root->left || UniqueBTrees(root->left, res)) &&
(!root->right || UniqueBTrees(root->right, res)) &&
lus.find(root->val) == lus.end() &&
rus.find(root->val) == rus.end()) {
res.push_back(root);
for (int x : lus) {
us.insert(x);
}
for (int y : lus) {
us.insert(y);
}
us.insert(root->val);
return true;
} else {
return false;
}
}

B*R2013-02-20 08:02

42 楼

Blessing

s*e2013-02-20 08:02

43 楼

must be me
my is TSC, 11/2012, still ACCEPTANCE.

【在 s*********u 的大作中提到】

: 不过ＴＳＣ区的同学更新并不及时，据我知道的至少还有一位同学（ＩＤ忘了）在ＴＳ
: Ｃ，记得是11月中的ＲＤ，还没有绿。
: bless us all!

i*t2013-02-20 08:02

44 楼

NSC地处中西部民风淳朴大家节奏慢了点

f*g2013-02-20 08:02

45 楼

今天看到tsc一片报绿， 1月十几号收到的都绿了。
再看看nsc 每周寥寥。

s*u2013-02-20 08:02

46 楼

算自己倒霉，和广大难民绿卡分在一个中心处理。
大家交一样的钱，凭空在ＮＳＣ就要多等一个月甚至更长。只能怨政府。美国政府监管
不力；
中国政府如果不搞文革早搞经济，大家也很可能不用求爷爷告奶奶地在这边呆着。
发发牢骚，还是要
bless us ALL!!

【在 f*****g 的大作中提到】

: 今天看到tsc一片报绿， 1月十几号收到的都绿了。
: 再看看nsc 每周寥寥。

d*72013-02-20 08:02

47 楼

bless所有NSC的485 都能顺顺利利。

s*12013-02-20 08:02

48 楼

祝福nsc的xdjm早绿，包括我LG和我，嘿嘿嘿嘿。。。