传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3732|回复: 33
收起左侧

facebook 三面 加面

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

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

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

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

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

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

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


补充内容 (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. from: 1point3acres.com/bbs
因为我一开始写的recursion是:
1.找左子树最大值和当前节点值比.1point3acres缃
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
没太看懂这个面试官要求优化的是什么地方?

因为我一开始写的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到底可不可以啊
. 1point3acres.com/bbs
可以的,传参保存之前的一个值,发现下降点直接结束递归返回 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
. from: 1point3acres.com/bbs 请问楼主  面试官的意思是让你不用Resursion的方法? 要求用Inorder的方法嘛? 没看懂优化诶

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

使用道具 举报

hpplayer 发表于 2015-10-28 02:46:13 | 显示全部楼层
Iterative 版本的:
  1.     public boolean isValidBST(TreeNode root) {. visit 1point3acres.com for more.
  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)
这个就是普通的IN-ORDER TRAVERSAL,但是我写成了ITERATIVE形式
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-25 03:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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