Fizzbuzz — это простой алгоритм, который когда-то был популярен в контексте технических собеседований.

Я знал, что это такое, но до прошлой недели меня ни разу не просили написать его.

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

Базовую реализацию fizzbuzz можно написать однострочником на Typescript:

const fizzbuzz = (n: number)=>`${n%3 ? '' : 'Fizz'}${n%5 ? '' : 'Buzz'}`;

Во время собеседования меня попросили написать fizzbuzz на любом близком мне языке; собеседующий даже сказал, что можно использовать эзотерические языки программирования, но рекомендовал не делать этого, потому что некоторые правила реализовать будет сложно. Этого вполне можно было ожидать, ведь собеседование могло длиться до 45 минут, а обсуждать простой fizzbuzz особого смысла не было. Менять язык программирования после начала собеседования тоже было запрещено.

Первый набор правил мне раскрыли за раз, это были всего лишь инструкции по написанию fizzbuzz:

1. Алгоритм должен работать хотя бы для целых чисел в интервале 1-1000. Числа вне этого интервала нас не интересуют.

2. Использование браузера разрешается, но нельзя искать FizzBuzz и заходить на страницы с обсуждением FizzBuzz.

3. ИИ-инструменты запрещены.

4. Входные данные хранятся в массиве DATA.

5. Вместо чисел, кратных 3, программа должна выводить Fizz.

6. Вместо чисел, кратных 5, программа должна выводить Buzz.

7. Вместо чисел, кратных 3 и 5, программа должна выводить FizzBuzz.

8. FizzBuzz — это критичный код. Плохие входные данные должны игнорироваться, а не влиять на вывод и не приводить к катастрофическим вылетам.

9. Правила действуют всегда, только если их не заменяют другие правила.

10. Новые правила будут раскрываться одно за другим. Кандидат должен записать их, потому что больше их показывать не будут.

11. Нарушение правила не приводит к мгновенной дисквалификации, некоторые нарушения допускаются, если они не вопиющие с точки зрения собеседующего. Однако нельзя возвращать недопустимый вывод.

Это было просто, мне просто нужно было выполнить filter валидных входных данных при помощи Number.isSafeInteger, а затем произвести map массива DATA с использованием приведённой выше реализации fizzbuzz, а затем произвести reduce результата для вывода в виде строки. Потом стали известны новые правила:

1. Код не длиннее 30 строк. Строки, занимаемые входным массивом, не учитываются.

2. Максимальная ширина строки кода — 100 символов. Строки должны разрываться в естественных точках разрыва, а не с целью соблюдения правил. Комментарии не учитываются в этом ограничении и в случае своей полезности будут оцениваться положительно.

3. Переменные не могут иметь имена из одного или двух символов. Исключения допускаются, если это не мешает осмысленности имён, или когда смысл переменной можно понять по способу её использования, или в случаях, когда короткие имена используются традиционно (например, в циклах).

4. Читаемость: нельзя пренебрегать отступами и символами новых строк. Табы занимают 4 пробела.

5. Результат должен быть представлен в виде строки. Плохие входные данные должны возвращать пустую строку.

6. Запрещены операции, изменяющие массив. После инициализации добавление или удаление данных из массива не допускается.

Как видите, эти правила не требуют или почти не требуют никаких изменений в моём fizzbuzz, поэтому собеседующий просто перещёлкивал дальше слайды Powerpoint с правилами. Думаю, эти правила нужны или для отсеивания самых новичков, или чтобы кандидаты комфортнее почувствовали себя на сессии живого кодинга.

Правило 7 стало первым правилом, заставившим мой мозг выйти из режима экономии энергии:

7. Числовые типы, числовые литералы и связанные с ними методы и операции запрещены. Во входном массиве должны содержаться строковые представления чисел. Программист может выбрать любое подходящее ему представление, с одним ограничением: оно должно содержать буквы, числа и символы, которые можно ввести одним нажатием (раскладка клавиатуры не уточнялась, на моей одним нажатием можно ввести ñ и ç; я предположил, что имеется в виду раскладка США). Максимальная длина строки, представляющей число — 6 символов.

