刚面完的Linkedin电面

[quote]liqingfd 发表于 2019-5-3 11:12
刚刚写了一个版本，跟楼上grandyang链接里面的差不多，欢迎指正!

1. import java.ut ...[/quote]
3. [hide=200]没必要用TreeMap吧，感觉PriorityQueue应该就够了吧？[code]public class RetainBestCache<K, T extends Rankable> {
   
4.         int entriesToRetain;
   
5.         HashMap<K, T> map = new HashMap<K,T>();
   
6.         PriorityQueue<Wrapper<K, T>> pq;
   
7.         DataSource<K,T> ds;
   
8. 
   
9.         /* Constructor with a data source (assumed to be slow) and a cache size */
   
10.         public RetainBestCache(DataSource<K,T> ds, int entriesToRetain) {
    
11.                 //impliment here
    
12.                 this.pq = new PriorityQueue<>(new Comparator<Wrapper>() {
    
13.                         public int compare(Wrapper w1, Wrapper w2) {
    
14.                                 return w1.data.getRank() - w2.data.getRank();
    
15.                         }
    
16.                 });
    
17.                 this.ds = ds;
    
18.                 this.entriesToRetain = entriesToRetain;
    
19.         }
    
20.         /* Gets some data. If possible, retrieves it from cache to be fast. If the data is not cached,
    
21.         * retrieves it from the data source. If the cache is full, attempt to cache the returned data,
    
22.         * evicting the T with lowest rank among the ones that it has available
    
23.         * If there is a tie, the cache may choose any T with lowest rank to evict.
    
24.         */
    
25.         public T get(K key) {
    
26.                 //impliment here
    
27.                 if (map.containsKey(key)) {
    
28.                         return map.get(key);
    
29.                 }
    
30.                 T data = DataSource.get(key);
    
31.                 if (map.size() < entriesToRetain) {
    
32.                         map.put(key, data);
    
33.                         pq.offer(new Wrapper(key, data));
    
34.                 } else {
    
35.                         evict();
    
36.                         map.put(key, data);
    
37.                         pq.offer(new Wrapper(key, data));
    
38.                 }
    
39.                 return data;
    
40.         }
    
41. 
    
42.         private evict() {
    
43.                 Wrapper leastRank = pq.poll();
    
44.                 map.remove(leastRank.key);
    
45.         }
    
46. }
    
47. 
    
48. class Wrapper<K, T> {
    
49.         T data;
    
50.         K key;
    
51. 
    
52.         public Wrapper(T data, K key) {
    
53.                 this.data = data;
    
54.                 this.key = key;
    
55.         }
    
56. }
    
57. 
    
58. /*
    
59. * For reference, here are the Rankable and DataSource interfaces.
    
60. * You do not need to implement them, and should not make assumptions
    
61. * about their implementations.
    
62. */
    
63. public interface Rankable {
    
64.         /**
    
65.         * Returns the Rank of this object, using some algorithm and potentially
    
66.         * the internal state of the Rankable.
    
67.         */
    
68.         long getRank();
    
69. }
    
70. 
    
71. public interface DataSource<K, T extends Rankable> {
    
72.         T get(K key);
    
73. }

复制代码

[/hide]

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

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

Falldawn 发表于 2021-6-11 11:13
找到了这个帖子https://www.1point3acres.com/bbs/thread-279704-1-1.html，这题应该用TreeMap因为Heap的re ...

Heap remove 的时间复杂度难道不是O（log n）

xhdt 发表于 2021-7-8 12:46
Heap remove 的时间复杂度难道不是O（log n）

显然不是，搜一下吧

Falldawn 发表于 2021-6-11 11:13
找到了这个帖子https://www.1point3acres.com/bbs/thread-279704-1-1.html，这题应该用TreeMap因为Heap的re ...

再看了下，两个MAP是需要的。

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

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

biomedicineman 发表于 2021-8-24 21:31
TreeMap.remove() 应该是logN吧？
PriorityQueue remove() max/min也是logN，但remove(object)是 O(N)

是的，因为TreeMap是平衡二叉树，而Heap只有上下级的大小关系

Falldawn 发表于 2021-8-25 07:31
是的，因为TreeMap是平衡二叉树，而Heap只有上下级的大小关系

恩恩，平时都没怎么关注TreeMap的实现

用
-HashMap keep k - v relation
-TreeSet or PriorityQueue  to keep the rank list

补充内容 (2021-09-08 09:58 +8:00):
TreeSet does not work

提问：如果不用java怎么写？