一亩三分地论坛

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

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

脸书 电面

[复制链接] |试试Instant~ |关注本帖
alucardzhou 发表于 2016-9-2 05:17:25 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other在职跳槽

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

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

x
亲切的华人小哥,感觉放水了. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1.. visit 1point3acres.com for more.
一个完全树。node有parent指针。
每个node的值为 0或 1
每个parent的值为两个子node的 “and” 结果
现在把一个leaf翻牌子(0变1或者1变0)
把树修正一遍

2.
number of Island的超简化
给出一个二维char表,再给一个坐标
从坐标开始
找出所有连接(上下左右)的相同char
最后返回这个大岛的面积. From 1point 3acres bbs
【地里有个面经是返回这个大岛的周长,感觉我这个是简化了】

小哥思维很敏捷,祝他工作顺利
保佑我拿到onsite!



补充内容 (2016-9-6 12:30):
过完长周末被告知要第二轮电面。接着好好刷吧。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

mnmunknown 发表于 2016-9-3 00:31:26 | 显示全部楼层
alucardzhou 发表于 2016-9-2 12:52
是的是的。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
所以最后在复杂度的讨论部分有点意思。.鏈枃鍘熷垱鑷1point3acres璁哄潧
最优是O(1),最差是(logN)

leaf node 区分左右的话,可能有4种组合,每种组合分别有 flip{left, right} 两种选择,于是:

0,0 - 左,变成1; 右,变成1. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
0,1 - 左,不变; 右,变成0
1,0 - 左,变成0;右,不变;
1,1 - 左,不变,右,不变;

总共会造成 parent node 的值和之前有变化的可能是 4 种,所以在每一层 parent - child 的关系中任意 flip 一个 child,有 1/2 的几率造成 parent 的值也被 flip.

假设二叉树中总共有 N 的节点,其深度/自底向上路径长是 h = O(logN),那我们自底向上的更新路径实际次数就会在 【1, h】 的闭区间内,最少更新次数为 1 (计算了 leaf,但是发现对 parent 无任何影响),最大计算次数为 h ,代表一路更新到了 root.

那我们总共会计算【1,2,3 ... h】层的概率就是 【1 , 1/2 , (1/2)^2 , (1/2)^3 ... (1/2)^h】,其对应的计算次数期望值就是 1 + 1 * 1/2 + 2 * (1/2)^2 + 3 * (1/2)^3 + .... h * (1/2)^h  = 1 + Sigma (n / 2^n),在 n 趋近于无限的情况下,upper bound 是 1 + 2 = 3 ~ 所以总共的计算次数期望值确实是常数

补充内容 (2016-9-3 00:45):
最后一句话打错了=。=  变量名是 h 不是 n
回复 支持 3 反对 0

使用道具 举报

mnmunknown 发表于 2016-9-3 00:37:50 | 显示全部楼层
alucardzhou 发表于 2016-9-3 00:36. more info on 1point3acres.com
好犀利!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
那个小哥当时就是这样讲的。

这小哥题出的挺用心的~ fb 的面经题我最近看了不少,但是这题的时间复杂度分析算是我最近看到的最有意思的一个!
回复 支持 1 反对 0

使用道具 举报

cicean 发表于 2016-9-2 05:38:24 | 显示全部楼层
第一题 traverse tree 改 val ? 这就完了?
第二题,原来也是求面积最大吧。原题不是找有多少个岛么?
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-2 08:23:55 | 显示全部楼层
第一题能给点思路吗?只有parent指针吗?有left, right指针不?
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-2 08:25:32 | 显示全部楼层
cicean 发表于 2016-9-1 16:38
第一题 traverse tree 改 val ? 这就完了?
第二题,原来也是求面积最大吧。原题不是找有多少个岛么?


所以我说小哥放水啊

之前地里有个面经是求周长的。
前提一样,一个矩阵,每个格子一个字母。.鏈枃鍘熷垱鑷1point3acres璁哄潧
给一个坐标,以坐标开始,以相同字母建立最大岛,然后返回岛的周长。
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-2 08:28:39 | 显示全部楼层
iPhD 发表于 2016-9-1 19:23
第一题能给点思路吗?只有parent指针吗?有left, right指针不?

当然有啦。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-2 08:32:55 | 显示全部楼层
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我感觉要分4种情况?leaf是0或1,和他的parent是0或1,然后递归着做?如果Leaf是0,它的parent也是0,这种情况还要考虑sibling,稍微麻烦点,是这样做吗?
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-9-2 09:00:46 | 显示全部楼层
iPhD 发表于 2016-9-2 08:32
我感觉要分4种情况?leaf是0或1,和他的parent是0或1,然后递归着做?如果Leaf是0,它的parent也是0,这 ...

直接postorder改值就可以啦!
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-2 09:03:53 | 显示全部楼层
Sorrow雨 发表于 2016-9-2 09:00.鐣欏璁哄潧-涓浜-涓夊垎鍦
直接postorder改值就可以啦!

