Coding interviews
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
var cache = new Lru(2); cache.Put("a", 1); cache.Put("b", 2); cache.TryGet("a", out _); cache.Put("c", 3);
Console.WriteLine("b present:" + cache.TryGet("b", out _).ToString().ToLowerInvariant());
cache.Put("a", 9); Console.WriteLine("order:" + cache.Keys()); cache.TryGet("a", out int value); Console.WriteLine("a:" + value);
sealed class Lru {
private readonly int capacity; private readonly LinkedList<(string Key,int Value)> order = new();
private readonly Dictionary<string,LinkedListNode<(string Key,int Value)>> map = new(StringComparer.Ordinal);
public Lru(int capacity) { if (capacity <= 0) throw new ArgumentOutOfRangeException(nameof(capacity)); this.capacity = capacity; }
public void Put(string key, int value) { if (map.TryGetValue(key, out var node)) { node.Value = (key,value); order.Remove(node); order.AddFirst(node); return; }
if (map.Count == capacity) { var old = order.Last!; map.Remove(old.Value.Key); order.RemoveLast(); }
map.Add(key, order.AddFirst((key,value))); }
public bool TryGet(string key, out int value) { if (!map.TryGetValue(key,out var node)) { value=0; return false; } order.Remove(node); order.AddFirst(node); value=node.Value.Value; return true; }
public string Keys() => string.Join(",",order.Select(x=>x.Key));
}
Reveal answer and reasoning
The output lines, in order, are “b present:false”; “order:a,c”; “a:9”. After inserting a and b, reading a moves it to the front. Inserting c then evicts b. Updating a to nine changes the existing node rather than creating a second entry; the order becomes a,c. The final read retrieves nine. The Boolean miss return keeps a missing value distinct from a stored zero.
Updating a calls Remove with the node already retrieved from the dictionary, then AddFirst with that same node. Its identity remains stable while its payload changes. A failed lookup of b returns false without moving another entry, and retrieving a zero value would still return true for an existing node.
A dictionary points directly to linked-list nodes, so lookup, unlinking and moving a known node require expected constant time. Insertion can allocate a node and dictionary growth can resize storage. Space is O(capacity) entries, but that entry bound is not a bound on key bytes or total process memory. Calling LinkedList.Remove by value would search, losing the intended constant-time move.
Failing to remove an evicted key from the dictionary breaks the two-structure invariant. Enumeration order of the dictionary is irrelevant because the list defines recency. Shared access would require synchronization around both structures together.
What a strong answer covers
- Exact output: b present:false | order:a,c | a:9
- After inserting a and b, reading a moves it to the front.
- Calling LinkedList.Remove by value would search, losing the intended constant-time move.
Common pitfall
Calling LinkedList.Remove by value would search, losing the intended constant-time move. Failing to remove an evicted key from the dictionary breaks the two-structure invariant. Enumeration order of the dictionary is irrelevant because the list defines recency. Shared access would require synchronization around both structures together.
Follow-up questions
- Test capacity one, updating an existing key, a missing read and storing zero. Hint: updates should not evict an unrelated key or increase the count. After each operation compare the dictionary membership with the keys in the recency list.
- How would capacity zero differ from a cache entry whose stored value is zero?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.