Tiktok最近在美国风波不断，但是很多同学看准机会“抄底”Tiktok，巴菲特也说过，别人恐惧的时候我贪婪。Tiktok目前招聘仍然火热进行中，虽然可能要经历最终多轮的换组捞简历，但是在大环境不好的情况下，继续面试Tiktok也是个不错的选择。

下面来看看Tiktok近期的一道面试题吧

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity): Initialize the LRU cache with a positive size capacity.
• int get(int key): Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Constraints:

• -1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105

Requirements:

• The code must be completed using OOP principles.
• If you need more classes, simply define them inline.

这道面试题是设计一个遵循最近最少使用（LRU）缓存机制的数据结构，是一个在计算机科学和软件工程领域中非常常见且实用的问题。这个问题考察了面试者对数据结构、算法复杂度以及面向对象编程的理解和应用能力。实现一个性能优良的 LRU 缓存机制需要精心选择合适的数据结构以确保每个操作的时间复杂度都是 𝑂(1)O(1)。

思路：

1. 数据结构的选择：
   • 哈希表：用于快速查找和更新节点。哈希表将键映射到其在双向链表中的位置。
   • 双向链表：用于快速添加和删除节点。链表的两端分别表示最近使用的和最久未使用的节点。
2. 操作详解：
   • get(key)：
     • 如果键存在于哈希表中，则哈希表返回对应的节点。
     • 将该节点移动到双向链表的头部，表示最近使用过。
     • 返回节点的值。
     • 如果键不存在，返回 -1。
   • put(key, value)：
     • 如果键已存在，更新其值，并将此节点移动到链表头部。
     • 如果键不存在，创建新的节点，并将其加入到链表头部，同时在哈希表中添加映射。
     • 如果添加新节点后超出容量限制，则移除链表尾部的节点，并在哈希表中删除对应的映射。
3. 考虑边界条件：
   • 缓存容量可能为负数或零。
   • 必须处理好容量为零时的特殊情况，此时不应执行任何添加操作。
   • 对于所有的操作，必须保证时间复杂度为 𝑂(1)O(1)。

评价：

这道题的复杂度合适，适合用来评估面试者是否能够处理涉及多个组件的系统设计问题。经过我们的辅助，候选人谈笑间轻松通过了本次面试。如果你也需要我们的面试辅助服务，请抓紧时间联系我。