脸书VO跪经

tm1234 发表于 2020-9-14 10:25
同问！zszszzs

暴力算法行不行啊，统计每一层的个数，然后然后每一层作为complete的tree，这样可以计算需要添加或者删除的节点。然后找到最小值。

请问楼主第一面的coding题目是不是 利口 奇异？

zhangyangseu 发表于 2020-9-14 09:51
请问楼主第4题follow up怎么解啊 感谢！

当时时间不多了 只讨论了思路 大概先说了暴力解法 然后考虑了下如果子树是balance或者不balance的不同情况。感觉不balance的话 直接减掉多的子树的节点数或许可以达到最少值。也不是很确定 望大神提供思路

hgon23 发表于 2020-9-14 12:32
请问楼主第一面的coding题目是不是 利口 奇异？

算是变体吧 就是得看好例子 什么情况需要考虑当前路径 什么情况不需要考虑

zhangyangseu 发表于 2020-9-14 09:51
请问楼主第4题follow up怎么解啊 感谢！

個人一點想法
我們先算出整棵樹目前有的節點數量 然後用BFS去visit每個節點
由於在完全樹的情況每個節點可以有一個固定的編號
例如第一層的節點是0 第二層是1和2 以此類推 (p1 = 2 * c + 1, p2 = 2 * c + 2)
我們visit到某個節點的時候 都去計算補齊這個節點之前該有而沒有的節點 且刪除之後所有存在的節點
算出來的結果即是把這棵樹增減節點至當前節點所需步數
對於每個節點所算出的所需步數更新最小值
時間應該是 O(n) 不知道有沒有錯

我觉得可能不大对，有时候增加一节点后，后面的不用删，比如：a b # c d, 只要把#补全就可以了， 不需要删除c,d

CKCOS23 发表于 2020-9-15 03:44
個人一點想法
我們先算出整棵樹目前有的節點數量 然後用BFS去visit每個節點
由於在完全樹的情況每個節 ...

我觉得可能不大对，有时候增加一节点后，后面的不用删，比如：a b # c d, 只要把#补全就可以了， 不需要删除c,d

谢谢楼主分享，隐藏的部分暂时看不了求个大米

zhangyangseu 发表于 2020-9-15 05:40
我觉得可能不大对，有时候增加一节点后，后面的不用删，比如：a b # c d, 只要把#补全就可以了， 不需要 ...

哈哈可能我的表達太糟
a b # c d 的情況的話 整棵樹總共是 4 個節點
當我們在 a 會認為需要去除 4 (total) - 1 (visited) = 3 個節點且不用補節點 所以 cost = 3 + 0 = 3
在 b 的時候會認為需要去除 4 - 2 = 2 個節點且不用補節點 所以 cost = 2 + 0 = 2
在 c 的時候會認為需要去除 4 - 3 = 1 個節點且需要補 1 個節點 所以 cost = 1 + 1 = 2
在 d 的時候會認為需要去除 4 - 4 = 0 個節點且需要補 1 個節點 所以 cost = 0 + 1 = 1
我們取最小的 cost = 1

CKCOS23 发表于 2020-9-15 08:27
哈哈可能我的表達太糟
a b # c d 的情況的話 整棵樹總共是 4 個節點
當我們在 a 會認為需要去除 4 (tot ...

嗯嗯 感谢！ 意思就是以每个点为complete tree 的最后一个点，然后计算该增加的点和该去除的点，最后取最小值，时间复杂度O（n),   感觉O（logn） 应该做不成