Переход от правил 1-6 к правилу 7 оказался очень резким. Сначала я замер и несколько минут думал над тем, как написать fizzbuzz со строками так, чтобы он уместился в 30 строк кода, без использования чисел и математических операторов.

Когда мои нейроны достигли оптимальной рабочей температуры, я чётко понял: для решения мне не нужно заново изобретать все математические вычисления со строками. Я знаю, что числа, кратные 5, заканчиваются на 0 или 5, а разряды кратного 3 числа при рекурсивном сложении всегда равны 3, 6 или 9.

Мне нужно было только сделать так, чтобы мой fizzbuzz принимал только валидные представления чисел и он не посчитал строку “Ñ+!0” кратной 5.

И тут у меня в голове щёлкнуло:

В Typescript есть очень мощный инструмент обеспечения безопасности типов. Мне просто нужно переписать код, использовав типы Typescript.

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

Представьте мои муки, когда я это услышал! Как может такой мощный язык, который практически является прикладной теорией категорий, не быть ЛУЧШИМ языком для категоризации строк на два класса эквивалентности (числа, кратные 3, и числа, кратные 5) с последующим нахождением пересечения двух множеств для поиска кратных для обоих классов и отнесением членов каждой категории к Fizz, Buzz или FizzBuzz?

Я даже не особо много потеряю по сравнению с обычным Typescript, поскольку я всё равно не могу использовать математику, а типы предоставляют множество мощных высокоуровневых возможностей, за которые в обычном Typescript я бы расплачивался дополнительными строками кода.

type DATA = ["3", "5", "10"];
type DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
type FIZZBUZZABLE = `${DIGIT}${DIGIT | ""}${DIGIT | ""}` | "1000"; //Числа вне интервала 0-1000 отклоняются
type SUM_TABLE = [
    ["0",   "1",    "2",    "3",    "4",    "5",    "6",    "7",    "8",    "9"],
    ["1",   "2",    "3",    "4",    "5",    "6",    "7",    "8",    "9",    "1"],
    ["2",   "3",    "4",    "5",    "6",    "7",    "8",    "9",    "1",    "2"],
    ["3",   "4",    "5",    "6",    "7",    "8",    "9",    "1",    "2",    "3"],
    ["4",   "5",    "6",    "7",    "8",    "9",    "1",    "2",    "3",    "4"],
    ["5",   "6",    "7",    "8",    "9",    "1",    "2",    "3",    "4",    "5"],
    ["6",   "7",    "8",    "9",    "1",    "2",    "3",    "4",    "5",    "6"],
    ["7",   "8",    "9",    "1",    "2",    "3",    "4",    "5",    "6",    "7"],
    ["8",   "9",    "1",    "2",    "3",    "4",    "5",    "6",    "7",    "8"],
    ["9",   "1",    "2",    "3",    "4",    "5",    "6",    "7",    "8",    "9"],
]; //Каждая позиция содержит рекурсивную сумму цифр её индексов
type SumDigits<T> = T extends `${infer Head}${infer Tail}` //Применяет катаморфизм для T, рекурсивно возвращающий сумму цифр T, пока T не станет одной цифрой
    ? Head extends DIGIT
        ? Tail extends DIGIT
            ? SUM_TABLE[Head][Tail]
            : SUM_TABLE[Head][SumDigits<Tail>]
        : SUM_TABLE[SumDigits<Head>][SumDigits<Tail>]
    : "0";
