grab interview

gistfile1.txt

#include <iostream>
#include <map>
#include <unordered_map>
#include <list>
#include <utility>
#include <cassert>
using namespace std;

struct LRU{
  const int maxn=2;
  unordered_map<int,list<pair<int,int>>::iterator>ma;
  list<pair<int,int>>li;
  int exist(int key){
      return ma.count(key);
  }
  void sanitycheck(){
      for(auto [a,b]:li){
          cout << a << " " << b << endl;
      }
      for(auto [a,b]:ma){
          cout << a << " " << b->first << " " << b->second << endl;
      }
      cout << "----\n";
  }
  void pointtolast(int key){
      auto it=li.end();
      it--;
      ma[key]=it;
  }
  int put(int key,int val){
      if(exist(key))get(key);
      else{
          li.push_back({key,val});
          pointtolast(key);
          if(li.size()>maxn){
              ma.erase(li.begin()->first);
              li.erase(li.begin());
          }
      }
  }
  int get(int key){
      if(!exist(key))return -1;
      auto it=ma[key];
      auto value=it->second;
      li.erase(it);
      li.push_back({key,value});
      pointtolast(key);
      return value;
  }
};
/*
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

*/

int main()
{
    
    LRU lru;
    lru.put(1,1);
    lru.put(2,2);
    cout << lru.get(1) << "\n";
    lru.sanitycheck();
    lru.put(3,3);
    lru.sanitycheck();
    cout << lru.get(2) << "\n";
    lru.sanitycheck();
    lru.put(4, 4);
    cout << lru.get(1) << "\n";
    cout << lru.get(3) << "\n";
    cout << lru.get(4) << "\n";
    return 0;
}