Вопрос интервью: Факториалы и кеширование

Question

Недавно я наткнулся на следующий вопрос:

Вам необходимо спроектировать систему, которая будет предоставлять ответы на вопросы факториалов для от 1 до 100. Вы можете кэшировать 10 номеров. Как бы ты организовать / управлять этим кешем, и каков наихудший случай для поиска на отсутствует кеш.

Как вы думаете, что будет подходящим ответом и каковы причины этого? Лично я бы кешировал первые десять чисел для первого ввода, а затем впоследствии поддерживал кэш LRU на основе самого последнего ввода, потому что люди с большей вероятностью будут повторять поиск. Не совсем уверен, какой будет худший случай для поиска при пропадании кэша. Вероятно, O (n), если вы используете подход динамического программирования при реализации факториальной функции. Что ты думаешь?

Answer 1

впоследствии поддерживает кэш LRU на основе самых последних данных, потому что люди с большей вероятностью будут повторять поиск

Это может быть разумным выбором дизайна, но в интервью я бы сформулировал это больше как вопрос к интервьюеру: «Было бы разумно предположить, что вызовы будут больше походить на последние значения, или есть другая ожидаемая группировка (большие числа будут запрашиваться чаще, чем маленькие или наоборот)? "

Например, может иметь смысл кэшировать LRU, но никогда не выбрасывать значения для 10, 20, 30, 40 и т. Д. Таким образом, наихудший случай для вычисления факториала после заполнения кэша этими значениями - выполнить 10 умножений.

Еще одно соображение, которое вы можете сделать, заключается в том, что компьютеры могут очень легко справляться с определенными факториалами:

• 12! является самым большим, который может содержаться в 32-разрядном слове.
• 20! является самым большим, что может содержаться в 64-битном слове.
• 34! это самое большое, что может быть в 128-битном слове.

Поскольку современные машины могут легко работать с 64-битной арифметикой (может быть, даже 128-битной арифметикой), также может иметь смысл никогда не кэшировать значение для 20! или ниже, как только кеш заполняется значениями, превышающими это.

Наихудший случай поиска пропущенного кэша будет зависеть от того, как вы храните кэш. Это массив, отсортированный по аргументу функции? (поиск O (log n)) Это массив в порядке LRU? (посмотрите на отсутствие кэша O (n)). Я думаю, вы также хотели бы прояснить, что вы хотите, чтобы поиск в кэше всегда возвращал самое высокое значение в кэше, которое меньше, чем вы ищете - это значение кэша представляет собой работу, которую вам не нужно делать для этого конкретного факторного расчета.

Answer 2

Идея в том, чтобы выбрать некоторые числа, чтобы можно было вычислить другие из них.Предполагая, что ваша система выполняет умножение с постоянной скоростью и без деления, кэширование (или «предварительное вычисление») 1 !, 11 !, 21 !, 31 !, 41 !, 51 !, 61 !, 81 !, 91!позволяет рассчитать все оставшиеся числа с не более чем 9 умножениями для каждого.

В действительности умножение больших чисел обходится дороже, и вы также можете сделать деление (например, 90! = 91! / 91), и вы неt действительно нужно 1 !, что может привести к другому оптимальному распределению этих якорных номеров.

Answer 3

Как насчет использования 9 слотов кеша для факториала 10, 20, 30, 40, 50, 60, 70, 80 и 90?10-й слот может быть LRU.Тогда поиск в худшем случае - это O (10) или постоянное время.

Answer 4

Моя идея чем-то напоминает ConnorDoyle, я бы кешировал все кратные 10. Без представления о типе вызовов, которые будут делать пользователи, это оставило бы вас с наименьшим худшим сценарием из 7 умножений / делений, включая исходный два, чтобы найти единицы и десятки цифр, или постоянное время.

Быстрый псевдо-алгоритм на моей голове:

total;
mod = input%10;
div = input/10;
if(input%10 == 0)
    output(cache[input/10]);
else{
    if(mod < 5) {
        total = cache[div];
        for(i = 1; i<=mod; i++)
            total = total * (cache[div] + i);
    }
    else {
        total = cache[div + 1];
        for(i = 9; i>mod; i--)
            total = total / (cache[div] + i);
    }
    output(total);
}

В худшем случае будет что-либо с 5 в цифре.