type TailOf<T> = T extends DIGIT ? T : T extends `${DIGIT}${infer Tail}` ? TailOf<Tail> : "0";
type Fizzer<T> = SumDigits<T> extends "3" | "6" | "9" ? 'Fizz' : '';
type Buzzer<T> = TailOf<T> extends "5" | "0" ? 'Buzz' : '';
type FizzBuzz<T> = T extends FIZZBUZZABLE ? `${Fizzer<T>}${Buzzer<T>}` : ""; //Из Fizzer и Buzzer T становится правильно сформированными входными данными
type Folded<T> = T extends [infer Head, ...infer Tail] ? `${FizzBuzz<Head>}${Folded<Tail>}` : ""; //Применяет катаморфизм FizzBuzz к массиву
type Result = Folded<DATA>;
     //^ FizzBuzzBuzz

27 строк! (Строка с входными данными по правилам не учитывается.)

Я подумал, что меня сразу примут на работу, и уже представлял, как удваивается сумма моей зарплаты. Мне не приходило в голову, что всё может быть сложнее, чем эта задача, ведь это и так было самое сложное собеседование в моей жизни, но я ошибался…

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

8. Массив может содержать 0. Если в выбранном числовом представлении невозможно представить 0, то представление необходимо изменить.

Фух! Ну, тут всё просто: выбранное мной представление, наивная запись по основанию 10, позволяло использовать 0.

Мне достаточно было добавить | “0” в оператор extends Fizzer, после чего ноль начал превращаться в FizzBuzz.

Мы обсудили это с собеседующим: он сказал, что 0 не кратен 3 и 5.

Это потребовало бы больше работы, потому что простой проверки последней цифры было бы недостаточно для проверки на кратность 5, ведь «0» не прошёл бы тест. Это было бы не так сложно, но я бы предпочёл не делать этого, поскольку обратное потребовало бы добавления всего 4 символов. К счастью, его коллега согласился, чтобы ноль был кратным любому числу, поэтому моё решение приняли.

9. Входной массив может быть пустым. В таком случае код должен выводить «Cronk».

Это вполне решается тернарной операцией type Result = DATA extends [] ? "Cronk" : Folded<DATA>;.

10. Входной массив может содержать недопустимые представления чисел вперемешку с допустимыми. Недопустимые представления не должны влиять на вывод программы.

Поначалу я немного удивился, ведь мне не пришлось ничего делать для соблюдения этого правила; но на самом деле это неудивительно, ведь я уже сузил входные данные FizzBuzz до только допустимых значений в нужном нам интервале (0-1000).

11. Во входном массиве допускаются отрицательные числа, их нужно игнорировать.

Как и в случае с предыдущим правилом, мой FizzBuzz работал безупречно! Любые входные данные, не состоящие из символов, представляющих числа в интервале 0-1000, отбрасывались и даже могли обрабатываться другим типом, если того потребует правило. Теперь меня было не остановить: никакое правило не заставило бы меня провалить собеседование!

12. Если язык допускает это, входные данные могут быть любым скалярным типом. Любые входные данные, отличающиеся от массива, должны приводить к выводу пустой строки.

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

14. Десятичный 0 с дробной частью (0.0) и отрицательный 0 с дробной частью (-0.0) должны иметь своё собственное представление и обрабатываться как десятичные числа с дробной частью (выводить пустую строку). (Это правило кажется довольно странным, если компания действительно хотела, чтобы целочисленный ноль не выводил FizzBuzz).

На этом моменте собеседующий был удивлён тем, что я ничего не делал, но FizzBuzz при этом работал по правилам.

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

Я подумал, что они обсуждают мой наём, но, похоже, вместо этого они думали, что делать с fizzbuzz, который без всяких проблем побеждает любое правило. Возможно, они хотели оценить мои навыки отладки/рефакторинга, но FizzBuzz был идеальным.

Спустя несколько секунд коллега собеседующего включил свой микрофон и сказал, что мы ещё не закончили и что будут ещё правила. Но для начала я должен изменить своё решение, потому что жёстко прописанная SUM_TABLE — это жульничество, потому что частично жёстко прописывает решение задачи.

