刚面完的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]

找到了这个帖子https://www.1point3acres.com/bbs/thread-279704-1-1.html，这题应该用TreeMap因为Heap的remove操作是O(n)，用一个HashMap作为cache记录<Key, Value>，用一个TreeMap来记录rank对应的Set of Value

如果multi thread会有什么问题，该如何处理?

1. 
   
2. public class RetainBestCache<K, T extends Rankable> {
   
3.      private Map<K, T> cacheMap;
   
4.      private TreeMap<Long, Set<K>> rankMap;
   
5.      private DataSource<K, T> dataSource;
   
6.      private int maxSizeOfCache;
   
7. 
   
8.     /* Constructor with a data source (assumed to be slow) and a cache size */
   
9.     public RetainBestCache(DataSource<K,T> ds, int entriesToRetain) {
   
10.         // Implementation here
    
11.         cacheMap = new HashMap<>();
    
12.         rankMap = new TreeMap<>();
    
13.         dataSource = ds;
    
14.         maxSizeOfCache = entriesToRetain;
    
15.     }
    
16. 
    
17.     /* Gets some data. If possible, retrieves it from cache to be fast. If the data is not cached,
    
18.      * retrieves it from the data source. If the cache is full, attempt to cache the returned data,
    
19.      * evicting the T with lowest rank among the ones that it has available
    
20.      * If there is a tie, the cache may choose any T with lowest rank to evict.
    
21.      */
    
22.     public T get(K key) {        
    
23.         if (cacheMap.containsKey(key)) {        
    
24.           return cacheMap.get(key);
    
25.         }
    
26.         return fetchDataFromDs(key);
    
27.     }
    
28. 
    
29.     private T fetchDataFromDs(K key) {
    
30.        if(cacheMap.size() > maxSizeOfCache) {
    
31.           evictElement();
    
32.         }
    
33.         T curValue = dataSource.get(key);
    
34.         cache.put(key, curValue);
    
35.         long curRank = curValue.getRank();      
    
36.         rankMap.putIfAbsent(curRank, new HashSet<>());      
    
37.         rankMap.get(curRank).add(key);
    
38.         return curValue;
    
39.     }
    
40. 
    
41.     private void evictElement() {
    
42.       Entry<Long, Set<K>> entry = rankMap.firstEntry();//It returns an entry with the least key and null if the map is empty.
    
43.       K key = entry.getValue().iterator().next();
    
44.       entry.getValue().remove(key);
    
45.       cacheMap.remove(key)
    
46.       if(entry.getValue().size() == 0) {
    
47.         rankMap.remove(entry.getKey());
    
48.       }
    
49.     }
    
50. }
    
51. 
    
52. // What if rank is defined as the number of reads of elements in cache?
    
53. // LRU
    
54. // Let's assume that rank can change dynamically. It is not immutable, but it is not LRU. We do not know how it is changed
    
55. 
    
56. 
    
57. /*
    
58. * For reference, here are the Rankable and DataSource interfaces.
    
59. * You do not need to implement them, and should not make assumptions
    
60. * about their implementations.
    
61. */
    
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. }
    

复制代码

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是需要的。

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

TreeMap.remove() 应该是logN吧？
PriorityQueue remove() max/min也是logN，但remove(object)是 O(N)

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怎么写？