Grok - X - x.ai - ML Engineer Phone Interview

class Node:
    def __init__(self, key=0, value=None, size=0):
        self.key = key
        self.value = value
        self.size = size
        self.prev = None
        self.next = None

class SizedLRUCache:
    def __init__(self, max_size: int):
        self.max_size = max_size
        self.current_size = 0
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_node(self, node):
        """Add node after head (MRU)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        """Remove node from list."""
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev
    
    def _move_to_head(self, node):
        """Move node to head (MRU)."""
        self._remove_node(node)
        self._add_node(node)
    
    def _evict_until_fits(self, required_size: int):
        """Evict LRU items until required_size fits."""
        while self.current_size + required_size > self.max_size and self.map:
            lru = self.tail.prev
            self._remove_node(lru)
            self.current_size -= lru.size
            del self.map[lru.key]
    
    def get(self, key: int) -> any:
        if key in self.map:
            node = self.map[key]
            self._move_to_head(node)
            return node.value
        return -1
    
    def put(self, key: int, value: any, size: int) -> None:
        if size > self.max_size:
            return  # Item too large to ever fit
        
        if key in self.map:
            # Update existing item
            node = self.map[key]
            old_size = node.size
            node.value = value
            node.size = size
            self.current_size += size - old_size
            self._move_to_head(node)
            # Evict if size increased too much
            if self.current_size > self.max_size:
                self._evict_until_fits(0)
        else:
            # Add new item
            self._evict_until_fits(size)
            if self.current_size + size <= self.max_size:
                new_node = Node(key, value, size)
                self.map[key] = new_node
                self._add_node(new_node)
                self.current_size += size

# Test
cache = SizedLRUCache(10)
cache.put(1, "a", 4)  # {1:a,4}, total=4
cache.put(2, "b", 4)  # {2:b,4, 1:a,4}, total=8
cache.put(3, "c", 5)  # Evict 1, {2:b,4, 3:c,5}, total=9
print(cache.get(2))   # "b"
cache.put(4, "d", 3)  # Evict 3, {2:b,4, 4:d,3}, total=7
print(cache.get(3))   # -1
print(cache.get(2))   # "b"