Я на это не купился. У многих алгоритмов есть готовые матрицы, векторы или константы, а мне нельзя использовать матрицу 10x10?

Как это можно сделать в менее чем 30 строках, если у нас нет даже базовых математических операций? TS — очень компактный язык. Типы ещё более компактны, но что, если кто-то выбрал C или Java?

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

15. Создавать готовые матрицы запрещено.

Поначалу я не знал, что с этим делать: казалось, я ограничил свои возможности, решив использовать типы Typescript, и у меня не было достаточно времени, чтобы переписать всё это с нуля на обычном Typescript с соблюдением правил. Я даже не знал, как написать FizzBuzz с этим правилом на обычном Typescript.

Собеседующий сказал мне, что на одном из правил я должен был вносить изменения в код, потому что один из проверяемых им аспектов — это способность кандидатов к отладке. Он хотел порасспрашивать о рассуждениях кандидата в процессе отладки. Также он сказал, что вполне нормально, если я не решу эту задачу и что ценятся попытки или правильная обработка хотя бы некоторых видов входных данных. Под конец он сказал мне, что если я нарушу некоторые правила, то решение всё равно может быть рассмотрено; всё зависит от конкретных нарушенных правил и серьёзности нарушений. Например, он бы принял решение в 50 строках длиной до 110 символов.

Когда я нашёл путь к решению, мои нейроны уже нагрелись выше своей оптимальной температуры.

Если бы числа, кратные 3, следовали тому же правилу, что и кратные 5 (проверки последней цифры), то алгоритм был бы тривиальным, но математика оказалась не на моей стороне.

Дурацкая математика постоянно ставит подножки! Надо исправить её так, чтобы числа, кратные 3 и 5 можно было определять по их последней цифре.

У меня под рукой не было бумаги, потому что она никогда не пригождалась мне во время собеседований. Я плохо справляюсь с вычислениями в голове, поэтому способен был лишь составлять теории, почему 5 следует этому правилу, а 3 нет. К счастью, мне повезло с первой попытки!

Я рассуждал так:

Есть ли какие-то другие числа, с которыми это происходит?

Да, числа, кратные 2, оканчиваются на 2, 4, 6, 8, 0.

Этому правилу следуют только 5 и 2, и оба они — делители 10 (основания системы счисления). Отлично!

Все делители основания обладают этим свойством: при прибавлении делителя к самому себе n раз, где n — произведение всех других делителей, ещё одно прибавление к основанию делает их последнее число исходным числом, и возникает периодичность. Числа, кратные делителю основания, имеют base/n возможных последних цифр.

Например, если взять 2 из основания 10, то другой делитель будет 5, и когда мы доберёмся до 2+2+2+2+2 (2*5), следующее + 2 создаст число, закачивающееся на 2, и образуется периодичность.

Если мы возьмём 5 из основания 10, то другим делителем будет 2, и произойдёт то же самое: мы добираемся до 5+5 (5*2) и после прибавления ещё одной 5 возникает период.

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

А теперь самое простое! Нужно лишь закодировать числа по основанию 15, и мы сможем применить правило чисел 2 и 5 к числам 3 и 5!

Использование основания 15 допускалось, потому что я мог использовать любой другой символ, который можно ввести одним нажатием, поэтому 0-9 и A-E не нарушали правило.

Я изменил представление на основание 15, для тестирования при помощи (<number>).toString(15) в консоли браузера преобразовал разные числа по основанию 15, и всё сработало!

Коллега собеседующего засмеялся, и оба они были удивлены тем, что мне это не только удалось, но и я пришёл к гораздо более короткому и удобочитаемому решению (если не обращать внимания на то, что все числа теперь имели основание 15).

Я подумал, что мне больше не дадут новых правил, потому что последнее было придумано на ходу коллегой собеседующего, но я ошибался. Они перелистнули Powerpoint на следующий слайд, и вот что я увидел:

