一亩三分地论坛

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

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

facebook 三面 加面

[复制链接] |试试Instant~ |关注本帖
plich 发表于 2015-10-27 02:27:10 | 显示全部楼层 |阅读模式

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

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

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

x
coordinator 犯了一个错误,给我排的2:30 PM,给那个老印排了10:00AM,我真是……
是个老印,我说了一下我可以面不过希望能晚一点但是肯定以你schedule为准反正您是大爷您唆了蒜…….鐣欏璁哄潧-涓浜-涓夊垎鍦
search组的,两年多工作经验,我自我介绍两三句,他也没问问题,直接开搞

1.跟fibonacci number差不多,f(n)=f(n-1)+2*f(n-3)
2.isValidBST: 判断一颗树是否为二叉搜索树
. 1point 3acres 璁哄潧
第二题有点聪明反被聪明误,自己写了一个渣recursion,然后问optimize的时候又说用inorder traversal,然后他说不行,在他的提示下写了另外一个……

提醒大家一下,在部分interviewer眼里递归开stack是不算space complexity的,所以他们让你算空间复杂度的时候记得问他……
  1. 我:“inorder复杂度是 O(logn),因为要开stack或者用stack”
  2. 老印:”你说logn可是worst case是O(n)吖,咱们来个不要空间的“. Waral 鍗氬鏈夋洿澶氭枃绔,
  3. 我:”不要空间?!……“-google 1point3acres
  4. 老印:”你看你的原始解法也是一个recursion,但是前半段走太深了,你优化一下,不就是不要空间了么“.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5. (我:”你麻痹我写个recursion的inorder不也是'不要空间么'…… “)
复制代码
Anyway,求过求积分啊……
呃……求过就行,过了给我捐了积分也成啊……


补充内容 (2015-10-27 06:23):
已过……

评分

4

查看全部评分

bill701 发表于 2015-11-12 05:44:09 | 显示全部楼层
gamespeed 发表于 2015-10-27 13:10
我的递归是这样的,每次检查某个节点是否在某个范围内,并递归检查其子树

不小心手抖点了个反对,求问怎么删除反对
回复 支持 1 反对 2

使用道具 举报

gamespeed 发表于 2015-10-27 13:10:27 | 显示全部楼层
plich 发表于 2015-10-27 12:07. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
因为我一开始写的recursion是:
1.找左子树最大值和当前节点值比. 1point 3acres 璁哄潧
2.找右子树最大值和当前节点值比

我的递归是这样的,每次检查某个节点是否在某个范围内,并递归检查其子树
  1. bool isValid(Node *root, long long min, long long max);
复制代码
回复 支持 0 反对 1

使用道具 举报

gamespeed 发表于 2015-10-27 11:19:31 | 显示全部楼层
没太看懂这个面试官要求优化的是什么地方?
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2015-10-27 11:53:27 | 显示全部楼层
cong! lz通过的略快呀
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-27 12:07:20 | 显示全部楼层
gamespeed 发表于 2015-10-27 11:19. more info on 1point3acres.com
没太看懂这个面试官要求优化的是什么地方?

因为我一开始写的recursion是:
1.找左子树最大值和当前节点值比
2.找右子树最大值和当前节点值比
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴3.递归……
所以才有优化的地方了……
但是按照inorder来其实并没有优化的空间……起码没有他所期待的优化
回复 支持 反对

使用道具 举报

hohojoy 发表于 2015-10-27 14:02:03 | 显示全部楼层
morris traversal 应该可以优化吧。常数空间
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-27 14:09:09 | 显示全部楼层
第二题用inorder到底可不可以啊
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-27 20:50:57 | 显示全部楼层
gamespeed 发表于 2015-10-27 13:10
我的递归是这样的,每次检查某个节点是否在某个范围内,并递归检查其子树

嗯,这个是我的interviewer所期待的优化
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-27 20:52:03 | 显示全部楼层
jy_121 发表于 2015-10-27 14:09
第二题用inorder到底可不可以啊

可以的,传参保存之前的一个值,发现下降点直接结束递归返回 false就成了
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-28 00:34:09 | 显示全部楼层
plich 发表于 2015-10-27 20:52
可以的,传参保存之前的一个值,发现下降点直接结束递归返回 false就成了

好的,多谢
回复 支持 反对

使用道具 举报

cu0817 发表于 2015-10-28 01:13:10 | 显示全部楼层
LZ 上面说面试官说 worst case O(N) 是 space complexity?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-10-28 02:08:42 | 显示全部楼层
plich 发表于 2015-10-27 12:07
因为我一开始写的recursion是:
1.找左子树最大值和当前节点值比
2.找右子树最大值和当前节点值比

请问楼主  面试官的意思是让你不用Resursion的方法? 要求用Inorder的方法嘛? 没看懂优化诶
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-10-28 02:09:20 | 显示全部楼层
恭喜楼主,祝楼主offer
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-28 02:28:30 | 显示全部楼层
小A要当码农 发表于 2015-10-28 02:08
请问楼主  面试官的意思是让你不用Resursion的方法? 要求用Inorder的方法嘛? 没看懂优化诶

不是,因为我挖的坑是一个大于O(n)的方法……所以他就希望来一个O(n)的
回复 支持 反对

使用道具 举报

hpplayer 发表于 2015-10-28 02:46:13 | 显示全部楼层
Iterative 版本的:
  1.     public boolean isValidBST(TreeNode root) {
  2.         if(root == null) return true;
  3.         
  4.         Stack<TreeNode> stack = new Stack<TreeNode>();
  5.         
  6.         TreeNode curr = root;
  7.         TreeNode prev = null;
  8.         
  9.         while(!stack.isEmpty() || curr != null){
  10.             if(curr != null){
  11.                 stack.push(curr);
  12.                 curr = curr.left;
  13.             }else{
  14.                 TreeNode temp = stack.pop();
  15.                 if(prev != null && temp.val <= prev.val) return false;
  16.                 prev = temp;
  17.                 curr = temp.right;
  18.             }
  19.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.         
  21.         return true;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.         
  23.     }
复制代码
回复 支持 反对

使用道具 举报

hpplayer 发表于 2015-10-28 02:47:21 | 显示全部楼层
为什么会有三面?我不明白,如果电面发挥不好,不是直接REJ么,怎么还会有加面呢?
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-10-28 04:11:14 | 显示全部楼层

这个时间,空间复杂度是多少?
回复 支持 反对

使用道具 举报

oio14644 发表于 2015-10-28 04:13:29 | 显示全部楼层
fibonacci number 这个递归能过吗? 要求用迭代了吗?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-10-28 04:29:25 | 显示全部楼层
plich 发表于 2015-10-28 02:28
不是,因为我挖的坑是一个大于O(n)的方法……所以他就希望来一个O(n)的

好吧。。。祝早日拿offer啦~
回复 支持 反对

使用道具 举报

hpplayer 发表于 2015-10-28 04:31:48 | 显示全部楼层
oio14644 发表于 2015-10-28 04:11
这个时间,空间复杂度是多少?

空间 O(logN)就是树的高度,时间的话就是O(N). 1point 3acres 璁哄潧
这个就是普通的IN-ORDER TRAVERSAL,但是我写成了ITERATIVE形式
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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