It was told that cache will have a key, value pair(int, int).
Solution is to take hash with key as cache key and value is Node where Node is the address of the node in the linked list which contains the same key. Linked list node contains cache key and cache value.
Insert Operation --
- Make a node "Node" with key and value and put that node at the end of linked list.
- if count of nodes are more than cache size then remove head node from linked list , also remove hash[head->key].
- Update hash as hash[Node->key] = Node
Get Operation --
- Get operation will return the cache value of given cache key. Also now it will make this key is the most recently used one.
- Get the Node by hash[key] and move that Node at the end of linked list.
- Return hash[key]->value.
Implementation in C#:
public class LRUCache
{
public LRUCache(int capacity)
{
this.currentCount = 0;
this.cacheCapacity = capacity;
this.list = new LinkedList<KeyValuePair<int, int>>();
this.hash = new Dictionary<int, LinkedListNode<KeyValuePair<int, int>>>();
}
public int Get(int key)
{
if (hash.ContainsKey(key))
{
list.Remove(hash[key]);
list.AddLast(hash[key]);
return hash[key].Value.Value;
}
return -1;
}
public void Put(int key, int value)
{
if (hash.ContainsKey(key))
{
hash[key].Value = new KeyValuePair<int, int>(key, value);
list.Remove(hash[key]);
list.AddLast(hash[key]);
}
else
{
if (currentCount + 1 > cacheCapacity)
{
LinkedListNode<KeyValuePair<int, int>> linkedListNode = list.First;
list.RemoveFirst();
hash.Remove(linkedListNode.Value.Key);
}
else
{
++currentCount;
}
LinkedListNode<KeyValuePair<int, int>> newNode = new LinkedListNode<KeyValuePair<int, int>>(new KeyValuePair<int, int>(key, value));
list.AddLast(newNode);
hash.Add(key, newNode);
}
}
Dictionary<int, LinkedListNode<KeyValuePair<int, int>>> hash;
LinkedList<KeyValuePair<int, int>> list;
private int cacheCapacity;
private int currentCount;
}
