滚烫的数据砖头电面

刚面的数据转头，题目很简单，设计一个数据结构，能支持高效的insert/delete/query 操作，这个数据结构是用来支持文本编辑器

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

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

gt; b
delete(1)
read(1)->c


求大米求大米求大米

我一朋友从内部题库看到这题了，其实大家都被误导了。小提示：不要去实现什么平衡树了，用bucket算法就行，比如用个5个元素的bucket，那算法是O(N/5)。这就算sub-linear

太卷了，电面面这么难的。。。

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

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

请问下楼主是要用线段树做么？
insert 和delete的时候索引位置都要相应的移动， 怎么才能sub-linear呢？

同問 樓主是用什麼数据结构做的？看起來不簡單啊...

你这个面的看起来和我的差不多，其实比我的简单很多。

dirtydoll 发表于 2020-11-10 02:57
你这个面的看起来和我的差不多，其实比我的简单很多。

请问您面的是什么题呢？ 我感觉楼主这个看起来不是很简单，是我miss 什么了，您有什么思路么？

sub-linear的意思是说少于O(n)吗？

应该是：https://en.wikipedia.org/wiki/Rope_(data_structure)

和手写红黑树或者AVL tree一样， 纯粹有病。

B+树肯定可以，那些操作都是数据库常规操作。