Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 28, 2016 21:32
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/3dc7da7e0465819e6aa8c10c71901723 to your computer and use it in GitHub Desktop.
Save jianminchen/3dc7da7e0465819e6aa8c10c71901723 to your computer and use it in GitHub Desktop.
LRU - Least Recently Used Cache - C# code implementation with one test case
/**
* @see <a href="https://leetcode.com/problems/lru-cache/">LRU Cache</a>
*
* Julia, work on C# version
*/
using System.Collections.Generic;
public class LRUCache
{
class ListNode
{
public int key, val;
public ListNode prev, next;
public ListNode(int k, int v)
{
key = k;
val = v;
prev = null;
next = null;
}
}
private int capacity, size;
private ListNode dummyHead, dummyTail;
// private Map<Integer, ListNode> map; Java code
private Dictionary<int, ListNode> map;
public bool argumentOk = true;
public LRUCache(int capacity)
{
if (capacity <= 0)
{
//throw new IllegalArgumentException("Positive capacity required.");
argumentOk = false;
return;
}
this.capacity = capacity;
size = 0;
dummyHead = new ListNode(0, 0);
dummyTail = new ListNode(0, 0);
dummyTail.prev = dummyHead;
dummyHead.next = dummyTail;
map = new Dictionary<int, ListNode>();
}
public int get(int key)
{
if (!map.ContainsKey(key))
{
return -1;
}
ListNode target = map[key];
remove(target);
addToLast(target);
return target.val;
}
public void set(int key, int value)
{
if (map.ContainsKey(key))
{ // update old value of the key
ListNode target = map[key];
target.val = value;
remove(target);
addToLast(target);
}
else
{ // insert new key value pair, need to check current size
if (size == capacity)
{
map.Remove(dummyHead.next.key);
remove(dummyHead.next);
--size;
}
ListNode newNode = new ListNode(key, value);
map.Add(key, newNode);
addToLast(newNode);
++size;
}
}
private void addToLast(ListNode target)
{
target.next = dummyTail;
target.prev = dummyTail.prev;
dummyTail.prev.next = target;
dummyTail.prev = target;
}
private void remove(ListNode target)
{
target.next.prev = target.prev;
target.prev.next = target.next;
}
public static void Main(string[] args)
{
LRUCache cache = new LRUCache(4);
int[][] keyValuePair = new int[5][]{
new int[2]{1,1},
new int[2]{2,1},
new int[2]{3,1},
new int[2]{4,1},
new int[2]{5,1}
};
for (int i = 0; i < 4; i++ )
cache.set(keyValuePair[i][0], keyValuePair[i][1]);
int value = cache.get(1); // key 1 is in LRU, so the value is 1; and also 1 is visited, then, remove key 1, and add key 1 to to last one instead.
cache.set(keyValuePair[4][0], keyValuePair[4][1]); // should remove key 1, but 1 is visited recently; 2 is one to remove.
int value2 = cache.get(1); // return 1
int value3 = cache.get(2); // return -1
int value4 = cache.get(3);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment