caching - 面试题 : Factorials and caching

Question

我最近遇到了以下面试问题:

You need to design a system to provide answers to factorials for between 1 and 100. You can cache 10 numbers. How would you arrange/manage that cache, and what is the worst case for lookup on a cache miss.

你认为什么是合适的答案，这背后的原因是什么？就个人而言，我会缓存第一个输入的前十个数字，然后根据最近的输入维护一个 LRU 缓存，因为人们更有可能重复搜索。不太确定查找缓存未命中的最坏情况是什么。如果您在实现阶乘函数时使用动态编程方法，则可能为 O(n)。你怎么认为？

Answer 1

subsequently maintain an LRU cache based on the most recent input because people are more likely to repeat searches

这可能是一个合理的设计选择，但在采访中，我更像是对采访者的一个问题:“假设调用更像是使用最近的值进行调用是否合理，或者是否有其他一些预期的分组(大数字会比小数字更频繁地被请求，反之亦然)？”

例如，缓存 LRU 可能是有意义的，但永远不要丢弃 10、20、30、40 等的值。这样，一旦缓存充满这些值，计算阶乘的最坏情况是必须执行 10乘法。

您可能要考虑的另一个问题是计算机可以很容易地处理某些阶乘:

12!是 32 位字中可以容纳的最大值。

20!是 64 位字中可以容纳的最大值。

34!是 128 位字中可以容纳的最大值。

由于今天的机器可以轻松处理 64 位算术(甚至可能是 128 位算术)，因此永远不要缓存 20 的值也可能是有意义的!或低于一旦缓存填充了大于该值的值。

查找缓存未命中的最坏情况取决于您如何存储缓存。它是按函数参数排序的数组吗？ (查找是 O(log n))它是 LRU 顺序的数组吗？ (查找缓存未命中是 O(n))。我认为您还想明确表示您希望缓存查找始终返回缓存中的最高值，该值小于您要查找的值 - 该缓存值代表您不必做的工作对于这个特定的阶乘计算。