能说具体点吗?或给个伪代码?怎么改?
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-2 10:00:15 | 显示全部楼层

不用postorder遍历。别想复杂了。
输入就是个leaf node。(没有root)
因为是完全树(每个parent都膝下双子健在),而且有parent指针。
所以就是一个自底向上的检查。
顺序是:
先把所给leaf的值switch。然后基于新值检查其parent是否需要switch。
如果需要,则对其parent递归运行同样的方法。
如果不需要,return停止。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-2 10:13:02 | 显示全部楼层
alucardzhou 发表于 2016-9-2 10:00
不用postorder遍历。别想复杂了。
输入就是个leaf node。(没有root)
因为是完全树(每个pare ...

如果Leaf是0,它的parent也是0,这种情况好像比较复杂?还要看sibling的值?是要分4种情况讨论,然后递归吗?
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-2 10:22:09 | 显示全部楼层
防水的题 第一眼  我也没思路 ——>去刷题,要努力哦,加油! 昨晚刷到凌晨1点。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-2 10:32:34 | 显示全部楼层
alucardzhou 发表于 2016-9-2 10:00
不用postorder遍历。别想复杂了。
输入就是个leaf node。(没有root). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
因为是完全树(每个pare ...

输入时所有的leaves?
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-9-2 11:03:29 | 显示全部楼层
iPhD 发表于 2016-9-2 09:03
能说具体点吗?或给个伪代码?怎么改?

哦哦 理解错了 直接给你的就是改过的leaf node么?那就直接向上改就行了吧
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-9-2 11:07:49 | 显示全部楼层
alucardzhou 发表于 2016-9-2 10:00
不用postorder遍历。别想复杂了。
输入就是个leaf node。(没有root)
因为是完全树(每个pare ...

运气可以啊 ! 祝lz早日拿到offer
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-9-2 11:08:15 | 显示全部楼层
houqingniao 发表于 2016-9-2 10:32
输入时所有的leaves?
. visit 1point3acres.com for more.
只改一个leaf 所以输入就是那个leaf
回复 支持 反对

使用道具 举报

wzs9988 发表于 2016-9-2 11:32:35 | 显示全部楼层
第一题感觉直接走一遍从leaf到root的path就行了?(depending on 树的值,未必需要完全走完)-google 1point3acres
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  1. void invert(TreeNode n) {
  2.     while (n != null) {
  3.         n.val ^= 1;
  4.         if (n.parent != null) {
  5.             if (n.parent.left == n) {
  6.                 if (n.parent.right.val == 0) break;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7.             } else {. visit 1point3acres.com for more.
  8.                 if (n.parent.left.val == 0) break;. 1point 3acres 璁哄潧
  9.             }
  10.         }. 鍥磋鎴戜滑@1point 3 acres
  11.         n = n.parent;
  12.     }
  13. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-2 12:49:13 | 显示全部楼层
Sorrow雨 发表于 2016-9-1 22:03
哦哦 理解错了 直接给你的就是改过的leaf node么?那就直接向上改就行了吧

正解!就是这个意思
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-2 12:52:57 | 显示全部楼层
wzs9988 发表于 2016-9-1 22:32
第一题感觉直接走一遍从leaf到root的path就行了?(depending on 树的值,未必需要完全走完)

是的是的。. 鍥磋鎴戜滑@1point 3 acres
所以最后在复杂度的讨论部分有点意思。
最优是O(1),最差是(logN)
但是小哥引进了概率。每次parent翻牌子的几率只有1/4.
所以平均时间复杂度比logN要低。他说是O(1)。
这里我也没太理解。
回复 支持 反对

使用道具 举报

hzyslddm 发表于 2016-9-2 14:36:05 | 显示全部楼层
alucardzhou 发表于 2016-9-2 12:52.鏈枃鍘熷垱鑷1point3acres璁哄潧
是的是的。
所以最后在复杂度的讨论部分有点意思。. 1point3acres.com/bbs
最优是O(1),最差是(logN)

谢谢Lz分享,请问每次parent翻牌子的概率为什么是1/4? 感觉是1/2呀,两个孩子的值有四种可能(1 1,0 0, 1 0, 0 1), 假设被翻的是前面的孩子, 那么第1、4种情况下,翻了孩子之后parent的值都会变
回复 支持 反对

使用道具 举报

 楼主| alucardzhou 发表于 2016-9-2 22:51:23 | 显示全部楼层
hzyslddm 发表于 2016-9-2 01:36. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢Lz分享,请问每次parent翻牌子的概率为什么是1/4? 感觉是1/2呀,两个孩子的值有四种可能(1 1,0 0,  ...
. 1point 3acres 璁哄潧

你说得对对。可能是我记错了。. From 1point 3acres bbs
说实话自己当时很紧张。
十分害怕碰到什么写json啊,什么不排序找等差数列那样的神题。
那么这种情况下时间复杂度应该是O(1)么?还是仍然是O(logN)呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 14:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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