Продолжаю рассказывать про процесс собеседования в стартап в Долине. Это уже пятая часть, если не читали предыдущие посты — можно начать с них:

первая серия
вторая серия
третья серия
четвёртая серия

После прочтения прошлого поста половина из вас проголосовали за то, что я успешно прошёл собеседование. Так и было 😉 Рекрутер написала мне, что следующий этап — это выполнение тестового задания. Задача звучала так: написать на C++ самый быстрый код для расчёта формул в электронной таблице. Понятно, что по сравнению с Google Таблицами формулы были сильно проще — нужно было реализовать только сложение отдельных ячеек друг с другом.

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

1. средство, которое будет измерять быстроту каждой новой версии;
2. какая-то базовая реализация, которая гарантированно работает правильно и с которой мы будем сравнивать корректность и скорость нашей самой быстрой версии.

Первым шагом я написал однопоточную реализацию задачи, потестировал её и убедился, что она работает правильно. Вторым шагом я воспользовался библиотекой Google Benchmark и создал набор бенчмарков, который позволял сравнивать реализации друг с другом. Дальше я уже начал создавать многопоточную версию своего решения и стремиться сделать её как можно более быстрой.

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

В какой-то момент, работая над многопоточной реализацией, я понял, что мне нужно провести исследование, чтобы понять, на каком количестве потоков достигается наилучшая производительность. На первый взгляд ответ очевиден: на количестве потоков равном количеству ядер. Однако я всё же решил поисследовать и получил очень странные результаты. Оказалось, что наибольшую производительность мой код выдаёт, если его запускать на 256 потоках. Это очень странно для 12-ядерной машины. И здесь я принял весьма спорное решение: решил довериться своему инструменту измерения.

В какой-то момент идеи, как сделать ещё быстрее, у меня закончились. Я скинул рекрутеру тестовое задание с описанием, в котором рассказал, почему я принял те или иные решения и почему мой код написан именно таким образом. Если вам интересно, что у меня получилось, ловите репозиторий.

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

To be continued...