Facebook 昂賽面經

楼主 task的题目能讲讲吗？图里每个节点指向前序task？怎么BFS，要探测circle吗

aodeyixia 发表于 2018-11-27 12:15
请问楼主第三轮第二题是topological sort吗，还是tree的结构一直，只需要做BFS就可以了？

topological sort后怎么找到路径呢？

那道k-nearest points不应该是min-heap嘛？

Adam57 发表于 2019-1-8 22:56
那道k-nearest points不应该是min-heap嘛？

老問題了，用 max-heap 是一個優化的過程。假設一共有 N 個點要找 k 個最近的點，用 min-heap 就得把所有點放進 heap 再取 k 個出來，所以 heap 內會有 N 個數。如此時間複雜度為 O(N log N)。

改用 max-heap 的概念是不斷把 k+1 近的點剔除 (if a[i] < heap.top() then heap.pop())，所以 heap 內能保持最多 k 個點。時間複雜度為 O(N log k)。

comaniac0621 发表于 2019-1-9 02:17
老問題了，用 max-heap 是一個優化的過程。假設一共有 N 個點要找 k 個最近的點，用 min-heap 就得把所有 ...

嗯嗯，谢谢解答，我说的就是第二个思路，O(Nlogk)的复杂度，但是要最近的点（距离最小的），对应的不应该用最小堆嘛？

Adam57 发表于 2019-1-9 03:23
嗯嗯，谢谢解答，我说的就是第二个思路，O(Nlogk)的复杂度，但是要最近的点（距离最小的），对应的不应该 ...

用 min-heap 做不出 O(N log k) 吧

comaniac0621 发表于 2019-1-9 03:26
用 min-heap 做不出 O(N log k) 吧

是我晕了么，堆里放k个元素，对应k个离原点最近的点，然后你进来一个点，如果堆size超过K，我就pop一个元素，这个的这个堆不是最小堆么（因为是最近，所以要距离最小）。。？