我最近遇到了以下面试问题:
您需要设计一个系统,为1到100之间的阶乘提供答案.您可以缓存10个数字.您将如何安排/管理缓存,以及查找缓存未命中的最坏情况.
您认为什么是合适的答案以及这背后的原因是什么？就个人而言,我会为第一个输入缓存前10个数字,然后根据最近的输入维护LRU缓存,因为人们更有可能重复搜索.但是不确定查找缓存未命中的最坏情况是什么.如果您在实现阶乘函数时使用动态编程方法,可能是O(n).你怎么看？
随后根据最近的输入维护LRU缓存,因为人们更有可能重复搜索
这可能是一个合理的设计选择,但在采访中我会更多地向采访者提出一个问题:"假设呼叫更像是用最近的价值来做,或者是否有其他一些是合理的预期的分组(大数据将被要求更频繁,然后更小,反之亦然)？"
例如,缓存LRU可能有意义,但永远不会丢弃10,20,30,40等的值.这样,一旦缓存填满这些值,计算因子的最坏情况是必须执行10乘法.
您可能会考虑的另一个考虑因素是计算机可以非常轻松地处理某些因子:
由于今天的机器可以轻松处理64位算术(甚至可能是128位算术),所以从不缓存20的值也是有意义的!一旦缓存填充大于该值的值,则为低于此值.
查找缓存未命中的最坏情况取决于您如何存储缓存.它是一个按函数参数排序的数组吗？(查找是O(log n))它是LRU顺序的数组吗？(查看缓存未命中是O(n)).我想你也想明确表示你希望缓存查找始终返回缓存中的最高值,该值低于你要查找的值 - 缓存值代表你不必做的工作对于这个特定的因子计算.
这里的想法是选择一些数字,以便可以从中计算其他数字.假设你的系统以恒定速度进行乘法运算,根本没有除法,缓存(或"预先计算")1!,11!,21!,31!,41!,51!,61!,81!,91!允许计算所有剩余数字,每个数字最多9次乘法.
实际上,乘以更大的数字会更加昂贵,而且你也可以进行除法(例如90!= 91!/ 91),而你真的不需要1 !,这可能会导致这些锚号的另一个最佳分布.