S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 00:42:48 2011, 美东) 提到:
找 二叉树 两个最大的相同子树
没答上来。
见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
☆─────────────────────────────────────☆
boohockey (Pursuit of Dreams!) 于 (Thu Apr 7 10:27:03 2011, 美东) 提到:
bless
这道题有没有正解
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr 7 11:21:39 2011, 美东) 提到:
Why? there is O(n) algo. O(n) space and O(n) time.
but anyway, bless lz.
☆─────────────────────────────────────☆
Chevy (Chevy) 于 (Thu Apr 7 11:58:13 2011, 美东) 提到:
稍微详细说一下？
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr 7 12:25:56 2011, 美东) 提到:
Mark nodes from leaves(height from 0) based on left/right node. and put
into hashmap.
hashmap : (left_node_marked_value,right_node_marked_value) ->
marked_value
marked_value = 0 ;
if ( (left_node.marked_value,right_node.marked_value) is not in the map)
{
map[(left_node_marked_value,right_node_marked_value)] =
marked_value++;
}
current_node.marled_value =
map[(left_node_marked_value,right_node_marked_value);
BTW:
A subtree of a tree T is a tree consisting of a node in T and all of its
descendants in T.
☆─────────────────────────────────────☆
Chevy (Chevy) 于 (Thu Apr 7 12:32:45 2011, 美东) 提到:
谢谢！
先mark一下，晚上回去仔细研究一下
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 12:38:28 2011, 美东) 提到:
so after you build up a hash map like this, how do you give the maximum
sub-tree?
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr 7 13:06:43 2011, 美东) 提到:
Go through from leaves, find two max_depth nodes with same marked
values.
It can be done when we build it. Just change a little. (use map point
the first node)
if ( (left_node.marked_value,right_node.marked_value) is not in the map)
{
map[(left_node_marked_value,right_node_marked_value)] = current_node;
} else {
result = (current_node's subtree ,
map[(left_node_marked_value,right_node_marked_value)]'s subtree);
}
current_node.marled_value =
map[(left_node_marked_value,right_node_marked_value);
maximum
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 13:14:54 2011, 美东) 提到:
sorry, the problem is given two bt's and find the maximum identical sub-tree of
these two, or given one bt and find the maximum sub-tree in this bt?
☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 15:53:07 2011, 美东) 提到:
给一个二叉数，找这个树中两个相同子树，并且使它们是最大的相同子树， 意思是没
有两个相同子树size比它们更大。
tree of
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 15:56:04 2011, 美东) 提到:
so have u gotten grass' idea? i don't get it yet.
☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 16:24:45 2011, 美东) 提到:
I did not get it either. I did not see any comparation happened in glass's
alg. Could anybody give a more clear explanation? Is there other way to
solve it?
☆─────────────────────────────────────☆
orzgod (offer) 于 (Thu Apr 7 16:31:55 2011, 美东) 提到:
大致是说
如果左右子树一样 那么这棵树一样
用map就可以查到之前是否已经有同样子树的树
有的话就发现同样的子树
没有就插入
直到把每个节点都遍历 返回最大的那个就是了
☆─────────────────────────────────────☆
orzgod (offer) 于 (Thu Apr 7 16:37:02 2011, 美东) 提到:
那个算法中的比较就是发生在
map插入的时候
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 16:39:50 2011, 美东) 提到:
要求树结构一样，怎么用一个字数属性的比较来表示？
☆─────────────────────────────────────☆
hsp0221 (none) 于 (Thu Apr 7 17:04:20 2011, 美东) 提到:
how about this:
in-order traversal to get a string. then use suffix tree to find the two
identical strings. it is O(n) time and O(n) space.
☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 17:12:21 2011, 美东) 提到:
刚刚打了一下瞌睡，居然来了点灵感， 这不是类似于求两个最大的substring吗？ 我
怎么那么蠢呢？
☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 17:16:05 2011, 美东) 提到:
inorder遍历，
求两个最长的相同子串
☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 17:17:34 2011, 美东) 提到:
楼上已经有人想到了
☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 17:22:39 2011, 美东) 提到:
老兄眼快脑快
☆─────────────────────────────────────☆
hsp0221 (none) 于 (Thu Apr 7 17:26:23 2011, 美东) 提到:
唉，一个onsite 也没拿到。
☆─────────────────────────────────────☆
gululu00 (咕噜噜) 于 (Thu Apr 7 17:29:53 2011, 美东) 提到:
I am sorry, I don't quite understand what the problem is:
Given a binary Search Tree, find two biggest same subtrees.???
二叉树 是 binary search tree, or binary tree?
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 17:36:09 2011, 美东) 提到:
i don't think this is right.
here the question is the structure isophormism, not the data the same.
for example, the tree could have all node data 1. then the tree is 1111111..
. after travesal. the structure info is lost.
☆─────────────────────────────────────☆
orzgod (offer) 于 (Thu Apr 7 17:47:53 2011, 美东) 提到:
agree
..
☆─────────────────────────────────────☆
gululu00 (咕噜噜) 于 (Thu Apr 7 17:54:10 2011, 美东) 提到:
那么多人在讨论问题，为什么没有人回我啊？可不可以把题么说说清楚？或是翻译to
English?
☆─────────────────────────────────────☆
hsp0221 (none) 于 (Thu Apr 7 18:14:33 2011, 美东) 提到:
大家都明白阿。不知还要怎么解释。
☆─────────────────────────────────────☆
orzgod (offer) 于 (Thu Apr 7 18:41:29 2011, 美东) 提到:
二叉树 是 binary tree
binary search tree 是 二叉查找树
题目就是你说的那个意思
这里的一样指的是结构上一样
☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 19:14:05 2011, 美东) 提到:
楼上有道理， 最大substring是必要条件不是充分条件
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Thu Apr 7 19:32:25 2011, 美东) 提到:
你怎么保证你找到的最大两个子串的头尾都是leaf
除非你在每个node那里加多一个变量mark是不是leaf
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr 7 20:07:31 2011, 美东) 提到:
解释一下我的算法：
所有两个节点，如果以它为根的树相同，就mark成相同的元素（或数字）
所有两个节点，如果它们的左子树和右子树都被mark成相同了，那么这两个节点也认为
相同。
例如，所有的叶节点，都相同。我们mark成0
然后，看depth=1的节点。如果（left,right)=(0，NULL)的节点mark成1 （NULL，0）
的mark成2
再看depth=3的。。。一直递推到root
有点像DP。
改进的算法，就是不用0,1,2,3..来mark，而是用满足的第一个点来mark。这样，第二
个相同的点就可以和第一个点构成相同子树。
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 21:02:32 2011, 美东) 提到:
明白你的思路了。不过这个改进是什么？
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr 7 21:07:41 2011, 美东) 提到:
原始算法在5楼（用数字mark）。改进的在8楼（用第一个满足的node mark）
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 21:07:59 2011, 美东) 提到:
感觉这个解法还是有问题。你这个编码最后的范围是什么？
假设n节点的二叉树有f(n)个，对每个不同子树，编码是sum(f(n-k)) + i，k = 1..n-1 ，i = 1..f(n)？如果是这样的话，编码最后可能变的很大啊。
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr 7 21:09:49 2011, 美东) 提到:
还是没明白啊。
这个是染色的思路。不是编码。
-1 ，i =
1..f(n)？如果是这样的话，编码最后可能变的很大啊。
☆─────────────────────────────────────☆
xiaoxing (燕麦) 于 (Thu Apr 7 21:09:58 2011, 美东) 提到:
请问叶子节点为啥都是0，不用考虑他们本身的值嘛？
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr 7 21:11:56 2011, 美东) 提到:
我的理解是只考虑树的形状。
两个子树有所有对应的点。
☆─────────────────────────────────────☆
gandjmitbbs (Nothing) 于 (Thu Apr 7 21:16:14 2011, 美东) 提到:
这么说吧。假设左子树拿到p，右子树拿到q，那根的编码是什么？
递归表达式：
c(r) = 0 if r->left == r->right == NULL;
c(r) = 1 if r->left != NULL && c(r->left) && r->right == NULL;
c(r) = 2 if r->left == NULL && r->right != NULL && c(r->right) == 0
otherwise, c(r) = f(c(r->left), c(r->right)).
but what is f(m, n) here?
☆─────────────────────────────────────☆
xiaoxing (燕麦) 于 (Thu Apr 7 21:16:44 2011, 美东) 提到:
明白啦
☆─────────────────────────────────────☆
xiaoxing (燕麦) 于 (Thu Apr 7 21:19:18 2011, 美东) 提到:
你想的太复杂了
画两棵树
从叶子节点一层层上去写出来
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Fri Apr 8 06:47:14 2011, 美东) 提到:
这里的相同是结构相同吗?
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Fri Apr 8 10:18:26 2011, 美东) 提到:
if the value of the node needs to be considered, we only need to change a
little in the algo.
same time/space complexity.
☆─────────────────────────────────────☆
cqer (重庆滴) 于 (Fri Apr 8 11:16:20 2011, 美东) 提到:
Mark
industry
recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求
祝福！
☆─────────────────────────────────────☆
qxc (法界闲人) 于 (Fri Jun 3 00:24:58 2011, 美东) 提到:
而且这个 substring 不能保证在一个node 下面， 这就土了。
我一开始也准备这么干来着。
1111111
☆─────────────────────────────────────☆
mercuriusl2 (Mercurius) 于 (Fri Jun 3 01:19:15 2011, 美东) 提到:
见了四个？
还是先别就面试吧。 延迟一个或两个月， 回家苦读书
MS最少三个。 要见七个才算成功 （还不是100%）
第三个那个对你不满意， 第四个也不满意
industry
recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求
祝福！
☆─────────────────────────────────────☆
philmia (小屁孩) 于 (Fri Jun 3 20:03:57 2011, 美东) 提到:
Go through from leaves, find two max_depth nodes with same marked
values.
It can be done when we build it. Just change a little. (use map point
the first node)
if ( (left_node.marked_value,right_node.marked_value) is not in the map)
{
map[(left_node_marked_value,right_node_marked_value)] = current_node;
} else {
result = (current_node's subtree ,
map[(left_node_marked_value,right_node_marked_value)]'s subtree);
}
current_node.marled_value =
map[(left_node_marked_value,right_node_marked_value);
~~~~~~~~~~~~~~~~~~~~~有点搞糊涂了，节点的marked_value = 一个节点？如果一个新
节点的子树与另一个节点的子树相同，他们的(left_node.marked_value,right_node.
marked_value) 也不应该相同吧？那你怎么前面用if ( (left_node.marked_value,
right_node.marked_value) is not in the map) 来做判断？
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Fri Jun 3 21:12:33 2011, 美东) 提到:
相同。请再仔细领会一下大牛代码的精神
☆─────────────────────────────────────☆
gepolv (gepolv) 于 (Fri Jun 3 23:34:01 2011, 美东) 提到:
为什么inorder，pre-order and post-order不行么？
☆─────────────────────────────────────☆
philmia (小屁孩) 于 (Sun Jun 5 03:59:08 2011, 美东) 提到:
got it.
Thanks.
☆─────────────────────────────────────☆
searchlyf (星仔) 于 (Fri Oct 21 16:23:25 2011, 美东) 提到:
no good idea,but:
preorder and inorder can uniquely define a btree, let me begin with here.
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！ | b*********6
发帖数: 19 | 2 我觉得如果inorder和preorder的方法是可行的，我们只要在叶子节点的下面指向NULL
的用特殊的符号表示一下，比如-1，然后把这个也存到数组中去，这样比较的话，结构
信息也被保存了。 | h********w
发帖数: 221 | 3 支持，traversal and find max substring if the tree is BST,
Mark, 我得想想grass的solution |
|
