San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 3289|回复: 21
收起左侧

FB家电面面经

[复制链接] |试试Instant~ |关注本帖
efny 发表于 2014-5-9 08:10:02 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类General 硕士 全职@Facebook - 网上海投 - 技术电面  | Other |

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
find the interection of two BST.
Print the number that appear in both BST.
No extra space, must be linear time

评分

5

查看全部评分

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

3、如果不想用栈,可以利用parent节点,实现和栈一样的功能。. 1point 3acres 论坛

4、楼主已经说了,是找到同时出现的数啊,所以不是指结构上的交叉。
. 1point 3acres 论坛
所以本题考察:中序遍历的非递归实现 + find intersection of two array 如果基础扎实10min应该可以码完。
同样出现的facebook面试为:here 以及 there
以下贴出代码:(用stack,O(h)额外空间)
  1. public class BSTIterator {. 1point 3acres 论坛
  2.     private Stack<TreeNode> stack = new Stack<TreeNode>();
  3.    
    -google 1point3acres
  4.     public BSTIterator(TreeNode root) {
  5.         pushAllLeft(root);  
  6.     }
  7. . From 1point 3acres bbs
  8.     /** @return whether we have a next smallest number */
  9.     public boolean hasNext() {
  10.         return !stack.empty(); 来源一亩.三分地论坛.
  11.     }

  12.     /** @return the next smallest number */ 来源一亩.三分地论坛.
  13.     public int next() {. 牛人云集,一亩三分地
  14.         TreeNode node = stack.pop();
  15.         pushAllLeft(node.right);
  16.         
  17.         return node.val;
  18.     }
  19.    
  20.     public int min() {. 1point 3acres 论坛
  21.         if (!stack.empty()) {
  22.             return stack.peek();
  23.         }
  24.     }
  25.    
  26.     private void pushAllLeft(TreeNode root) {
  27.         TreeNode head = root;
  28.         while (head != null) {
  29.             stack.push(head);-google 1point3acres
  30.             head = head.left;
  31.         }
  32.     }.1point3acres网
  33. }

  34. public class Solution {
  35.     public ArrayList<TreeNode> findIntersectionInTwoBST
  36.       (TreeNode rootA, TreeNode rootB) {
  37.         if (rootA == null || rootB == null) {
  38.             return null;
  39.         }
  40.         BSTIterator ia = new BSTIterator(rootA);
  41.         BSTIterator ib = new BSTIterator(rootB);
  42.         ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
  43.         while (ia.hasNext() && ib.hasNext()) {
  44.             if (ia.min().val == ib.min().val) {
  45.                 ans.add(ia.next());
  46.             } else if (ia.min().val < ib.min().val) {
  47.                 ia.next();
  48.             } else {
  49.                 ib.next();
  50.             }
  51.         }.本文原创自1point3acres论坛
  52.         
  53.         return ans;
  54.     }.留学论坛-一亩-三分地
  55. }
复制代码

评分

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 | 显示全部楼层

可以用Morris Traversal, 就是O(1)了. 围观我们@1point 3 acres

补充内容 (2014-5-10 03:35):
楼主最后有做出来吗?
回复 支持 反对

使用道具 举报

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

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| efny 发表于 2014-5-10 05:16:16 来自手机 | 显示全部楼层
挂了,应该是个华裔哥。我一开始说了2种有extra space的方法,他不让我写,问我有没有不需要extra space的。然后我说recursion行不行,他说好吧。结果头脑一片混乱写不出来。。最后我问他怎么做,他说tree 可以有parent pointer,我说X,这也行? 然后他说可以用stack,我说这不也是extra吗?然后就超时拜拜了。。

评分

3

查看全部评分

回复 支持 反对

使用道具 举报

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

我只要是华裔面我没有不挂的。。。patpat楼主,继续加油!
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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
stack不是extra space???。。。另外O(1)space是不是就是没用extra space?
. 围观我们@1point 3 acres
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
是不是先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:
   2                 2
     \                 \
      5                 4
   /   \                  \
4      6                 5
                             \
                              6. 围观我们@1point 3 acres
我认为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. From 1point 3acres bbs
挂了,应该是个华裔哥。我一开始说了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的,不合题意啊。

如果是比较子树结构相等,为何要是BST呢,一般的Binary Tree就行啊。总觉得这个面试官自己都不清楚
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-19 19:41:48 | 显示全部楼层
CrossTheWall 发表于 2015-1-31 02:40. visit 1point3acres for more.
是的,flatten成list的方法需要考虑还原成之前的树, 因为按理说应该不允许毁坏之前的数据结构,除非是有 ...

不是指结构上的交叉。。我个人感觉是iterator而已 所以上面贴了下代码。、,,
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 01:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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