Company Tags: Amazon, Adobe

Core Concept: Cache, Linked List, HashMap

Solve on LeetCode

29:T54b,class Node: def __init__(self, key, val): self.key, self.val = key, val self.prev = self.next = None class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.cache = {} # map key to node # left=LRU, right=most recent self.left, self.right = Node(0, 0), Node(0, 0) self.left.next, self.right.prev = self.right, self.left # remove node from list def remove(self, node): prev, nxt = node.prev, node.next prev.next, nxt.prev = nxt, prev # insert node at right def insert(self, node): prev, nxt = self.right.prev, self.right prev.next = nxt.prev = node node.next, node.prev = nxt, prev def get(self, key: int) -> int: if key in self.cache: self.remove(self.cache[key]) self.insert(self.cache[key]) return self.cache[key].val return -1 def put(self, key: int, value: int) -> None: if key in self.cache: self.remove(self.cache[key]) self.cache[key] = Node(key, value) self.insert(self.cache[key]) if len(self.cache) > self.cap: # remove from the list and delete the LRU from the hashmap lru = self.left.next self.remove(lru) del self.cache[lru.key]2a:T5b8,class LRUCache { private: struct Node { int key, val; Node *prev, *next; Node(int k, int v): key(k), val(v), prev(nullptr), next(nullptr) {} }; int capacity; unordered_map cache; Node *left, *right; void remove(Node* node) { Node *prev = node->prev; Node *nxt = node->next; prev->next = nxt; nxt

Spiral Matrix (#54)