Павел Ткаченко

Как удивить работодателя на техническом интервью с помощью Киану Ривза

ruby

Классическая задача для каждого джуниора (начинающего разработчика) – нахождение числа n в последовательности Фибоначчи. Если вы позабыли, то это это ряд чисел, где каждое число является суммой двух предыдущих. Так например для седьмого числа в ряду ответ будет 13. Ниже представлен ряд чисел Фибонначи.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Давайте попробуем решить такую задачу при помощи ruby и с поддержкой Киану.

День когда земля остановилась

В большинстве случаев интервьюер хочет увидеть ваше понимание рекурсии. Она к слову является одним из камней предкновения для большинства новичков наряду с указателями в C/C++.

И самое простое решение с использованием рекурсии будет следующим:

def fib(n)
  return n if n <= 1

  fib(n - 1) + fib(n - 2)
end

fib(7) #=> 13

Это решение очень неэффективно. Алгоритмическая сложность такого решения может быть выражена как O(2^n), т.е. сложность вычисления растет экспоненциально. Если вы хотите узнать больше про алгоритмическую сложность или как ее еще называют Big O Notation, советую почитать хорошую статью на Хабре. В нашем решении мы считаем все числа от 0 до n снова и снова для каждой n в последовательности. Для больших чисел (>80) количество операций расчета уже будет больше, чем количество атомов во вселенной! И конечно же, при таком подходе, такие числа невозможно вычислить не только на вашем компьютере, все вычислительные мощности Земли замрут. Интервьюер вряд ли будет доволен таким решением, нам нельзя останавливать Землю!

Посмотрим на стэк вызовов при рекурсии. Когда вы вызываете функцию fib(7), она рекурсивно вызывает функции fib(6) и fib(5). В это время fib(6) вызывает fib(5) снова, хотя fib(5) был расcчитан при вызове fib(7).

Дерево вызовов функции fib при рекурсии

Джонни Мнемоник

Если вы продвинулись в своих навыках программирования, то при использовании рекурсии можете добавить мемоизацию. В этом случае вы избегаете повторных расчетов. В нашем случае, fib(7) уже рассчитала значения для функций fib(6) и fib(5). Поэтому, при вызове функции fib(6), она уже не будет рассчитывать fib(5) снова, а возьмет уже готовое значение из памяти. В большинстве случаев интервьюер будет доволен таким решением и предложение с хорошей зарплатой будет у вас в кармане.

module Fib
  @memo = [0,1]
  def self.calc(num)
    return num if num < 2

    @memo[num] ||= self.calc(num - 1) + self.calc(num - 2)
  end
end

Fib.calc(7) #=> 13

Здесь мы сохраняем каждый результат функции в переменную @memo и при каждом вызове функции, проверяем, нет ли уже готового результата для нужного числа. Код не сильно усложнился, но теперь можно рассчитать значительно большие числа. Что насчет алгоритмической сложности? Она у нас O(n), выглядит очень даже хорошо.

Матрица

Но что если вы хотите удивить интервьюера и предложить решение с алгоритмической сложностью O(log n)? Следуй за белым кроликом! Решение очень компактное, но сверх-эффективное:

require "matrix"

def fib(n)
  (Matrix[[1,1],[1,0]] ** n)[1,0]
end

fib(7) #=> 13

Хмм... Здесь немного математики! А говорят, она не нужна программисту. Нужно вспомнить школьный курс матриц. Расслабьтесь, главная фишка здесь в простом возведении матрицы [[1,1][1,0]] в степень n, где n – нужное нам число. Требуемый ответ будет лежать в получившейся матрице в элементах [1,0] или [0,1]. В этом случае расчет практически моментальный и алгоритмическая сложность почти не растет с увеличением числа n.

Вот так решение видят математики

Таким решением вы покажете интервьюеру, что вы не только посещали уроки алгебры в школе, но и умеете применять ее силу в программировании. Поэтому не забудьте освежить ваши знания алгебры, математика не всегда бывает скучной. А с таким решением на собеседовании у вас всегда будет преимущество перед другими кандидатами.

Павел Ткаченко
Веб-разработчик в Скиллотеке. Программирует с детства, без ума от Ruby. В свободное время занимается созданием инди-игр на Unity.