员工软件工程师（电面贴）

qzxdoabe 发表于 2019-4-18 23:33
我去年初电面他家也被问到了这题。感觉最优解应该是PriorityQueue + HashMap。TreeMap 有个缺陷就是读写都 ...

Priorityqueue难道offer/poll/remove不都是logn么。。。
只有peek o1把。。

这个可以是，可以让印度人看不懂哈哈哈

fay1224 发表于 2019-5-1 16:55
Priorityqueue难道offer/poll/remove不都是logn么。。。
只有peek o1把。。

PriorityQueue 在这题里的作用仅仅是track谁是rank最低的。只有当要做删除操作的时候，才会需要logn，不会影响读。最为cache，读是最频繁的，所以读的时候一定要效率。
还有，编程语言里面的 PriorityQueue offer 和 poll 是 logN，但是remove 任意点是 N。当然这道题里面不会需要remove 任意点。

qzxdoabe 发表于 2019-5-2 22:32
PriorityQueue 在这题里的作用仅仅是track谁是rank最低的。只有当要做删除操作的时候，才会需要logn，不 ...

对啊 track rank最低 难道不是要offer么。。
offer就是logn啊。。。。
remove 头尾是logn。。

fay1224 发表于 2019-5-5 00:35
对啊 track rank最低 难道不是要offer么。。
offer就是logn啊。。。。
remove 头尾是logn。。

logN只是在remove和insert的时候，但是在正常读的时候只用到 HashMap，是常数。如果用 TreeMap 的话，每次读取都是需要 logN 的时间

qzxdoabe 发表于 2019-5-5 09:33
logN只是在remove和insert的时候，但是在正常读的时候只用到 HashMap，是常数。如果用 TreeMap 的话，每 ...

我不太明白你用 pq的思路。 我理解的是 pq size就是max size  满了就把最小的remove 再加新的
remove insert都是logn
treemap也是一样的。
也只是remove insert 读是从hashmap里读。
我是觉得pq 跟treemap 没有差。 从复杂度来说。

fay1224 发表于 2019-5-6 05:10
我不太明白你用 pq的思路。 我理解的是 pq size就是max size  满了就把最小的remove 再加新的
remove in ...

我最初评论是回复发帖作者的，以下是作者原文：

当时设计的时候就想到既然要排序的话，那就要用treeMap，当时就用treemap<K, Integer> map,前面一个存的是key，后面的一个存的是linkedlist index。然后在construct class写了个treemap的生成，内含一个compartor class，用数据的getRank排序。getItem方法和380类似，若果在treeMap里，直接返回list.get(map.get(key)); 如果不在而且treemap的大小不到evicitedNumber，从数据库里拿出，直接put进去；如果已经满， 拿出firstKey， 然后把那个index的item换成新的item， 然后把新的item加到treeMap，然后把旧的item删除。

作者用的是 TreeMap + LinkedList的做法，这种情况下读取时先要去 TreeMap 里查找，然后再去读对应 list 里的位置，时间复杂度是 logN.

qzxdoabe 发表于 2019-5-6 20:45
我最初评论是回复发帖作者的，以下是作者原文：

哦哦 如果用treemap + linkedlist  确实是。
我是用hashmap + treemap。