脸书 电面

alucardzhou 发表于 2016-9-2 22:51
你说得对对。可能是我记错了。
说实话自己当时很紧张。
十分害怕碰到什么写json啊，什么不 ...

(1/2)的(logN)次方吧，N很大的时候，复杂度可能就约等于O(1)了吧。不过应该没事，感觉LZ答得很好，祝顺利拿到onsite~

hzyslddm 发表于 2016-9-2 10:25
(1/2)的(logN)次方吧，N很大的时候，复杂度可能就约等于O(1)了吧。不过应该没事，感觉LZ答得很好，祝顺利 ...

原来真是这样啊，受教了。

代码虽然写的比较慢，但是应该是bug free的。
佛祖保佑，永无bug

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

mnmunknown 发表于 2016-9-2 11:31
leaf node 区分左右的话，可能有4种组合，每种组合分别有 flip{left, right} 两种选择，于是：

0,0 -  ...

好犀利！
那个小哥当时就是这样讲的。

感谢！

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

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

鼓励和提倡给同胞放水的行为

LZ脸书一般电面几面呀？

到现在为止我直接到一个。看地里的面经觉得电面应该就一轮。

感觉应该跟这道题类似吧。不过不用DP  直接 DFS 搜相连 面积就行吧，
are 找到一个就++ 有几个相似的面积应该就多大吧。

cicean 发表于 2016-9-3 14:27
感觉应该跟这道题类似吧。不过不用DP  直接 DFS 搜相连 面积就行吧，
are 找到一个就++ 有几个相似的面积 ...

221        Maximal Square        20.2%        Medium