Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class LRUCache
{
private readonly int _capacity;
private readonly IDictionary<int, LinkedListNode<Tuple<int, int>>> _store = new Dictionary<int, LinkedListNode<Tuple<int, int>>>();
private LinkedList<Tuple<int, int>> _accessLog = new LinkedList<Tuple<int, int>>();
public LRUCache(int capacity)
{
_capacity = capacity;
}
public int Get(int key)
{
LinkedListNode<Tuple<int, int>> val;
if(_store.TryGetValue(key, out val))
{
_accessLog.Remove(val);
_accessLog.AddLast(val);
return val.Value.Item2;
}
return -1;
}
public void Put(int key, int value)
{
var val = new LinkedListNode<Tuple<int, int>>(Tuple.Create(key, value));
if(!_store.ContainsKey(key))
{
if(_store.Count == _capacity)
{
_store.Remove(_accessLog.First.Value.Item1);
_accessLog.RemoveFirst();
}
_store.Add(key, val);
_accessLog.AddLast(val);
}
else
{
var previousValue = _store[key];
_accessLog.Remove(previousValue);
_store[key] = val;
_accessLog.AddLast(val);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.