FB家电面面经

find the interection of tw

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

t be linear time

楼上有人说对了，就是iterator的变型嘛。。虽然面试官可能表述不清楚。但是不用递归是肯定的，也不能把全部节点都保存出来，这样耗费O(n)的复杂度。
1、因为是BST，所以迅速想到中序遍历是有序的，所以可以从两个树分别各自最左边开始比较。那么就是implement 一个 BST的iterator。
2、鉴于面试官说可以用栈，那么这个题目的额外空间复杂度应该是O(h)是树的高度。

3、如果不想用栈，可以利用parent节点，实现和栈一样的功能。

4、楼主已经说了，是找到同时出现的数啊，所以不是指结构上的交叉。

所以本题考察：中序遍历的非递归实现 + find intersection of two array 如果基础扎实10min应该可以码完。
同样出现的facebook面试为：here 以及 there
以下贴出代码：（用stack，O(h)额外空间）

1. public class BSTIterator {
   
2.     private Stack<TreeNode> stack = new Stack<TreeNode>();
   
3.    
   
4.     public BSTIterator(TreeNode root) {
   
5.         pushAllLeft(root);  
   
6.     }
   
7. 
   
8.     /** @return whether we have a next smallest number */
   
9.     public boolean hasNext() {
   
10.         return !stack.empty();
    
11.     }
    
12. 
    
13.     /** @return the next smallest number */
    
14.     public int next() {
    
15.         TreeNode node = stack.pop();
    
16.         pushAllLeft(node.right);
    
17.         
    
18.         return node.val;
    
19.     }
    
20.    
    
21.     public int min() {
    
22.         if (!stack.empty()) {
    
23.             return stack.peek();
    
24.         }
    
25.     }
    
26.    
    
27.     private void pushAllLeft(TreeNode root) {
    
28.         TreeNode head = root;
    
29.         while (head != null) {
    
30.             stack.push(head);
    
31.             head = head.left;
    
32.         }
    
33.     }
    
34. }
    
35. 
    
36. public class Solution {
    
37.     public ArrayList<TreeNode> findIntersectionInTwoBST
    
38.       (TreeNode rootA, TreeNode rootB) {
    
39.         if (rootA == null || rootB == null) {
    
40.             return null;
    
41.         }
    
42.         BSTIterator ia = new BSTIterator(rootA);
    
43.         BSTIterator ib = new BSTIterator(rootB);
    
44.         ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
    
45.         while (ia.hasNext() && ib.hasNext()) {
    
46.             if (ia.min().val == ib.min().val) {
    
47.                 ans.add(ia.next());
    
48.             } else if (ia.min().val < ib.min().val) {
    
49.                 ia.next();
    
50.             } else {
    
51.                 ib.next();
    
52.             }
    
53.         }
    
54.         
    
55.         return ans;
    
56.     }
    
57. }

复制代码

感觉是写BST的inorder iterator.
这样就变成intersection of two sequences了.

No extra space  不可能吧，起码要log(n)

wondermu 发表于 2014-5-10 02:52
No extra space  不可能吧，起码要log(n)

可以用Morris Traversal， 就是O(1)了

补充内容 (2014-5-10 03:35):
楼主最后有做出来吗？

是不是先flatten BST to linkedlist(这个也不用额外开辟新的list内存)，然后你比较两个list的相交部分

挂了，应该是个华裔哥。我一开始说了2种有extra space的方法，他不让我写，问我有没有不需要extra space的。然后我说recursion行不行,他说好吧。结果头脑一片混乱写不出来。。最后我问他怎么做，他说tree 可以有parent pointer，我说X，这也行？ 然后他说可以用stack，我说这不也是extra吗？然后就超时拜拜了。。

efny 发表于 2014-5-10 05:16
挂了，应该是个华裔哥。我一开始说了2种有extra space的方法，他不让我写，问我有没有不需要extra space的 ...

我只要是华裔面我没有不挂的。。。patpat楼主，继续加油！

stack不是extra space？？？。。。另外O（1）space是不是就是没用extra space？

sj1456 发表于 2014-5-19 11:31
stack不是extra space？？？。。。另外O（1）space是不是就是没用extra space？

no extra space  = in place ??

不过只要说出 O 1 一般都是 M

两个BST同时in order tranverse 像find intersection for array一样 可以返回intersection么 O(n) no extra space.

shire1989 发表于 2014-5-10 03:52
是不是先flatten BST to linkedlist(这个也不用额外开辟新的list内存)，然后你比较两个list的相交部分

flatten转化之后的linkedlist是前序遍历的，除了个别情况，list是乱序的，要求相交，复杂度很高。