您现在的位置是:首页 > 网站心得网站心得

2019阿里巴巴技术专家面试题_LRU缓存机制_附带专家答案

2019-08-13【网站心得】人已围观

简介面试题 LRU缓存机制出题人 阿里巴巴技术专家 阿里云CDN技术专家题目:设计和实现一个 LRU(最近最少使用)缓存数据结构,使它应该支持一下操作: get 和 put。

面试题 LRU缓存机制

出题人 阿里巴巴技术专家 阿里云CDN技术专家

题目:

设计和实现一个 LRU(最近最少使用)缓存数据结构,使它应该支持一下操作: get 和 put。
get(key) - 如果 key 存在于缓存中,则获取 key 的 value(总是正数),否则返回 -1。
put(key,value) - 如果 key 不存在,请设置或插入 value。当缓存达到其容量时,它应该在插入新项目之前使最近最少使用的项目作废。

专家参考答案:


《 Python 版本 》
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.cache = {}
self.keys = []
self.capacity = capacity
def visit_key(self, key):
if key in self.keys:
self.keys.remove(key)
self.keys.append(key)
def elim_key(self):
key = self.keys[0]
self.keys = self.keys[1:]
del self.cache[key]
def get(self, key):
"""
:type key: int
:rtype: int
"""
if not key in self.cache:
return -1
self.visit_key(key)
return self.cache[key]
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if not key in self.cache:
if len(self.keys) == self.capacity:
self.elim_key()
self.cache[key] = value
self.visit_key(key)
def main():
s =
[["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[
4,4],[1],[3],[4]]]
obj = LRUCache(2)
l=[]
for i,c in enumerate(s[0]):
if(c == "get"):
l.append(obj.get(s[1][i][0]))
else:
obj.put(s[1][i][0], s[1][i][1])
print(l)
if __name__ == "__main__":
main()


《 C++版本 》
class LRUCache{
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
auto it = m.find(key);
if (it == m.end()) return -1;
l.splice(l.begin(), l, it->second);
return it->second->second;
}
void set(int key, int value) {
auto it = m.find(key);
if (it != m.end()) l.erase(it->second);
l.push_front(make_pair(key, value));
m[key] = l.begin();
if (m.size() > cap) {
int k = l.rbegin()->first;
l.pop_back();
m.erase(k);
}
 

这套技术题共计28题,这里为大家准备了pdf汇总,方便学习查看 
请点击下载 2019阿里巴巴技术专家面试题汇总(附带专家答案)

Tags:

很赞哦! ()

文章评论

    共有条评论来说两句吧...

    用户名:

    验证码:

站点信息

  • 建站时间:2019-05-01
  • 网站程序:帝国CMS7.5
  • 文章统计45篇文章
  • 微信公众号:关注最新拼团信息