CareerCup

two important things to consider:
1. To find out if an entry is already there in the cache or not should be fast. Linear time search will not do.
2. If the cache is full then we need to remove the oldest entry from the cache when a new entry is about to be fetched from the disk when this entry could not be found in the cache.

So, to solve these two issues we need two data structures.
1. Hash map : This will have (key, value) pair. key is some unique id associated with the actual object. While value here is reference to the corresponding entry in a doubly linked list structure. Searching for a key in hash map will be of O(log n).

2. Doubly linked list: maintain head and tail pointers. Each node will have key, data, prev_pointer and next_pointer as attributes.
Whenever an entry (key) is searched in the hashmap, following two cases can happen:
a) entry is not found:
- fetch the object from the disk
- create node structure to be inserted in the DLL
- add this node at the front of the DLL.
- add (key, reference_to_node_in_dll) pair in hashmap
b) entry is found in the hashmap
- use the reference for the key to traverse to the node containing the object in DLL
- adjust the prev and next pointers of the nodes to make it a front node of the DLL
purpose of this exercise to move the node which is not being accessed or the least recently used one to the end of the DLL.

Now, whenever the cache is full and we have to add an entry in the hashmap:
- delete the node pointed by tail in DLL ( as this is the least recently used node) and using the key value remove the entry in the hashmap as well.
- fetch the object, create a node for DLL and add it at the front
- add (key, reference_to_node_in_dll) pair in the hashmap

This way we can implement an LRU which will handle all the possible scenarios.

you can use a queue with the delete function. add recently used pages from back of the queue and remove pages from the front. if you need to add a page to the end which is in the middle of the queue, then delete this node from the queue, copy it and add it to the back of the queue

import java.util.*;

class DoubleLinkNode{
	int key;
	DoubleLinkNode next;
	DoubleLinkNode prev;
	DoubleLinkNode(int key){
		this.key = key;
		next = null;
		prev = null;
	}
}

public class LRUCache{
	private HashMap<Integer,DoubleLinkNode> map = new HashMap<Integer,DoubleLinkNode>();
	private DoubleLinkNode head = null;
	private DoubleLinkNode end = null;
	private DoubleLinkNode temp = null;
	private static final int MAX_LIMIT = 6;
	private int totalElements = 0;

	void insert(int key){
		if(totalElements >= MAX_LIMIT ){
			//System.out.println("Limit");
			end = end.prev;
			end.next = null;
			//System.out.println("end : "+end.key);
			totalElements--;
			insert(key);
		}else{
			if(head == null){
				head = end = new DoubleLinkNode(key);
				map.put(key,head); 
			}else{
				temp = new DoubleLinkNode(key);
				temp.next = head;
				head.prev = temp;
				head = temp;
				map.put(key,head);			
			}
			totalElements++;
		}
	}

	void get(int key){
		temp = map.get(key);
		if(temp != null){
			if(key == head.key){
				return;
			}
			temp.prev.next = temp.next;
			if(key != end.key){
				temp.next.prev = temp.prev;
			}
			temp.prev = null;
			temp.next = head;
			head.prev = temp;
			head = temp;			
		}else{
			//System.out.println("inside");
			insert(key);
		}
	}

	void check(){
		System.out.println("checking next");
		temp = head;
		while(temp!=null){
			System.out.println(temp.key);
			temp = temp.next;
		}
		/*System.out.println("checking prev");
		temp = end;
		while(temp!=null){
			System.out.println(temp.key);
			temp = temp.prev;
		}*/
	}

	void run(){
		for(int i = 1 ; i <= 12; i+=2){
			//check fucniton is used for checking elements are 
			//inserted right in doubly linked list
			get(i);
		}
		System.out.println("Checking all 6 elments");
		check();
		get(3);
		System.out.println("chcking already inserted elemnt 3");
		check();
		System.out.println("checking extra elemnt insert");
		get(13);		
		check();
		get(14);
		check();
		get(14);
		check();
		get(7);
		check();
	}	

	public static void main(String args[]){
		LRUCache obj = new LRUCache();
		obj.run();
	}
}

C++ solution using hash map & doubly linked list of standard library.

#include <iostream>
#include <list>
#include <unordered_map>
#include <memory>
#include <cassert>

using namespace std;

class lru_cache {
	struct cache_entry {
		int key;
		shared_ptr<string> val;
	};
	const unsigned max_elem = 3;
	mutable list<cache_entry> cache_;
	mutable unordered_map<int,list<cache_entry>::iterator> map_;

public:
	shared_ptr<string> get(int key) const;
	void set(int key, shared_ptr<string> val);
};

shared_ptr<string> lru_cache::get(int key) const {
	auto r = map_.find(key);
	if (r != map_.end()) {
		// cache_.push_front(*(r->second));
		// cache_.erase(r->second);
		cache_.splice(cache_.begin(), cache_, r->second);
		map_[key] = cache_.begin();
		return cache_.begin()->val;
	}
	else {
		return shared_ptr<string>();
	}
}