16. Если число кратно 3 и 5, оно должно выводить только «Bazz».

Фух! Ну, это просто. Думаю, после придуманного правила о запрете матриц можно было считать всё остальное простым, но тут действительно достаточно было скопипастить одну строку.

Мне показалось странным, что это правило было последним.

Возможно, из-за него многие решения нарушают какое-то правило или при некоторых входных данных оно вызывает забагованное поведение?

Кажется, как будто это правило должно быть одним из первых. Для него достаточно добавить ещё одно условие и удалить из Fizzer и Buzzer «0» как один из допустимых конечных символов.

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

Моё итоговое решение было таким:

type DATA = ["0", "2", "3", "7", "5", "20"]; //Числа, закодированные по основанию 15. Их эквиваленты по основанию 10 - это 0, 2, 3, 7, 5, 30
type _ = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "A" | "B" | "C" | "D" | "E"; //Допустимые цифры по основанию 15
type TailOf<T> = T extends _ ? T : T extends `${_}${infer Tail}` ? TailOf<Tail> : "";
type Fizzer<T> = TailOf<T> extends "3" | "6" | "9" | "C" ? 'Fizz' : '';
type Buzzer<T> = TailOf<T> extends "5" | "A" ? 'Buzz' : '';
type Bazzer<T> = TailOf<T> extends "0" ? 'Bazz' : ''; //Числа, заканчивающиеся на 0,  кратны основанию (15)
type FizzBuzz<T> = T extends `${_}${_|""}${_|""}` ? `${Fizzer<T>}${Bazzer<T>}${Buzzer<T>}` : "";
type Folded<T> = T extends [infer Head, ...infer Tail] ? `${FizzBuzz<Head>}${Folded<Tail>}` : "";
type Result = DATA extends [] ? 'Cronk' : Folded<DATA>;
     //^ BazzFizzBuzzBazz

8 строк, самая длинная из которых состоит из 98 символов!

Код соблюдает все правила, даже правила форматирования, однако он компактен, читаем и надёжен.

Если убрать части с Bazz и Cronk, то это просто «обычный» FizzBuzz. Над многими правилами мне даже не пришлось думать, всё работало благодаря проверке типов!

До предела в 30 строк у меня всё ещё было много места. Я запросто мог добавить ещё правил, например, ограничить входные данные только интервалом 0-1000, заставить отрицательные числа выводить FizzBuzz и так далее.

На этом моменте я понял, что это конец: FizzBuzz решён в 8 строках. Соблюдаются 16 правил, причём многие из них связаны с проверкой входных данных, что практически не требуется, поскольку недопустимые входные данные уже преобразовывались в пустую строку.

Больше в FizzBuzz нельзя внести почти никаких изменений, которые бы не были тривиальными и легко реализовывались в 22 оставшихся строках.

Собеседующий перелистнул слайд, и это был конец презентации.

Я ожидал хотя бы слайда с поздравлениями, но он просто был полностью чёрным.

Меня поздравили с тем, что я добрался до конца, и сказали ждать ответа от компании и ещё одного собеседования.

Прошёл месяц, но я не получил ни ответа, ни обратной связи…

Я знал, что не хватало квалификации для этой вакансии:

• У меня нет университетской степени и какого-то другого формального обучения.
• Им нужен был сениор-разработчик с четырьмя годами опыта. У меня было два.
• Им нужен был опыт работы с AWS. Я никогда с ним не работал.
• У меня плохое английское произношение, несмотря на то, что я умею читать, писать и понимать язык.

Но я ожидал хотя бы письма, в котором говорилось, что они нашли кандидата, лучше подходящего на должность, или что мне не хватает необходимого опыта.

