狗家昂赛跪经

第二题应该不简单啊

应该是leetcode 最新的contest的最后一题

"round 3: 利口留扒坝"
想确认一下，这个是 留巴巴？

最后一题不就是红黑树再加上每个节点记录子树个数就行了吧。。。

请问楼主在哪个Office面的

这都是T4的面试题么？ 还是T3的？ 感觉现在T3也都很多hard题目了。

littledog 发表于 2018-3-21 04:36
最后一题不就是红黑树再加上每个节点记录子树个数就行了吧。。。

不过如果真的要白板code的话，红黑树写不完的啊

请问一下，第四轮那个题目，插入的节点的大小是完全random的么？如果是的话可以build一个bst，存一下左边有多少个节点。不知道这个思路对不对，谢谢回复啦

zhengyiyu 发表于 2018-3-13 11:42
第4轮是否可以考虑为一个bst，然后每个节点额外存上左树所有node的数量，这样就知道自己是第多少个了

所 ...

我怎么觉得这个思路有点问题，如果更新父节点的数量，那所有比插入节点大的都应该被更新，这个操作就应该是o(n)了吧。

yuxrose 发表于 2018-3-25 14:49
我怎么觉得这个思路有点问题，如果更新父节点的数量，那所有比插入节点大的都应该被更新，这个操作就应该 ...

只需要更新所有父节点就可以了吧，如果比插入节点大的已知节点，但是是右子树的，不需要管吧。

           5
    3             6
（1）

更新前，3的左子树数量是0，5的是1，6的是0，插入1后，只需要把3的更新为1，5的更新为2就可以了

这样算6的rank时候，就是根据他的父子树5的左子树数量（2）+1（root 节点） + 6的左子树数量（如果有的话）