ARTS-Week-8

发表于 分类于 Disqus： 本文字数： 3k 阅读时长 ≈ 3 分钟

第八周

  • Alogrithm:LRU Cache
  • Reading:AWS re:Invent 2018: Running Serverless at The Edge (CTD302)
  • Tech:DNS探秘
  • Share:clion远程调试指南

Alogrithm

题目—LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

首先，对于cache，如果希望有O(1)的查找复杂度，肯定要用hashmap来保存key和对象的映射。同时用双向链表构建LRU很方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

struct LRUNode {
  LRUNode *pre = nullptr;
  LRUNode *next = nullptr;
  int key;
  int val;
};

class LRUCache {
 public:
  LRUCache(int capacity);
  int get(int key);
  void put(int key, int value);
 private:
  void ToTop(std::unordered_map<int, LRUNode*>::iterator it);
  int cap = 0;
  LRUNode *first = nullptr;
  LRUNode *last = nullptr;
  std::unordered_map<int, LRUNode*> nodemap;
};

LRUCache::LRUCache(int capacity){
 cap = capacity;
}

int LRUCache::get(int key) {
  auto it = nodemap.find(key);
  if (it != nodemap.end()) {
    ToTop(it);
    return it->second->val;
  }
  return -1;
}

void LRUCache::put(int key, int value) {
  auto it = nodemap.find(key);
  if (it != nodemap.end()) {
    ToTop(it);
    it->second->val = value;
    return;
  }
  LRUNode* new_node = new LRUNode;
  new_node->key = key;
  new_node->val = value;
  new_node->next = first;
  new_node->pre = nullptr;
  if(first) {
    first->pre = new_node;
  }
  if (nodemap.size() < cap) {
    nodemap.insert(std::make_pair(key, new_node));
    first = new_node;
    if (!last) last = new_node;
  } else if (last) {
    nodemap.erase(last->key);
    if(last->pre) last->pre->next = nullptr;
    auto tmp = last;
    last = last->pre;
    delete(tmp);
    nodemap.insert(std::make_pair(key, new_node));
    first = new_node;
  }
  return;
}

void LRUCache::ToTop(std::unordered_map<int, LRUNode*>::iterator it) {
  auto node = it->second;
  if (!node->pre) return;
  auto temppre = node->pre;
  node->pre = nullptr;
  temppre->next = node->next;
  if (node->next) node->next->pre = temppre;
  node->next = first;
  first->pre = node;
  first = node;
  if (last == node) last = temppre;
  return;
}

Tips:

Reading

AWS re:Invent 2018: Running Serverless at The Edge (CTD302)
AWS的边缘计算实践

Tech

DNS探秘：DNS探秘

Share

clion远程调试指南