狗VO

匿名用户 发表于 2023-9-2 21:41
this is a brute force methods, not accepted

可是题目写了是list, list 删除元素(非末尾)只有O(n)做法吧 due to shifting
如果要转换成为linked list也需要initialization O(n)

盲猜面试官只是希望O(1) （not logn）生成random element in the list, 然后del部分O(n)?

请问楼主有何高见? 感谢！

匿名用户 发表于 2023-9-2 21:41
this is a brute force methods, not accepted

原题是一个前缀和，follow up感觉是在log(n)时间内完成删除+更新前缀和，估计套个线段树/binary indexed tree然后小改一下就能符合复杂度要求了

线段树能符合复杂度要求

祝lz有好消息，请问霍夫曼树那一题可能会出现出现这样的input：{'b': 3, 'e': 1, 'z': 3}，或者{'b': 2, 'e': 1, 'z': 3}吗？也就是构建完的树有叶子结点值为*的情况。谢谢！

齐晖互感器 发表于 2023-9-4 19:17
祝lz有好消息，请问霍夫曼树那一题可能会出现出现这样的input：{'b': 3, 'e': 1, 'z': 3}，或者{'b': 2, 'e ...

叶子结点值不会为*

请问1. 这个tree一定要是binary tree嘛？2. “Within the same length, sm‍‌‌‌‌‌‍‌‌‌‍‍‌‌‌‌‍‌‌aller values appear to the left of larger values (so 'b' to the left of 'z', etc.)” value指的是原letter的ascii code 的排序吗？

huffman只有叶子节点有值，为啥这个题e不在叶子节点啊

匿名用户 发表于 2023-09-03 09:20:25
原题是一个前缀和，follow up感觉是在log(n)时间内完成删除+更新前缀和，估计套个线段树/binary indexed tree然后小改一下就能符合复

应该是n（logn）^2。每次查询是对线段树范围查询（0， mid）范围的和，找到第一个大于random的范围，（logn）^2。删除时候更新单个节点，logn