脸书 电面

亲切的华人小哥，感觉放水了
1.
一个完全树。node有parent指针。
每个node的值为 0或 1
每个parent的值为两个子node的 “and” 结果
现在把一个leaf翻牌子（0变1或者1变0）
把树修正一遍

2.
numbe

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

site！



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

alucardzhou 发表于 2016-9-2 12:52
是的是的。
所以最后在复杂度的讨论部分有点意思。
最优是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

alucardzhou 发表于 2016-9-3 00:36
好犀利！
那个小哥当时就是这样讲的。

这小哥题出的挺用心的~ fb 的面经题我最近看了不少，但是这题的时间复杂度分析算是我最近看到的最有意思的一个！

第一题 traverse tree 改 val ？ 这就完了？
第二题，原来也是求面积最大吧。原题不是找有多少个岛么？

第一题能给点思路吗？只有parent指针吗？有left, right指针不？

cicean 发表于 2016-9-1 16:38
第一题 traverse tree 改 val ？ 这就完了？
第二题，原来也是求面积最大吧。原题不是找有多少个岛么？

所以我说小哥放水啊

之前地里有个面经是求周长的。
前提一样，一个矩阵，每个格子一个字母。
给一个坐标，以坐标开始，以相同字母建立最大岛，然后返回岛的周长。

iPhD 发表于 2016-9-1 19:23
第一题能给点思路吗？只有parent指针吗？有left, right指针不？

当然有啦。

alucardzhou 发表于 2016-9-2 08:28
当然有啦。

我感觉要分4种情况？leaf是0或1，和他的parent是0或1，然后递归着做？如果Leaf是0，它的parent也是0，这种情况还要考虑sibling，稍微麻烦点，是这样做吗？

iPhD 发表于 2016-9-2 08:32
我感觉要分4种情况？leaf是0或1，和他的parent是0或1，然后递归着做？如果Leaf是0，它的parent也是0，这 ...

直接postorder改值就可以啦！

Sorrow雨 发表于 2016-9-2 09:00
直接postorder改值就可以啦！

能说具体点吗？或给个伪代码？怎么改？

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

alucardzhou 发表于 2016-9-2 10:00
不用postorder遍历。别想复杂了。
输入就是个leaf node。（没有root）
因为是完全树（每个pare ...

如果Leaf是0，它的parent也是0，这种情况好像比较复杂？还要看sibling的值？是要分4种情况讨论，然后递归吗？