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

Предварительные условия:

В этом руководстве предполагается, что вы знакомы с синтаксисом javascript, структурой данных, алгоритмами, временной сложностью. Однако, если у вас есть идея, вы можете решить задачу на любом удобном для вас языке.

Что такое ряд Фибоначчи

Согласно Википедии числа Фибоначчи, обычно обозначаемые как Fn, образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с от 0 до 1.

Как работает Фибоначчи?

Основная логика состоит в том, что серия начинается с [0, 1], поэтому элемент [0] + element [1] и результаты будут помещены в element [2] и так далее. Например,

для элемента с индексом 2: 0 + 1 = 1, 1 будет помещен в массив с индексом 2.

для элемента с индексом 3: 1 + 1 = 2, 2 будет помещен в массив с индексом 3.

для элемента с индексом 4: 2+ 1 = 3, 3 будет помещен в массив с индексом 4.

для элемента с индексом 5: 3+ 2 = 5, 5 будет помещен в массив с индексом 5.

для элемента с индексом 6: 5+ 3 = 8, 8 будет помещен в массив с индексом 6.

Ряд Фибоначчи - это порядок чисел, в котором каждое число является суммой двух предыдущих.

Каково реальное применение рядов Фибоначчи

Фибоначчи имеет большое применение в программировании. Например:

  1. он используется при оценке задач в Agile. Большая часть управления Agile-командой - это оценка времени, которое потребуется для выполнения задач.
  2. Еще одно приложение в веб-дизайне, небольшой скрипт, который может быть разработан для автоматического взвешивания размеров шрифта заголовков.
  3. Отличное применение ряда Фибоначчи, которое в основном используется в автомобильной промышленности, - это преобразование мили в километры на передней приборной панели автомобиля.

Вопрос из интервью.

Вам необходимо вернуть n-й элемент (n) и вывести его на консоль из ряда Фибоначчи.

Например, если у вас есть такая последовательность [0, 1, 1, 2, 3, 5, 8, 13], получите 6-й элемент - это вернет 8 . См. Иллюстрацию ниже.

для элемента с индексом n: element (n-1) + element (n-2) Итак, общая форма будет F (n) = F (n-1) + F (n-2).

Применение алгоритма кодирования

  1. Использование классического цикла for для создания ряда

Приведенный выше код не требует пояснений, мы устанавливаем цикл for из третьего элемента массива - так как первый и второй всегда равны 0 и 1. После этого мы отправили результат в контейнер удерживающего массива - result [] . Этот алгоритм занимает O (n) временную сложность.

2. Использование рекурсии :-)

Теперь, после завершения вашего кода, интервьюер спросит вас, как вы можете улучшить этот алгоритм? Когда он спрашивает вас, это означает, что ему нужно, чтобы вы конкретно произнесли рекурсию. Как упоминалось на рисунке 1, мы перебираем только две переменные (n-1) и (n-2), которые могут быть хорошим кандидатом для рекурсии.

Алгоритм рекурсии очень дорог, поскольку временная сложность Big O экспоненциальна. Это потому, что вы вызываете одну и ту же функцию снова и снова, инициализируете аргументы, создаете заполнитель для функции при каждом вызове и т. Д. Итак, как только вы выполнили алгоритм рекурсии, вы должны сообщить своему интервьюеру, что для этого требуется O ( 2 ^ n) время.

BenchMark два алгоритма

Как показано на рисунках 5 и 6, использование цикла for лучше с точки зрения скорости. Рекурсия на 47% медленнее, чем при использовании классического алгоритма цикла for.

Более продвинутый трюк для повышения производительности

На этом этапе, если интервьюер хочет сжать вас сильнее, он спросит, как повысить производительность алгоритма рекурсии?
Если вы посмотрите на иллюстрацию ниже, вы заметите, что мы вызываем одну и ту же функцию с одним и тем же аргументом более одного раза. Например, для n = 6 мы вызываем F (1) 8 раз - представьте, что n = 36 F (1) выйдет за пределы. Итак, если есть способ сохранить эти вызовы функций в памяти и вызывать их только один раз, это значительно повысит производительность. Это мемоизация.

В вычислениях мемоизация - это метод оптимизации, используемый в первую очередь для ускорения компьютерных программ за счет сохранения результатов дорогостоящих вызовов функций и возврата кэшированного результата, когда те же входные данные повторяются снова - википедия.

По сути, вам нужно создать функцию, которая берет на себя медленную функцию и повышает ее производительность путем кэширования повторяющихся вызовов.

Теперь BenchMarking

Проверить производительность теста можно по этой ссылке.

Заключительные примечания

Технические собеседования могут быть сложными, но для их успешного прохождения вам нужно продолжать практиковаться, писать алгоритмы самостоятельно, а не просто читать. Постарайтесь максимально упростить задачу, используя рисование, письмо и т. Д. Если вы выполняете задание по кодированию на доске, постарайтесь думать вслух, чтобы привлечь собеседников к вам. Они хотят знать ваш подход к решению проблем, а не решение - они уже знают правильный ответ.

Наконец, я надеюсь, что этот пост принесет пользу другим людям в процессе собеседования. Если вам понравился мой пост, подпишитесь на меня на Medium или оставьте комментарий. Вы можете подписаться на меня в твиттере @salmaneg. Спасибо за чтение и удачи в поиске работы !!!

📝 Прочтите этот рассказ позже в Журнале.

🗞 Просыпайтесь каждое воскресенье утром и слышите самые интересные истории, мнения и новости недели, ожидающие в вашем почтовом ящике: Получите заслуживающий внимания информационный бюллетень›