数据砖 电面挂经

面试官中年大叔. 10mins 简历。之后 要是design 一种数据结构 类似StringBuilder 实现 insert(char ch,

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

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

delete时间复杂度, 不会做。面完复盘，面试官给的hints把我往块状链表上引。

请问hashmap+doubly linkedlist 为什么不是O(1)

大家有什么好办法吗？
看其他面经说要求这三个操作都要better than O(N)？ 如果用块状链表的话read()好像就是O(N)啊，能符合要求吗？

匿名者 发表于 2020-12-12 12:21
请问hashmap+doubly linkedlist 为什么不是O(1)

因为插入删除 操作会改变插入位 之后字符的index.  

store the string in Segment tree. each opearation will be log(N) + maintain the tree(logN). kind of impossible to implment in the interview

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

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

关于如何根据字符串建立BST，如果字符串本身是随机生成的，那么可以根据每个字符的value作为bst的生成条件，如果不是随机生成，那么可以for i =0; i<size(); i++, gen_val[i] = rand(); 来对于每个index随机生成一个value，这样保证一开始生成的BST是balanced。当然也可以直接套用size balanced tree。

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

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

denghuixing 发表于 2021-2-4 05:35
块状链表相当于一个只有两层的低配B树吧，所以肯定是比O(N)低的
你每次找index都是先找第一层找block， ...

每个block都只有一个element咋办。。。还是O(n)呀。。

denghuixing 发表于 2021-2-4 05:35
块状链表相当于一个只有两层的低配B树吧，所以肯定是比O(N)低的
你每次找index都是先找第一层找block， ...

块状链表的大小=sqrt(n), n是元素的总个数?