void lru_cache::set(int key, shared_ptr<string> val) {
	if (cache_.size() >= max_elem) {
		map_.erase(cache_.back().key);
		cache_.pop_back();
	}
	cache_.push_front({key, val});
	map_[key] = cache_.begin();
}

int main() {
	lru_cache cache;
	cache.set(1, make_shared<string>("abcd"));
	cache.set(2, make_shared<string>("bcde"));
	cache.set(3, make_shared<string>("cdef"));
	cache.set(4, make_shared<string>("defg"));
	assert(cache.get(2) && *cache.get(2) == "bcde");
	cout << *cache.get(2) << endl;
	assert(cache.get(3) && *cache.get(3) == "cdef");
	cout << *cache.get(3) << endl;
	assert(cache.get(4) && *cache.get(4) == "defg");
	cout << *cache.get(4) << endl;
	assert(!cache.get(1));
	assert(!cache.get(5));
	cache.set(5, make_shared<string>("efgh"));
	assert(!cache.get(2));
	assert(cache.get(3));
	assert(cache.get(4));
	assert(cache.get(5));
	
	return 0;
}

The time complexity for the implementation using 2 data structure hash_map and doubly linked list is the following:

1) if page doesn't exist in memory, it takes o(1)+o(1) = o(1) time
2) if page already in memory, it takes o(1)+o(n) = o(n).

which comes to our question, what is the data distribution pattern (page visiting pattern)? how big is our memory cache?

If the answer is that most of the time, page hit is already cached (we have a big cache or user just use a handful of pages / functionality - this is highly dependent on the nature of the system being developed i.e. is it a news focused or trading related environment?

Anyway, if this is the case, a simple map data structure will do the job nicely. And the time complexity is a constant o(log(n)) - much better than the previous implementation's linear time o(n).

In C++, can make use of Hash Map and Doubly Linked List

There is the same problem on LeetCode. Write some code and test it.

class LRUCache{
private:
    list<int> _Cache; // node(value)
    unordered_map<int, list<int>::iterator> _Map; // key->node
    int _Capacity;
public:
    LRUCache( int capacity ) {
        _Capacity = capacity;
    }
    
    int get( int key ) {
        /* Found */
        if( _Map.find( key ) != _Map.end() ){
            list<int>::iterator it = _Map[key];
            int value = *it;
            _Cache.erase( it );
            _Cache.push_front( value );
            _Map[key] = _Cache.begin();
            return value;
        }
        
        /* Not found */
        else{
            return -1;
        }
    }
    
    void set( int key, int value ) {
        /* Found */
        if( _Map.find( key ) != _Map.end() ){
            list<int>::iterator it = _Map[key];
            _Cache.erase( it );
        }
        
        /* Not found */
        else{
            if( _Cache.size() == _Capacity ){
                list<int>::iterator it = _Cache.end(); // Past-the-end element
                it--;
                /* Find in _Map and delete it */
                for( auto mapIt = _Map.begin(); mapIt != _Map.end(); ++mapIt ){
                    if( mapIt->second == it ){
                        _Map.erase( mapIt );
                        break;
                    }
                }
                _Cache.erase( it );
            }
        }
        
        /* Insert new element */
        _Cache.push_front( value );
        _Map[key] = _Cache.begin();
    }
};

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    class Program
    {
        static void Main(string[] args)
        {
            var nodeMap = new Dictionary<int, Node>();
            var list = new LinkedList();
            int T = Int32.Parse(Console.ReadLine().Trim());
            while(T-- > 0)
            {
                int action = Int32.Parse(Console.ReadLine().Trim());
                if(action == 1)
                {
                    int data = Int32.Parse(Console.ReadLine().Trim());
                    if(!nodeMap.ContainsKey(data))
                    {
                        nodeMap.Add(data, list.InsertFront(data));
                    }
                    else
                    {
                        list.Delete(nodeMap[data]);
                        nodeMap.Remove(data);
                        nodeMap.Add(data, list.InsertFront(data));
                    }
                }
                else
                {
                    list.Print();
                }
            }
            Console.ReadLine();
        }
    }
    public class LinkedList
    {
        public Node root;
        public LinkedList()
        {
            root = null;
        }
        public Node InsertFront(int val)
        {
            Node temp = new Node(val);
            temp.right = root;
            if(root != null)
            {
                root.left = temp;
            }
            root = temp;
            return temp;
        }

        public void Delete(Node temp)
        {
            if(temp.right != null)
            {
                temp.right.left = temp.left;
            }
            if(temp.left != null)
            {
                temp.left.right = temp.right;
            }
        }
        public void Print()
        {
            Node temp = root;
            while(temp != null)
            {
                Console.Write("{0} -> ", temp.val);
                temp = temp.right;
            }
            Console.WriteLine();
        }
    }
    public class Node
    {
        public int val;
        public Node left;
        public Node right;
        public Node(int data)
        {
            val = data;
            left = null;
            right = null;
        }
    }
}