我最近遇到了以下面试问题:
您认为什么是合适的答案，其背后的原因是什么？就个人而言，我会缓存第一个输入的前十个数字，然后根据最近的输入维护一个 LRU 缓存，因为人们更有可能重复搜索。不太确定查找缓存未命中的最坏情况是什么。如果您在实现阶乘函数时使用动态编程方法，则可能为 O(n)。你怎么看？
最佳答案
这可能是一个合理的设计选择，但在采访中，我更像是对采访者的一个问题:“假设调用更像是使用最近的值进行调用是否合理，或者还有其他一些吗？预期的分组(大数字会比小数字更频繁地被请求，反之亦然)？”
例如，缓存 LRU 可能是有意义的，但永远不要丢弃 10、20、30、40 等的值。这样，一旦缓存充满这些值，计算阶乘的最坏情况是必须执行 10乘法。
您可能要考虑的另一个问题是计算机可以很容易地处理某些阶乘:
由于今天的机器可以轻松处理 64 位算术(甚至可能是 128 位算术)，因此永远不要缓存 20 的值也可能是有意义的!或低于一旦缓存填充了大于该值的值。
查找缓存未命中的最坏情况取决于您如何存储缓存。它是按函数参数排序的数组吗？ (查找是 O(log n))它是 LRU 顺序的数组吗？ (查找缓存未命中是 O(n))。我认为您还想明确表示您希望缓存查找始终返回缓存中的最高值，该值小于您要查找的值 - 该缓存值代表您不必做的工作对于这个特定的阶乘计算。