刚面完的Linkedin电面

jeh

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

电面介绍自己之后是两道题，一个是leetcode上 Nested list weight sum 那道，我做出来了。

但是第二道是一道cache设计题

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

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

现它不是, 这是题目是这样的，网上有答案

public class RetainBestCache<K, T extends Rankable> {
int entriesToRetain;
HashMap<K, T> map = new HashMap<K,T>();
DataSource<K,T> ds;
/* Constructor with a data source (assumed to be slow) and a cache size */
public RetainBestCache(DataSource<K,T> ds, int entriesToRetain) {
//impliment here
}
/* Gets some data. If possible, retrieves it from cache to be fast. If the data is not cached,
* retrieves it from the data source. If the cache is full, attempt to cache the returned data,
* evicting the T with lowest rank among the ones that it has available
* If there is a tie, the cache may choose any T with lowest rank to evict.
*/
public T get(K key) {
//impliment here
}
/*
* For reference, here are the Rankable and DataSource interfaces.
* You do not need to implement them, and should not make assumptions
* about their implementations.
*/
public interface Rankable {
/**
* Returns the Rank of this object, using some algorithm and potentially
* the internal state of the Rankable.
*/
long getRank();
}
public interface DataSource<K, T extends Rankable> {
T get(K key);
}

复制代码

密码

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

import java.ut ...[/quote]
[hide=200]没必要用TreeMap吧，感觉PriorityQueue应该就够了吧？[code]public class RetainBestCache<K, T extends Rankable> {
int entriesToRetain;
HashMap<K, T> map = new HashMap<K,T>();
PriorityQueue<Wrapper<K, T>> pq;
DataSource<K,T> ds;
/* Constructor with a data source (assumed to be slow) and a cache size */
public RetainBestCache(DataSource<K,T> ds, int entriesToRetain) {
//impliment here
this.pq = new PriorityQueue<>(new Comparator<Wrapper>() {
public int compare(Wrapper w1, Wrapper w2) {
return w1.data.getRank() - w2.data.getRank();
}
});
this.ds = ds;
this.entriesToRetain = entriesToRetain;
}
/* Gets some data. If possible, retrieves it from cache to be fast. If the data is not cached,
* retrieves it from the data source. If the cache is full, attempt to cache the returned data,
* evicting the T with lowest rank among the ones that it has available
* If there is a tie, the cache may choose any T with lowest rank to evict.
*/
public T get(K key) {
//impliment here
if (map.containsKey(key)) {
return map.get(key);
}
T data = DataSource.get(key);
if (map.size() < entriesToRetain) {
map.put(key, data);
pq.offer(new Wrapper(key, data));
} else {
evict();
map.put(key, data);
pq.offer(new Wrapper(key, data));
}
return data;
}
private evict() {
Wrapper leastRank = pq.poll();
map.remove(leastRank.key);
}
}
class Wrapper<K, T> {
T data;
K key;
public Wrapper(T data, K key) {
this.data = data;
this.key = key;
}
}
/*
* For reference, here are the Rankable and DataSource interfaces.
* You do not need to implement them, and should not make assumptions
* about their implementations.
*/
public interface Rankable {
/**
* Returns the Rank of this object, using some algorithm and potentially
* the internal state of the Rankable.
*/
long getRank();
}
public interface DataSource<K, T extends Rankable> {
T get(K key);
}

复制代码

[/hide]

Miaaaaa

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

但是这题priorityqueue只需要remove top，不需要remove specific object，所以用pq也是o(lgN)吧，而且实现上更简单？

biomedicineman

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)

Wyf2222

请问楼主怎么做的
Cache hit o(1) , cache miss tree map ologn 的方案面试官接受吗

jeh

Wyf2222 发表于 2019-2-22 09:51
请问楼主怎么做的
Cache hit o(1) , cache miss tree map ologn 的方案面试官接受吗

我没有做出来来，还没说到那个程度，我只找到这个网上的答案： https://www.cnblogs.com/apanda009/p/7945036.html

jeh

Wyf2222 发表于 2019-2-22 09:51
请问楼主怎么做的
Cache hit o(1) , cache miss tree map ologn 的方案面试官接受吗

没有出来

在网上找到这个答案： https://www.cnblogs.com/apanda009/p/7945036.html

Wu_kong

请问楼主是LRU 或者 LFU吗？

jeh

gui59106375 发表于 2019-2-22 11:44
请问楼主是LRU 或者 LFU吗？

不是的，我上面的链接给了网上的解法

Ellachen

用PriorityQueue也可以

WantBetterLife

谢谢楼主cache的分享

huntersjm

cache 这题很有意思，用最小堆实现吗？超过size把堆顶remove掉，把新的add进去

liqingfd

刚刚写了一个版本，跟楼上grandyang链接里面的差不多，欢迎指正!

import java.util.*;
public class RetainBestCache<K, T extends RetainBestCache.Rankable> {
int entriesToRetain;
Map<K, T> keyValueMap; // map<key, val>
Map<Long, List<K>> rankKeyMap; // map<rank, list<key>>
DataSource<K, T> ds;
/* Constructor with a data source (assumed to be slow) and a cache size */
public RetainBestCache(DataSource<K, T> ds, int entriesToRetain) {
this.keyValueMap = new HashMap<>();
this.rankKeyMap = new TreeMap<>();
this.ds = ds;
this.entriesToRetain = entriesToRetain;
}
/* Gets some data. If possible, retrieves it from cache to be fast. If the data is not cached,
* retrieves it from the data source. If the cache is full, attempt to cache the returned data,
* evicting the T with lowest rank among the ones that it has available
* If there is a tie, the cache may choose any T with lowest rank to evict.
*/
public T get(K key) {
if (keyValueMap.containsKey(key)) {
return keyValueMap.get(key);
}
T val = ds.get(key);
keyValueMap.put(key, val);
rankKeyMap.put(val.getRank(), new ArrayList<>());
rankKeyMap.get(val.getRank()).add(key);
while (keyValueMap.size() > entriesToRetain) {
Long lowestRank = rankKeyMap.keySet().iterator().next();
K k = rankKeyMap.get(lowestRank).get(0);
rankKeyMap.get(lowestRank).remove(0);
if (rankKeyMap.get(lowestRank).size() == 0) {
rankKeyMap.remove(lowestRank);
}
keyValueMap.remove(k);
}
return val;
}
/*
* For reference, here are the Rankable and DataSource interfaces.
* You do not need to implement them, and should not make assumptions
* about their implementations.
*/
public interface Rankable {
/**
* Returns the Rank of this object, using some algorithm and potentially
* the internal state of the Rankable.
*/
long getRank();
}
public interface DataSource<K, T extends Rankable> {
T get(K key);
}
}

复制代码

补充内容 (2019-5-5 06:04):
line 28写错了，应该先判断一下map里面有没有这个key再put的。

刚面完的Linkedin电面

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

浏览过的版块