狗家昂赛跪经

回馈地里攒人品，题目本身不太难，但是楼主题目练习不过关，写起来太慢，move on了

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Ferocious丶 发表于 2018-3-20 05:24
楼主请问下 第一题那个返回回文串要求inplace么？还是说可以重新建一个string？
利口应该不是inplace的

没有要求inplace

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的左子树数量（如果有的话）

Kwang100 发表于 2018-3-15 03:19
层主，这个思路当然是对的，但是这个方法问题是不是在于如果BST不平衡的话，插入，删除都几乎是O（n）了 ...

这个如果不写代码，纯followup的话，用个 height balance的bst就可以解决了吧

感觉不会让写出来的，最多就提一下红黑树/avl树之类的呗。

其实这个题，我还想过另外一种方式就是用bucket的思想，在对数据有假设的情况下，或许能做到overhead很高的O（1），或者O（logn）的话，在bucket级别上加上skip list的结构。但是基本只能用来口头讨论，不能写代码了

楼主 最后一题 是不是个二叉树呢？多记录一些信息？

楼主请问第二题输入是什么结构呢？需要自己定义数据结构吗

第二题感觉像是个有向图问题  最后一个题不太清楚啊

round2那个题能说的详细一些么？

最后一题rank是什么东东

楼主第一题shuffle字符是啥意思，能举个例子么？ 第四题是order statistic tree 吧，是平衡二叉树的augmentation，要求写代码了么，面试中根本不可能写完的

Ramily 发表于 2018-3-13 01:07
楼主请问第二题输入是什么结构呢？需要自己定义数据结构吗

同问第二题输入是什么？

第4轮是否可以考虑为一个bst，然后每个节点额外存上左树所有node的数量，这样就知道自己是第多少个了

所以就会都是log n

插入删除都是要回去更新父节点的对应的数量

haohao188 发表于 2018-3-12 07:12
楼主 最后一题 是不是个二叉树呢？多记录一些信息？

恩，是二叉树的变种