狗家新鲜VO面经

freezeblue 发表于 2022-4-27 22:51
第三轮

insert(parent_id, node_id)

node_id可以是一个新的id也可以是已经在tree里的node_id，要分别处理。添加一个新的node需要考虑新的tree不能超过max_depth，而且要在O(max_depth)内实现。

请问lz是面的L5吗？还是L4也是有SD？谢谢

lucius323 发表于 2022-4-28 13:45
请问lz是面的L5吗？还是L4也是有SD？谢谢

L5紫薯紫薯

楼主最后一题是用什么方法做的？是priority queue吗。

我的思路是用用一个map存value -> priority queue
addOrReplace 如果是add那就append index到当前priority queue去，如果是replace那就old_value_priority_queue.remove(old_index)，然后append index给新的value的priority queue，时间复杂度是O(N)
findSmallestIndex 从map里取出priority queue，如果没有活着queue是空的就return -1，O(1) 复杂度

微信用户_e7fb7bf 发表于 2022-4-29 21:59
楼主最后一题是用什么方法做的？是priority queue吗。

我的思路是用用一个map存value -> priority queue ...

我当时用的python的SortedSet（类似于Java的TreeMap），两个时间复杂度都是logN

匿名者 发表于 2022-4-29 22:40
我当时用的python的SortedSet（类似于Java的TreeMap），两个时间复杂度都是logN

请问你指的是用两个数据结构吗
1. index_to_num = dict()
2. num_to_indexes = defaultdict(SortedSet)

想请教一下第三轮整体思路，其中delete那部分node delete以后left，right child也一起delete吗？还是像bst一样需要考虑0-2个子树会有不同处理方法？感谢

Delete 是要把 delete 那個 node 下面的 child node 全部接上 delete node 的 parent 嗎 ?

想请教下SD轮的思路，如果能拿到所有的phishing URL，感觉这个问题还是很直接的。不知道具体的讨论的点在哪里