LruCache

/*
A Least Recently Used (LRU) Cache organizes items in order of use, allowing you to quickly identify which item hasn't been used for the longest amount of time.
An LRU Cache should support fast lookup. Apparently, in order to achieve fast lookup, we need to use Hashtable or HashMap.

Also, an LRU Cache requires that insert and delete operations should be in O(1) time. The obvious choice for this requirement is Linked List. Linked List support insert/delete operations in O(1) time if we have the reference of element.

While building an LRU cache requires that you think in terms of these two data structures. The reality is that these two data structures actually work coherently to achieve the design.

So, we are finalizing on these data structures: HashMap and Doubly Linked List
*/

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

class Lru{
    list<int> l;
    //for storing refrence of list elements
    unordered_map<int, list<int> :: iterator> m;
    int csize;            //maximum capacity of cache
    public:
        Lru(int n){
            csize=n;
        }
        void insert(int x){
            //not present in cache
            if(m.find(x) == m.end() ){
                //if cache is full
                if(l.size() == csize){
                    int last=l.back();
                    l.pop_back();
                    m.erase(last);
                }
            }
            //if present in cache
            else
                l.erase(m[x]);

            //updating refrence
            l.push_front(x);
            m[x]=l.begin();
        }

        void display(){
            for(auto it=l.begin(); it!=l.end(); it++)
                cout<<*it<<" ";
            cout<<endl;
        }
};

int main() {
    int size;
    cin>>size;
    Lru l(size);
    int no_of_elements;
    cin>>no_of_elements;
    for(int i=0; i<no_of_elements; i++){
        int x;
        cin>>x;
        l.insert(x);
    }
    l.display();

    return 0;
}