一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2756|回复: 21
收起左侧

FB家电面面经

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
efny 发表于 2014-5-9 08:10:02 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽
北航小涵 发表于 2015-3-19 19:41:04 | 显示全部楼层
楼上有人说对了,就是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.     /** @return whether we have a next smallest number */
  8.     public boolean hasNext() {
  9.         return !stack.empty();
  10.     }

  11.     /** @return the next smallest number */. visit 1point3acres.com for more.
  12.     public int next() {
  13.         TreeNode node = stack.pop();
  14.         pushAllLeft(node.right);
  15.         
  16.         return node.val;
    . 1point 3acres 璁哄潧
  17.     }
  18.    
  19.     public int min() {. 1point 3acres 璁哄潧
  20.         if (!stack.empty()) {
  21.             return stack.peek();
  22.         }
  23.     }
  24.     . visit 1point3acres.com for more.
  25.     private void pushAllLeft(TreeNode root) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.         TreeNode head = root;
  27.         while (head != null) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.             stack.push(head);
  29.             head = head.left;
  30.         }
  31.     }
  32. }

  33. public class Solution {. 1point 3acres 璁哄潧
  34.     public ArrayList<TreeNode> findIntersectionInTwoBST-google 1point3acres
  35.       (TreeNode rootA, TreeNode rootB) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.         if (rootA == null || rootB == null) {
  37.             return null;
  38.         }
  39.         BSTIterator ia = new BSTIterator(rootA);. From 1point 3acres bbs
  40.         BSTIterator ib = new BSTIterator(rootB);
  41.         ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
  42.         while (ia.hasNext() && ib.hasNext()) {
  43.             if (ia.min().val == ib.min().val) {
  44.                 ans.add(ia.next());
  45.             } else if (ia.min().val < ib.min().val) {
  46.                 ia.next();
  47.             } else {
  48.                 ib.next();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  49.             }
  50.         }. from: 1point3acres.com/bbs
  51.         
  52.         return ans;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  53.     }
  54. }
复制代码

评分

3

查看全部评分

回复 支持 1 反对 0

使用道具 举报

NdrZmansN 发表于 2015-1-31 14:08:08 | 显示全部楼层
感觉是写BST的inorder iterator.
这样就变成intersection of two sequences了.
回复 支持 1 反对 0

使用道具 举报

wondermu 发表于 2014-5-10 02:52:37 | 显示全部楼层
No extra space  不可能吧,起码要log(n)
回复 支持 反对

使用道具 举报

discoveryi 发表于 2014-5-10 03:27:19 | 显示全部楼层
回复 支持 反对

使用道具 举报

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

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| efny 发表于 2014-5-10 05:16:16 来自手机 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

lucifermoon 发表于 2014-5-16 00:50:46 | 显示全部楼层
efny 发表于 2014-5-10 05:16
挂了,应该是个华裔哥。我一开始说了2种有extra space的方法,他不让我写,问我有没有不需要extra space的 ...

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 我只要是华裔面我没有不挂的。。。patpat楼主,继续加油!
回复 支持 反对

使用道具 举报

sj1456 发表于 2014-5-19 11:31:40 | 显示全部楼层
stack不是extra space???。。。另外O(1)space是不是就是没用extra space?
回复 支持 反对

使用道具 举报

readman 发表于 2014-5-19 13:16:50 | 显示全部楼层
sj1456 发表于 2014-5-19 11:31. 1point3acres.com/bbs
stack不是extra space???。。。另外O(1)space是不是就是没用extra space?

no extra space  = in place ??
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不过只要说出 O 1 一般都是 M
回复 支持 反对

使用道具 举报

guruimage 发表于 2014-6-5 01:30:35 | 显示全部楼层
两个BST同时in order tranverse 像find intersection for array一样 可以返回intersection么 O(n) no extra space.
回复 支持 反对

使用道具 举报

Neal_kks 发表于 2014-11-26 14:50:01 | 显示全部楼层
shire1989 发表于 2014-5-10 03:52. 1point3acres.com/bbs
是不是先flatten BST to linkedlist(这个也不用额外开辟新的list内存),然后你比较两个list的相交部分

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

使用道具 举报

averillzheng 发表于 2014-11-26 23:52:46 | 显示全部楼层
morris in-order traversal
回复 支持 反对

使用道具 举报

neusharon 发表于 2014-11-30 03:24:00 | 显示全部楼层
稍微想了一下,感觉题目对两个BST的intersection不清楚,如果intersection是指子树(包括结构上)完全相同的话,前面层住说的先flatten为linkedlist然后找list的intersection的方法是不对的。eg:. From 1point 3acres bbs
   2                 2
     \                 \
      5                 4
   /   \                  \
4      6                 5. 鍥磋鎴戜滑@1point 3 acres
                             \
                              6
我认为constant space的方法是morris traversal 找到相同的node,再对比两个node的子树相同。求拍
回复 支持 反对

使用道具 举报

dtcxzch 发表于 2014-12-6 13:01:12 | 显示全部楼层
有parent的话用中序遍历从两个tree的最小节点开始比,然后依次找下个节点就可以了吧
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-1-31 09:58:02 | 显示全部楼层
这题要求不能用递归?
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-1-31 14:31:06 | 显示全部楼层
efny 发表于 2014-5-10 05:16
挂了,应该是个华裔哥。我一开始说了2种有extra space的方法,他不让我写,问我有没有不需要extra space的 ...

这个面试官简直脑残啊。。。。应该告诉他“you need some education..”
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-1-31 14:34:03 | 显示全部楼层
sj1456 发表于 2014-5-19 11:31
stack不是extra space???。。。另外O(1)space是不是就是没用extra space?

O(1)是常量空间啊,和in-place不一样的
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-1-31 15:40:00 | 显示全部楼层
neusharon 发表于 2014-11-30 03:24
稍微想了一下,感觉题目对两个BST的intersection不清楚,如果intersection是指子树(包括结构上)完全相同 ...

是的,flatten成list的方法需要考虑还原成之前的树, 因为按理说应该不允许毁坏之前的数据结构,除非是有明确要求可以改变这棵树。而且保存遍历结果的list需要extra space的,不合题意啊。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. 鍥磋鎴戜滑@1point 3 acres
如果是比较子树结构相等,为何要是BST呢,一般的Binary Tree就行啊。总觉得这个面试官自己都不清楚
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-19 19:41:48 | 显示全部楼层
CrossTheWall 发表于 2015-1-31 02:40
是的,flatten成list的方法需要考虑还原成之前的树, 因为按理说应该不允许毁坏之前的数据结构,除非是有 ...
-google 1point3acres
不是指结构上的交叉。。我个人感觉是iterator而已 所以上面贴了下代码。、,,
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 08:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表