Priority-expiry-cache

简介

这个问题是公司在面试中经常提出的问题之一，例如特斯拉、亚马逊、BP 等。

特斯拉电话面试缓存问题

我个人认为这个问题对于一个小时的面试来说有点太多，从构思到编写完整的代码实现。这个 crate 是一个尝试，使这个问题变得过时，并让优秀的候选人免受基于直觉而不是算法和数据结构技能的问题的拒绝。

对于所有只想要一个良好的优先级过期缓存的人来说，请随意查看这个 crate 的 官方 crate，在官方 GitHub 仓库发送 prs 和票据。

所有代码都在非正式的 Beerware 许可证下发布。

问题声明

问题声明要求我们设计一个具有以下方法的缓存

• get(String key)
• set(String key, String value, int priority, int expiry)
• evictItem(int currentTime)

缓存操作规则如下

1. 如果可用过期项，则删除它。如果多个项具有相同的过期时间，删除任何一个都足够。
2. 如果无法满足条件 #1，则删除优先级最低的项。
3. 如果有多个项满足条件 #2，则删除最近最少使用的项。
4. 多个项可以具有相同的优先级和过期时间。

未提及的规则

• 所有这些操作都应该在 O(1) 时间和空间复杂度内完成。

1 分钟解决方案摘要

这是 LRU 缓存（如本实现中所述 LRU 缓存面试蛋糕）的扩展，它扩展了 LRU 缓存维基百科，区别在于添加了一个二叉树来跟踪最小和最大优先级和过期时间。

解决方案

假设

• 所有参数都具有固定长度，例如 String = 长度 1024；Int = u32。

使用的数据结构

• 双链表
• 二叉树
• 哈希表

集合 O(1) 时间和空间复杂度

从集合开始，为了减少查找时间，我们将使用哈希表来存储封装“值”参数的对象的引用，假设映射已预先初始化，此时 K 是字符串的长度，因为它是我们的哈希函数的输入。假设“值”是固定长度的，那么我们的成本将是 O(1)。

现在我们可以假设 int 是一个有限数，比如 u32，这意味着我们可以构建一个深度为 32 的二叉树，访问时间为 O(32)，因此时间和空间复杂度都是 O(1)。

这样我们可以构建两个二叉树，它们将给我们最小和最大的优先级和过期时间，以 O(1) 的成本。为了满足规则 4，我们还需要使用双链表作为二叉树的叶级，这样我们就可以有多个具有相同过期时间或相同优先级的项，并且为了满足规则 3 关于移除最少使用项。

插入的复杂度是 O(1)，插入优先级和过期时间的二叉树是 O(K) x 2，假设 K 是常数，那么 O(1) + O(1) x 2 = O(1) 时间和空间。

获取 O(1) 时间和空间复杂度

获取更简单，因为我们只需要访问哈希表来获取对象的引用，而这已经在 O(1) 时间和空间内完成了。

并且

为了保持过期和优先级的一致性，我们将项移动到列表的头部，这样我们就可以在 O(1) 内跟踪最少使用的项。

查找的复杂度是 O(1)，插入优先级和过期时间的二叉树是 O(K) x 2，假设 K 是常数，那么 O(1) + O(1) x 2 = O(1) 时间和空间。

EvictItem O(1) 时间和空间复杂度

根据规则 1，我们将以 O(1) 的速度获取最小过期时间，这要归功于前面提到的二叉树，然后删除第一个项。根据我们的策略，我们使用最少使用策略来处理过期和优先级。

如果最小值还没有过期，我们将以 O(1) 的速度获取最小优先级，然后我们可以通过双链表移除最少使用的项。

复杂度是 O(1) x 2 对于最小过期时间和最小优先级的查找，以及 O(1) 来删除双链表的尾部 = O(1) 时间和空间。

致谢

• Giacomo Sorbi 仔细校对