狗家上周上门面

LionelWang 发表于 2019-6-12 15:06
系统设计日志系统怎么解？

按某章系统设计的套路来做的，是一个write heavy的系统

关于第三题 我想问一下， 这个parentship 是transitive的吗？比如说我要删除2 3是2的child 那是不是意味着所有3的children也需要被删除？

chenyijia055 发表于 2019-6-13 06:15
关于第三题 我想问一下， 这个parentship 是transitive的吗？比如说我要删除2 3是2的child 那是不是意味着 ...

对的，需要

fir925 发表于 2019-6-13 06:21
对的，需要

谢谢了, 你说的index就是原数组里面的位置吧。删除了之后每个树自己的index需要更新成，新数组对应的index，然后parent的指针也要变成当前parent所在的新index对吧？这题想写好，应该还是有难度的，请问你当时用了什么办法？面试官有没有expected的方法来做呢？

请问lz几年工作经验?

fir925 发表于 2019-6-12 08:57
对，思路是这样

naive的recursion速度太慢，要保证不能比O(logn)慢
是不是说从中间切一刀，如果切到的数比target大或者小就只递归一半，如果正好切到target就递归两边，还有就是如果一段的开始和结束都等于target就直接返回长度？

很有用的信息！

第三题用union find吧，一棵树只要有一个结点被移掉了整棵树就没了吧

yangyuzhiguang 发表于 2019-6-14 03:15
第三题用union find吧，一棵树只要有一个结点被移掉了整棵树就没了吧

要求是只删parent下的子树，不是整个树
整个树删除用union find最优
删子树用adjcency list dfs最优

LionelWang 发表于 2019/06/14 06:25:34


要求是只删parent下的子树，不是整个树
整个树删除用union find最优
删子树用adjcency list dfs最优

uf也可以删除子树 跳过删除的不连就可以了