黑车公司面经

第二题利用一个log记录就好了嘛，
开一个linked list，每次insert/update 都在最后append一个(key, value, maxNow)的 tuple，delete就append一个(key, NaN, maxNow) 就行
query就从后往前扫咯，反正对query 没有性能要求

mimighost007 发表于 2017-7-25 16:41
这题有坑。如果这种数据结构存在的话，那就可以设计出O(n)的排序算法。

首先insert所有元素，这个按照 ...

可以参考我楼上回复，这个数据结构对get没有要求，所以还是可以设计的

ivanyang 发表于 2017-7-25 17:07
可以参考我楼上回复，这个数据结构对get没有要求，所以还是可以设计的

这个有问题，假设最开始insert的是最大的元素，你记录的所有maxNow都是这一个值，delete这个max之后，必须要遍历整个log来找出下一个max。那就不是常数级别了。

mimighost007 发表于 2017-7-26 00:43
这个有问题，假设最开始insert的是最大的元素，你记录的所有maxNow都是这一个值，delete这个max之后，必 ...

是不是可以用min stack 的思路？

面试的时候可以试试这么圆过去
max()用任何一个算法实现，把结果存在一个地方
每次query都是O(1), 后台再找下一个max；这个后台操作的时间题目没有明确要求

补充内容 (2017-7-26 04:26):
应该是每次insert(), delete(), update()之后，max()后台update
否则连续insert N个数然后连续max, delete N 次，O(N) 就完成排序了

全O(1)那道问题我怀疑有些潜在的假设他并没告诉你。如果value是integer且落在某个不是特别大的范围内可以开数组count每个值出现的次数，insert, update, delete的时候去操作counter数组，用一个max变量指向counter数组里不为零的最大index。如果value是任意值的话基本上应该是没法做到始终O(1)的，或者他能保证max只会被call一次

lqs4188980 发表于 2017-7-26 14:20
全O(1)那道问题我怀疑有些潜在的假设他并没告诉你。如果value是integer且落在某个不是特别大的范围内可以开 ...

但是一旦最大值被delete了，寻找下一个max的index 也可能是O(N)的

LZ 这个system design有啥想法吗，如何来生成推荐算法呢

想问下楼主,  第三轮,  推荐recommendation app, 楼主是怎么设计的

mimighost007 发表于 2017-7-25 16:41
这题有坑。如果这种数据结构存在的话，那就可以设计出O(n)的排序算法。

首先insert所有元素，这个按照 ...

对啊, 就像要求不用额外空间, 设计一个玄学排序算法, O(N)完成.