Гроза собеседований: Задача FizzBuzz

Есть известное высказывание:

Меня немного удручает тот факт, что 199 из 200 соискателей программистских вакансий не умеют программировать. Повторю: они не умеют писать код. Вообще.

Речь здесь идет об известной задаче FizzBuzz, которую придумали еще в 2007 году.

Смысл ее такой:

Напишите программу, которая выводит на экран числа от 1 до 100. При этом вместо чисел, кратных трем, программа должна выводить слово «Fizz», а вместо чисел, кратных пяти — слово «Buzz». Если число кратно и 3, и 5, то программа должна выводить слово «FizzBuzz».

Появилась эта задача из-за того, что на технических интервью даже Senior Developer-ы не могли решать простейшие задачки на бумаге. Чтобы решить задачу FizzBuzz, у многих уходило более 15 минут, хотя должно занять не более пары минут.

Сейчас эта (и подобные) задачи стали уже классикой собеседований - их активно используют, чтобы выявить «недопрограммистов».

Дэн Кигель описал свои мысли по этому поводу так:

Поверьте, если вы можете написать цикл от 1 до 10 на всех языках, указанных в вашем резюме, если вы можете решить в уме несложный арифметический пример и если вы знаете, как применить рекурсию в несложной (но взятой из реальной жизни) задаче — то вы уже на голову выше большей части людей, вращающихся в нашей индустрии.

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

Попытка 1

Первое, что приходит в голову - в цикле проверять выполнение каждого условия и в зависимости от результата выводить число, Fizz или Buzz.

Вот так выглядит код в первой итерации:

 for x in range(1, 100):
     if x%3 == 0 and x%5 == 0:
         print("FizzBuzz", end=' ')
     elif x%3 == 0:
         print("Fizz", end=' ')
     elif x%5 == 0:
         print("Buzz", end=' ')
     else:
         print(x, end=' ') 

Однако, тут сразу можно дать несколько рекомендаций. Некоторые в коде уже учтены, а некоторые просто нужно принять к сведению.

• Лучше проверять делимость на 15, а не на 3 и 5 по-отдельности. Причина проста - одно вычисление быстрее, чем 2.
• Проверять делимость лучше с помощью оператора %, а не с помощью функций. Оператор работает быстрей.

Можно еще придумать ряд правил. Главное, понимать, что задача не просто на «умение написать код». С помощью этой задачи также проверяется, насколько Вы умеете код оптимизировать. Чем «экономней» будет Ваш цикл, тем лучше.

В интернете Вы найдете огромное количество реализаций этого алгоритма. Какие из них правильные?... Сложно сказать. Скорее всего, правильным кодом будет тот, который сидит у Вашего интервьюера в голове :) Так что не пытайтесь найти «секретный ключ» - просто сравните большое количество вариантов, найдите разницу между ними и выберите самый эффективный с точки зрения производительности и сложности алгоритма.

Попытка 2

Давайте рассмотрим еще несколько реализаций. Например, здесь с помощью строк мы уменьшаем количество условных блоков на 1.

 for x in range(1, 100):
     s = ''
     if x%3 == 0:
         s += 'Fizz'
     if x%5 == 0:
         s += 'Buzz'
     if s == '':
         s = x
     print(s, end=' ') 

Вот еще пример - в одну строку.

 [
     (
         "FizzBuzz" if (x%3 == 0) and (x%5 == 0)
         else "Fizz" if x%3 == 0
         else "Buzz" if x%5 == 0
         else x
     )
     for x in range(1, 100)
 ] 

А вообще, не зря говорят, что преждевременная оптимизация - источник зла. Пытаться что-то оптимизировать в отрыве от контекста - не всегда умная (и приносящая пользу) задача. Вы можете намудрить со структурами данных или сделать еще что-то великое, но если остальная программа использует другие структуры, то толку от этого не будет.

По этому поводу есть даже одно интересное замечание:

Если думать о производительности, то вообще надо предварительно вычисленные значения использовать.

Например, как-то так:

 print([1, 2, 'Fizz', 4, 'Buzz', 'Fizz', 7, 8, 'Fizz', 'Buzz', 11, 'Fizz', 13, 14, 'FizzBuzz', 16, 17, 'Fizz', 19, 'Buzz', 'Fizz', 22, 23, 'Fizz', 'Buzz', 26, 'Fizz', 28, 29, 'FizzBuzz', 31, 32, 'Fizz', 34, 'Buzz', 'Fizz', 37, 38, 'Fizz', 'Buzz', 41, 'Fizz', 43, 44, 'FizzBuzz', 46, 47, 'Fizz', 49, 'Buzz', 'Fizz', 52, 53, 'Fizz', 'Buzz', 56, 'Fizz', 58, 59, 'FizzBuzz', 61, 62, 'Fizz', 64, 'Buzz', 'Fizz', 67, 68, 'Fizz', 'Buzz', 71, 'Fizz', 73, 74, 'FizzBuzz', 76, 77, 'Fizz', 79, 'Buzz', 'Fizz', 82, 83, 'Fizz', 'Buzz', 86, 'Fizz', 88, 89, 'FizzBuzz', 91, 92, 'Fizz', 94, 'Buzz', 'Fizz', 97, 98, 'Fizz']) 

Эпилог

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

И не бойтесь рассуждать. Напишите первый, черновой, вариант решения, а потом постепенно его улучшайте. Ваш собеседник это оценит, я Вас уверяю. В конце концов, не забывайте высказывание Дэна Кигеля, которое мы приводили в начале статьи.