一亩三分地论坛

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

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

FB intern Round1

[复制链接] |试试Instant~ |关注本帖
夹心lee 发表于 2015-4-5 00:29:07 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
周四面的F家,是第一轮面试,赶在周末发个面筋~问了一个behavior的问题:Why FB?

第一题:strstr的leetcode原题,题目和solution都可以在leetcode上找到,就不多说啦
第二题(被面试官强行加的):
TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

public class Tree {
    private TreeNode root;. 1point 3acres 璁哄潧

    public Tree(TreeNode root) {
        this.root = root;
    }

    //implementation method to output next node of current node in pre-order traversal. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    public TreeNode next()
}. visit 1point3acres.com for more.
My Solution:
1. 一开始觉得这是一个简单的先序遍历,后面一看不是,而且没有理解题意,以为不能使用其他变量去保存,只能用next方法来直接处理。
2. 后面想了想,还是得使用辅助空间,声明了一个变量list,使用ArrayList在构造函数中保存了先序遍历树产生的所有结果,之后在next方法中每次返回第一个,并且删除第一个元素,当list为空时,遍历结束。
3. 面试官问还有没有更好的解法,并没有答上来,他也没有继续追问,然后问了问这个solution的优缺点,就结束了面试。. 鍥磋鎴戜滑@1point 3 acres
总的来说lz感觉三哥哥很没耐心啊对我写code的过程也不是很有兴趣,lz一直试图和他互动,可是他貌似在忙别的?总之沟通的有点蛋疼,一副爱理不理的样子==。
ps到现在也没有收到邮件通知,请问一下地里的大神们这种情况会不会挂掉

. 1point 3acres 璁哄潧

评分

1

查看全部评分

ppips 发表于 2015-4-7 07:34:33 | 显示全部楼层
haungge0385 发表于 2015-4-6 16:13. 1point 3acres 璁哄潧
请问有大神贴一下tree iterator 的代码吗?烧香感谢。。。

请指正
  1. // Tree iterator (preorder). visit 1point3acres.com for more.
  2. public static class BSTIterator {
  3.         TreeNode next;
  4.         Stack<TreeNode> stack;
  5.         public BSTIterator(TreeNode root) {
  6.                 next = root;. more info on 1point3acres.com
  7.                 stack = new Stack<TreeNode>();
  8.                 if (next != null)
  9.                         stack.push(next);
  10.                 next = stack.isEmpty() ? null : stack.pop();
  11.         }

  12.         /** [url=home.php?mod=space&uid=160137]@return[/url] whether we have a next smallest number */
    . 1point 3acres 璁哄潧
  13.         public boolean hasNext() {
  14.                 return next != null;. visit 1point3acres.com for more.
  15.         }
  16. . Waral 鍗氬鏈夋洿澶氭枃绔,
  17.         /** @return the next smallest number */
  18.         public int next() {. more info on 1point3acres.com
  19.                 int res = next.val;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                 if (next != null) {
  21.                         TreeNode n = next;
  22.                         if (n.right != null). 鍥磋鎴戜滑@1point 3 acres
  23.                                 stack.push(n.right);
  24.                         if (n.left != null)
  25.                                 stack.push(n.left);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.                 }
  27.                 next = stack.isEmpty() ? null : stack.pop();
  28.                 return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  29.         }
  30. }
复制代码
回复 支持 1 反对 0

使用道具 举报

lch04 发表于 2015-4-5 00:52:58 | 显示全部楼层
第二题还是LC原题吖
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-4-5 01:05:10 | 显示全部楼层
现在fb还在面intern。。这是今年得扩招了多少啊。。第一批都快入职了。。LZ尽量快点安排第二轮吧。
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-4-5 01:06:07 | 显示全部楼层
没事 第一轮很容易过 好好准备第二轮吧。
回复 支持 反对

使用道具 举报

 楼主| 夹心lee 发表于 2015-4-5 01:08:07 | 显示全部楼层
北航小涵 发表于 2015-4-4 12:05
现在fb还在面intern。。这是今年得扩招了多少啊。。第一批都快入职了。。LZ尽量快点安排第二轮吧。

上周末收到的邮件 排的这周四....前提是能收到第二轮啊
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-4-5 01:08:37 | 显示全部楼层
另外都是原题。。。。。你这个想法是用了O(n)的额外空间。。这个题目就是变相考你tree 遍历的stack实现。。
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-4-5 01:09:47 | 显示全部楼层
建议好好看看基础 二叉树的所以题目都要会的 我面了两轮FB每轮都有二叉树。当然就是基础变形而已
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-4-5 01:14:14 | 显示全部楼层
楼主头像是秀智吗...-google 1point3acres
怎么才能拿到FB面试啊
回复 支持 反对

使用道具 举报

 楼主| 夹心lee 发表于 2015-4-5 01:51:10 | 显示全部楼层
北航小涵 发表于 2015-4-4 12:09
建议好好看看基础 二叉树的所以题目都要会的 我面了两轮FB每轮都有二叉树。当然就是基础变形而已

好的 看来**还是得多刷题...谢谢小涵!我来沾沾喜气!
回复 支持 反对

使用道具 举报

 楼主| 夹心lee 发表于 2015-4-5 02:02:34 | 显示全部楼层
nibuxing 发表于 2015-4-4 12:14
楼主头像是秀智吗...
怎么才能拿到FB面试啊
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
是秀智
我是网投的~

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-5 04:31:38 | 显示全部楼层
想问问lz第二题的binary tree是full tree还是any tree啊? any tree的话代码也不好写的
回复 支持 反对

使用道具 举报

ppips 发表于 2015-4-5 04:38:58 | 显示全部楼层
yuxrose 发表于 2015-4-5 04:31
想问问lz第二题的binary tree是full tree还是any tree啊? any tree的话代码也不好写的

好像没有什么区别吧 只要是前序遍历就可以吧?
回复 支持 反对

使用道具 举报

haoxuango 发表于 2015-4-5 04:40:48 | 显示全部楼层
strstr 能用brute force 吗
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-5 04:58:21 | 显示全部楼层
ppips 发表于 2015-4-5 04:38
好像没有什么区别吧 只要是前序遍历就可以吧?

不太一样吧,如果是full tree的话,left child直接连right child, 如果不是的话,像下面这个
     A. from: 1point3acres.com/bbs
B         C
D null  E null

这种情况D是连E,还是不连,保持原状? 连E的话就得找下个同level的下个child,这里比较麻烦一下,也是我觉得next pointer II 比 I 最麻烦的地方。
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-5 07:06:22 | 显示全部楼层
汗我好像看错题了,不是要connect nodes,是successor啊!
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-5 07:10:24 | 显示全部楼层
lch04 发表于 2015-4-5 00:52
第二题还是LC原题吖
. 1point 3acres 璁哄潧
能告诉我是哪道题吗?
回复 支持 反对

使用道具 举报

ppips 发表于 2015-4-5 08:10:54 | 显示全部楼层
yuxrose 发表于 2015-4-5 07:10.1point3acres缃
能告诉我是哪道题吗?

lc原题是inorder iterator 这个是preorder 不过差不多实现起来
回复 支持 反对

使用道具 举报

haungge0385 发表于 2015-4-7 05:13:26 | 显示全部楼层
请问有大神贴一下tree iterator 的代码吗?烧香感谢。。。
回复 支持 反对

使用道具 举报

碇真嗣 发表于 2015-4-7 05:30:17 | 显示全部楼层
表示我二面的时候也遇到了差不多的面试官。。是个棒子。。爱理不理的。。LZ后来有结果了吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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