Microsoft VO 面试真题解析：LRU Map（LRU 缓存 / 哈希表 + 双向链表）

LRU Map

Design a data structure that supports storing key-value pairs and evicting the least recently used entry when capacity is exceeded.

Implement the basic operations for an LRU map so that lookups and updates can be performed efficiently.

这道题本质上是在实现一个支持最近最少使用淘汰策略的键值映射，也就是 LRU Cache。常见做法是用哈希表保证查找和更新接近 O(1)，再配合双向链表维护访问顺序：每次访问或插入都把节点移动到链表头部，容量超限时删除尾部最久未使用的节点。面试中重点考察的是数据结构组合、时间复杂度控制，以及对“最近使用”这一语义的准确维护。