По большинству вакансий я не дохожу даже до технического интервью, меня сразу отклоняют ещё до собеседования, а в тех менее чем 5% случаях, когда я добираюсь до собеседования, меня отклоняют на личном собеседовании. Но всё равно очень печально добраться до технического собеседования, пройти его с этим безумным FizzBuzz, однако так и не получить ответа.

Примечание: все версии FizzBuzz, кроме последней, я воссоздал по памяти. После собеседования у меня сохранилась только последняя версия. Правила были изложены по заметкам с отличиями от последнего кода FizzBuzz, которые я оставлял в комментариях.

▍ Про вакансию и про меня

Этот fizzbuzz был написан в собеседовании на удалённую должность в маленькой компании из Нидерландов. В Linkedin написано, что в ней меньше 50 сотрудников. Я не думаю, что было бы справедливо указывать её название, чтобы пристыдить её.

Вакансия была на должность бэкенд-разработчика на Node.js. В вакансии было написано, что компания использует Express, но после технического собеседования мне сообщили, что используется Nest.js. Не понимаю, в чём смысл искать разработчиков на фреймворке, которым не пользуется компания. К тому же, хоть я и работал с Nest.js, мне в нём многое не нравится, и, в частности, принудительное использование ООП в языке (TS), который, конечно, может использоваться для ООП, но лучше показывает себя в функциональном и декларативном программировании. Отличным примером этого стал мой FizzBuzz, но при хорошей зарплате я бы не против был писать кучу бойлерплейта Nest.js. В конце концов, в своей предыдущей компании я работал с довольно старой версией, и мне приходилось бороться с неприятными багами экосистемы, например, с условиями гонки typeORM при использовании pg bouncer, которые возникали только при высоких нагрузках и мешали освобождению подключений в пул.

Это было моё первое собеседование в иностранную компанию и первый опыт разговоров на английском. Хотя я ходил в государственную «билингвальную» среднюю и старшую школу, «билингвальность» лишь означала, что по истории и естественным наукам был дополнительный тонкий учебник на английском, а на экзаменах 1-2 из 8-20 заданий были составлены на английском. Иногда это были дурацкие заданий вида «заполните пробелы», в которых нужно вписывать в предложения конкретные ключевые слова (часть из них просто взяли из учебника).

Уровень зарплаты не походил на нидерландский: мне предложили 50 тысяч евро в год «грязными». Во время личного собеседования мне не сообщили, буду ли я работать как подрядчик или в штате, просто сказали, что просто ищут подходящего человека, а подробности обсудят позже.

Может показаться, что 50 тысяч евро — не такая большая зарплата для сотрудника с четырёхлетним опытом для этой вакансии, и, наверно, поэтому меня выбрали, несмотря на несоответствие требованиям. Для меня это очень высокая зарплата, в два с лишним раза больше предыдущей; я бы буквально стал человеком с самой высокой зарплатой в моём городе по официально публикуемым налоговым данным. Такая зарплата перевела бы меня в список 10% людей с самой высокой зарплатой в Испании.

Стоит отметить, что я живу на задворках города с населением менее трёхсот человек, среди которых я единственный младше тридцати. Здесь нет проводного Интернета, я вынужден пользоваться безлимитным тарифом 4G (к счастью, антенна находится в прямой линии видимости моего окна). Можно понять, что люди здесь зарабатывают не очень много.

Для сравнения: моя первая работа была удалённой фулстек-должностью в маленькой испанской компании; изначально я получал 20 тысяч евро, а спустя два года, непосредственно перед тем, как меня уволили, зарплата повысилась до 22 тысяч. Огромная кодовая база фронтенда, низкое качество кода и ещё более низкое качество структуры проекта. Во фронтенде не хватало техлидов (впрочем, в бэкенде и devops руководство было очень хорошим). Во фронтенде использовался React, перемешанный с CRA и сырым JS; и разработчики, и руководство фронтендом отказались от TS, как от «излишнего повышения сложности».

Telegram-канал со скидками, розыгрышами призов и новостями IT ?