[LeetCode] 146. LRU Cache

• Problem: 實作 LRU Cache data structure and get/put operations
• Limitation: O(1) time complexity
• Note:
• get 與 put 都包含了 find 的 operation, 若需要 O(1), 則需要 hash table (unordered_map)
• insert 與 pop: 若 insert (push), pop 都是 push / pop back的話, linked list 或是 vector container 都可以達到 O(1) 的 complexity
• move: 但 LRU 包含了將最近使用的 entry 移動到 begin, 這只有 linked list 能達成
• 要明確了解 get/put 的動作, e.g. put 若是 put 同樣 key, 不同 value, 則 value 應更新
• Concept:
• 較無演算發的要求, 畢竟 LRU 本身就是演算法的概念
• 相當於在考 data structure design, 可知要實作 hash table 找 entry (key 做 hash, value 為 pointer to cache entry), 並用 linked list 來maintain cache entries (key, value) 的 pair
• Implementation:

• class LRUCache {
  public:
      LRUCache(int capacity) {
          m_capacity = capacity;
      }   
      
      int get(int key) {
          unordered_map >::iterator>::iterator it = m_hash.find(key);
          if (it != m_hash.cend())
          {   
              // move cache
              m_cache.splice(m_cache.begin(), m_cache, it->second);
              it->second = m_cache.begin();
              return it->second->second;
          }   
          else
              return -1; 
      }   
      
      void put(int key, int value) {
          // 1. find if it alread exists, if yes, move to begin, else insert it
          unordered_map >::iterator>::iterator it = m_hash.find(key);
          if (it != m_hash.cend()) {
              // move cache
              m_cache.splice(m_cache.begin(), m_cache, it->second);
              it->second = m_cache.begin();
              // Note: this value may differ from original one, we need to update value
              it->second->second = value;
          } else {
              // check if size reaches capacity
              if (m_cache.size() >= m_capacity) {
                  // a. remove cache entry
                  it = m_hash.find(m_cache.back().first);
                  //cout << "m_cache.back().first: " << m_cache.back().first << endl;
                  m_hash.erase(it);
                  // b. remove LRU
                  m_cache.pop_back();
              }
              m_cache.emplace(m_cache.begin(), make_pair(key, value));
              m_hash.insert(make_pair(key, m_cache.begin()));
          }
      }
  
  private:
      // O(1) to move, insert, delete nodes, we need list data structure
      // for the given data, we need a pair to store both key & value
      list< pair > m_cache;
  
      // max cache size
      int m_capacity;
  
      // for O(1) to find, we need a hash table which we use map here
      unordered_map >::iterator> m_hash;
  };