--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/grok_interview/LRU.py	Mon Dec 15 19:55:17 2025 -0800
@@ -0,0 +1,46 @@
+from typing import Optional
+
+
+class Node:
+    def __init__(self, key, value):
+        self.key = key
+        self.value = value
+        self.next: Optional[Node] = None
+        self.prev: Optional[Node] = None
+
+class LRUCache:
+
+    def __init__(self, capacity: int):
+        self.capacity = capacity
+        self.map = {}
+        self.head = Node(-1, -1)
+        self.tail = Node(-1, -1)
+        self.head.next, self.tail.prev = self.tail, self.head
+
+    def get(self, key: int) -> int:
+        if not key in self.map:
+            return -1
+        node = self.map[key]
+        self._deleteAndAdd(node)
+        return node.value
+        
+    def put(self, key: int, value: int) -> None:
+        newNode = Node(key, value)
+        if key in self.map:
+            self._delete(self.map[key])
+        else:
+            if len(self.map.keys())+1 > self.capacity:
+                del self.map[self.head.next.key]
+                self._delete(self.head.next)
+        self._add(newNode)
+        self.map[key] = newNode
+
+    def _deleteAndAdd(self, node):
+        self._delete(node)
+        self._add(node)
+
+    def _delete(self, node):
+        node.prev.next, node.next.prev = node.next, node.prev
+
+    def _add(self, node):
+        node.prev, node.next, self.tail.prev.next, self.tail.prev = self.tail.prev, self.tail, node, node