Design an LRU (Least Recently Used) cache that supports the following operations: get(key) - get the value of the key if it exists, otherwise return -1; put(key, value) - insert or update the key-value pair, if the capacity is exceeded, remove the least recently used item. Both get and put operations must be O(1) time complexity.
分类: technical
难度: medium
标签:
答题技巧
Classic interview topic: hash map + doubly linked list combination; hash map for O(1) lookup, linked list to maintain access order; move node to front on get; handle existing key and capacity overflow on put; using dummy head/tail nodes makes implementation cleaner.
参考答案
Use a HashMap<key, Node> and a doubly linked list. Each Node contains key, value, prev, next. Move accessed/inserted nodes to the head (most recently used). When capacity is exceeded, remove the tail node (least recently used) and remove it from the HashMap. Both get and put are O(1).