《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3160|回复: 21
收起左侧

FB家电面面经

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

2014(4-6月) 码农类 硕士 全职@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。-google 1point3acres
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);  
    . more info on 1point3acres.com
  6.     }

  7.     /** @return whether we have a next smallest number */
  8.     public boolean hasNext() {
  9.         return !stack.empty();
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.     }
  11. . Waral 鍗氬鏈夋洿澶氭枃绔,
  12.     /** @return the next smallest number */.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.     public int next() {
  14.         TreeNode node = stack.pop();
  15.         pushAllLeft(node.right);
  16.         . 1point 3acres 璁哄潧
  17.         return node.val;
  18.     }
  19.     . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.     public int min() {
  21.         if (!stack.empty()) {
    . from: 1point3acres.com/bbs
  22.             return stack.peek();
  23.         }
  24.     }
  25.    
  26.     private void pushAllLeft(TreeNode root) {
  27.         TreeNode head = root;
    . from: 1point3acres.com/bbs
  28.         while (head != null) {
  29.             stack.push(head);
  30.             head = head.left;
  31.         }
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  32.     }
  33. }

  34. public class Solution {
  35.     public ArrayList<TreeNode> findIntersectionInTwoBST
  36.       (TreeNode rootA, TreeNode rootB) {
  37.         if (rootA == null || rootB == null) {
  38.             return null;. visit 1point3acres.com for more.
  39.         }
  40.         BSTIterator ia = new BSTIterator(rootA);
  41.         BSTIterator ib = new BSTIterator(rootB);. visit 1point3acres.com for more.
  42.         ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
  43.         while (ia.hasNext() && ib.hasNext()) {
  44.             if (ia.min().val == ib.min().val) {. 鍥磋鎴戜滑@1point 3 acres
  45.                 ans.add(ia.next());
  46.             } else if (ia.min().val < ib.min().val) {
  47.                 ia.next();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  48.             } else {
  49.                 ib.next();
  50.             }
  51.         }. 1point3acres.com/bbs
  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)了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (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楼主,继续加油!
回复 支持 反对

使用道具 举报

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?
. visit 1point3acres.com for more.
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的相交部分
.1point3acres缃
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. from: 1point3acres.com/bbs
   /   \                  \
4      6                 5
                             \
                              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
-google 1point3acres挂了,应该是个华裔哥。我一开始说了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
.鐣欏璁哄潧-涓浜-涓夊垎鍦是的,flatten成list的方法需要考虑还原成之前的树, 因为按理说应该不允许毁坏之前的数据结构,除非是有 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 03:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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