回复: 21
跳转到指定楼层
上一主题 下一主题
收起左侧

FB家电面面经

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
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

评分

参与人数 5大米 +51 收起 理由
豌豆开心果 + 20
fighterczy + 10 感谢分享!
爱丽丝和鲍勃 + 15
yk527 + 3 感谢分享!
tianz + 3 感谢分享!

查看全部评分


上一篇:Yelp面经
下一篇:Google London 被拒~
推荐
pandafolk 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 */
  12.     public int next() {
  13.         TreeNode node = stack.pop();
  14.         pushAllLeft(node.right);
  15.         
  16.         return node.val;
  17.     }
  18.    
  19.     public int min() {
  20.         if (!stack.empty()) {
  21.             return stack.peek();
  22.         }
  23.     }
  24.    
  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 {
  34.     public ArrayList<TreeNode> findIntersectionInTwoBST
  35.       (TreeNode rootA, TreeNode rootB) {
  36.         if (rootA == null || rootB == null) {
  37.             return null;
  38.         }
  39.         BSTIterator ia = new BSTIterator(rootA);
  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.         }
  51.         
  52.         return ans;
  53.     }
  54. }
复制代码

评分

参与人数 3大米 +14 收起 理由
lch04 + 10 感谢分享!
peace + 3 其实这题只是要把两树中重复的元素找出来就.
会编程的猪先生 + 1 回答的很好!

查看全部评分

回复

使用道具 举报

推荐
NdrZmansN 2015-1-31 14:08:08 | 只看该作者
全局:
感觉是写BST的inorder iterator.
这样就变成intersection of two sequences了.
回复

使用道具 举报

🔗
wondermu 2014-5-10 02:52:37 | 只看该作者
全局:
No extra space  不可能吧,起码要log(n)
回复

使用道具 举报

🔗
discoveryi 2014-5-10 03:27:19 | 只看该作者
全局:
wondermu 发表于 2014-5-10 02:52
No extra space  不可能吧,起码要log(n)

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

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

使用道具 举报

🔗
shire1989 2014-5-10 03:52:31 | 只看该作者
全局:
是不是先flatten BST to linkedlist(这个也不用额外开辟新的list内存),然后你比较两个list的相交部分

评分

参与人数 2大米 +15 收起 理由
22691482 + 5 回答的很好!
Kimurate + 10 好答案

查看全部评分

回复

使用道具 举报

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

评分

参与人数 3大米 +16 收起 理由
Kimurate + 10 momo,遇上这2面试官
discoveryi + 3 继续加油!
1guangnian + 3 patpat,感觉被坑了

查看全部评分

回复

使用道具 举报

🔗
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?

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是乱序的,要求相交,复杂度很高。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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