Лучший технический вопрос, который мне задавали на собеседовании

Много воды утекло с тех пор, как я в последний раз участвовал в собеседовании по программированию как соискатель. Но до сих пор помню особенно полюбившийся мне вопрос с такого собеседования. Дело было в MemSQL, году так в 2013. (Они даже успели переименоваться, поэтому, полагаю, конкретно этот вопрос они на собеседовании уже не задают. Не чувствую вины за то, что выдаю его. Это отличная история, которая также кажется мне поучительной; просто раньше я о ней никогда не писал).

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

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

Знакомство с memcached

Знаете, что такое memcached? Нет? Ну, это же хранилище ключей и значений, действующее в оперативной памяти. (Вот их страничка.) Давайте скачаем код этой базы данных и соберем ее – покажу вам, что она умеет делать.

Возможно, вам понадобится brew install libevent и, может быть, еще какое-нибудь хозяйство, чтобы успешно собрать memcached. Определиться с этим будет несложно, но, в любом случае, обустройство среды разработки не входило в задачу. Можете предположить, что собеседующие уже дали вам доступ к машине под Linux, в которой уже прописаны все нужные зависимости.

Чтобы впечатление было аутентичным, как в 2013 году, давайте обойдемся без репозитория на Github и распакуем из архива tar современные исходники дистрибутива:

curl -O https://memcached.org/files/memcached-1.4.15.tar.gz
tar zxvf memcached-1.4.15.tar.gz
cd memcached-1.4.15
./configure
make

Вот мы и собрали исполняемый экземпляр memcached. Давайте его запустим:

./memcached

Можем пообщаться с сервером через порт memcached, заданный по умолчанию, это порт 11211. В сущности, его протокол – обычный текст, поэтому для обмена информацией нам подойдет старый добрый telnet. (Если у вас уже нет telnet в наличии, замените включения telnet на nc -c)

$ telnet 127.0.0.1 11211
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.

Играем с memcached

memcached – это хранилище ключей и значений. Таким образом, мы можем приказать ему что-либо запомнить (в виде ассоциации между ключом и значением), а затем снова спросить этот ключ – и система ответит нам, какое значение она по этому ключу запомнила. В memcached все ключи являются строками в формате ASCII, а значения – это всегда произвольные потоки байт (то есть, их длину вам придется указывать вручную). Например, введите в вашем сеансе telnet следующее:

set fullname 0 3600 10
John Smith

Так вы приказываете memcached запомнить ассоциацию между строковым ключом fullname и 10-байтным значением John Smith. Другие числа в этой строчке – это значение «флаги» (0), запоминаемое вместе со значением потока байт, а также период до устаревания (3600) в секундах, по истечении которого memcached забудет эту ассоциацию. В любом случае, как только вы введете две эти строчки, memcached ответит:

STORED

Теперь можно извлечь значение fullname, введя в тот же самый сеанс telnet:

get fullname

memcached ответит:

VALUE fullname 0 10
John Smith
END

Можно перезаписать значение, ассоциированное с fullname, выдав еще одну команду set fullname. Также можно запросить memcached модифицировать значение тем или иным образом; например, есть специальные выделенные команды для операций append и prepend.

append fullname 0 3600 6
-Jones
STORED
get fullname
VALUE fullname 0 16
John Smith-Jones
END

Разумеется, если бы вы хотели прикрепить -Jones к fullname, сделав это из клиентской программы, то могли бы поступить примерно так:

# pip install python-memcached
import memcache
mc = memcache.Client(['127.0.0.1:11211'])
v = mc.get('fullname')    # получить старое значение memcached
v += '-Jones'             # прикрепить -Jones
mc.set('fullname', v)     # установить новое значение в memcached

Но преимущество выделенной команды append, применяемой в memcached – в том, что она гарантированно будет выполняться атомарно. Если у вас множество клиентов подключено к одному и тому же серверу memcached, и все они одновременно пытаются прикрепить один и тот же ключ, то из-за версии get/set некоторые из этих обновлений могут быть потеряны, тогда как с append вы можете быть уверены, что все они окажутся учтены.

Еще одна выделенная команда, выполняемая атомарно – это incr:

set age 0 3600 2
37
STORED
incr age 1

memcached реагирует на значение, полученное после инкремента:

38

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

memcached, конечно же, тоже запоминает приращаемое значение:

get age
VALUE age 0 2
38
END

Обратите внимание: 37 и 38 у нас по-прежнему сохраняются и возвращаются в виде байтовых строк; они декодируются из ASCII в целые числа и обратно в рамках атомарной операции. Если вы попытаетесь incr нецелочисленное значение, то получите ошибку:

incr fullname 1
CLIENT_ERROR cannot increment or decrement non-numeric value

Наконец, отметим, что incr – это полноценная операция сложения: можно сделать инкремент (или декремент, decr) на любое положительное значение, а не только на 1.

incr age 10
48
decr age 10
38
incr age -1
CLIENT_ERROR invalid numeric delta argument

Кстати, когда закончите разговоры с memcached и захотите разорвать соединение, можете ввести в memcached команду quit. (Если вы работаете с nc -c, то Ctrl+D тоже подойдет. Либо просто перейдите в консоль, где работает сервер memcached, и нажмите Ctrl+C, чтобы его положить.)

Задача: изменить memcached

При помощи команд incr и decr memcached предоставляет встроенный способ, чтобы атомарно прибавить k к числу. Но другие арифметические операции таким способом не предоставляются, в частности, нет «атомарной операции умножения на k».

Вот вам задача на программирование: добавьте команду mult в memcached.

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

mult age 10
380

У вас три часа. Поехали!

Анализ

Для технического собеседования эта задача просто отличная, так как она позволяет четко разделить весь пул соискателей на три различных типа:

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

Кстати, MemSQL по состоянию на 2013 год оперировала чрезвычайно таинственным и высокопроизводительным C++11, поэтому был плюсом (а не минусом) тот факт, что эта задача требует бегло владеть C. Если у вас вся база кода написана на Python и Go, то вы, вероятно, не станете использовать memcached в задачах для собеседования.

Тип 1 рассмотрит проблему и скажет: “Ах! Конечно же, понятно, как это сделать. Умножение – это просто многократное сложение, а у на уже есть готовая субпроцедура для сложения, в виде incr. От нее и будем плясать. Да, но не станем добавлять константу к значению x, а будем складывать значение x с самим собой… и вся эта штука должна быть атомарной. Посмотрим-ка, как тут работает блокировка….” Так все три часа окажутся потрачены на все более и более глубокое зарывание в разные кроличьи норы – и ничего работоспособного такой соискатель вам все равно не выдаст. Соискателей из этой группы мы также на работу не берем.

Тип 2 рассмотрит задачу и скажет: «Ах! Ну тут же все понятно! Умножение – все равно, что сложение, только там, где при сложении +, я должен поставить *». Поэтому он берется за копипаст, меняет все + на * - и справляется за полтора часа. У кандидатов из этой группы весьма высоки шансы получить оффер.

Наилучшие соискатели заметят, что времени у них остается еще много, поэтому отполируют свою работу – например, убедятся, что форматирование везде единообразное, добавят модульные тесты или уточнят свои «дизайнерские решения», чтобы быть уверенными, что смогут обоснованно ответить на вопрос: «а почему вы так сделали»?  

Пошаговый разбор

Чтобы убедиться, что мои оценки времени на решение задачи – верного порядка, вчера вечером я выполнил всю эту задачу сам.

Вероятно, этот раздел задолбает всех, кроме самых мазохистов, поэтому если вы не из таких – смело переходите к Заключению.

Для начала я загнал в grep строку "incr" (в кавычках), поскольку мы хотим сымитировать существующую команду incr, и ее нужно где-то распарсить. Это привело меня к части функции process_command, которая выглядит так:

} else if ((ntokens == 4 || ntokens == 5) && (strcmp(tokens[COMMAND_TOKEN].value, "incr") == 0)) {
    process_arithmetic_command(c, tokens, ntokens, 1);
} else if ((ntokens == 4 || ntokens == 5) && (strcmp(tokens[COMMAND_TOKEN].value, "decr") == 0)) {
    process_arithmetic_command(c, tokens, ntokens, 0);

Аргумент со значением 0 или 1 соответствует параметру bool incr. Я изменил его на int opcode, а вызывающие стороны изменил так:

} else if ((ntokens == 4 || ntokens == 5) && (strcmp(tokens[COMMAND_TOKEN].value, "incr") == 0)) {
    process_arithmetic_command(c, tokens, ntokens, 1);
} else if ((ntokens == 4 || ntokens == 5) && (strcmp(tokens[COMMAND_TOKEN].value, "decr") == 0)) {
    process_arithmetic_command(c, tokens, ntokens, 0);
} else if ((ntokens == 4 || ntokens == 5) && (strcmp(tokens[COMMAND_TOKEN].value, "mult") == 0)) {
    process_arithmetic_command(c, tokens, ntokens, 2);

(С точки зрения проектирования такие волшебные числа – весьма плохое решение, но зато оно быстрое и позволяет мне быстро продвигаться вперед. Через десять минут мне в голову придет решение получше, поэтому я пересмотрю этот код).

Пролистаю тело process_arithmetic_command, там я буду искать ссылки на инкремент и декремент. Сообщение об ошибке "CLIENT_ERROR cannot increment or decrement non-numeric value" кажется несколько неоптимальным, поэтому изменю этот код на

if (opcode == 2) {
    out_string(c, "CLIENT_ERROR cannot multiply non-numeric value");
} else {
    out_string(c, "CLIENT_ERROR cannot increment or decrement non-numeric value");
}

И схожим образом – чуть ниже:

+if (opcode == 2) {
+    c->thread->stats.mult_misses++;
+} else if (opcode == 1) {
-if (incr) {
     c->thread->stats.incr_misses++;
 } else {
     c->thread->stats.decr_misses++;
 }

Отметил в голове, что нужно добавить поле mult_misses к любым c->thread->stats; но пока рвемся вперед. Если о чем-то забуду – то компилятор напомнит мне об ошибке.

-switch(add_delta(c, key, nkey, incr, delta, temp, NULL)) {
+switch(add_delta(c, key, nkey, opcode, delta, temp, NULL)) {

При помощи Grep вновь спускаемся до add_delta.

 enum delta_result_type do_add_delta(conn *c, const char *key, const size_t nkey,
-                                    const bool incr, const int64_t delta,
+                                    const int opcode, const int64_t delta,
                                     char *buf, uint64_t *cas,
                                     const uint32_t hv) {

Эта сигнатура нарушает мою ориентировку по const-корректному коду в том, что передает массу вещей «по const-значению», но нас так просто не проведешь. Заменим bool на int и движемся дальше.

Наконец, находим искомое место – то, где нужно заменить + на *! Этот путь в коде принимает вид:

+if (opcode == 2) {
+    value *= delta;
+    MEMCACHED_COMMAND_MULT(c->sfd, ITEM_key(it), it->nkey, value);
+} else if (opcode == 1) {
-if (incr) {
     value += delta;
     MEMCACHED_COMMAND_INCR(c->sfd, ITEM_key(it), it->nkey, value);
 } else {
     if(delta > value) {
         value = 0;
     } else {
         value -= delta;
     }
     MEMCACHED_COMMAND_DECR(c->sfd, ITEM_key(it), it->nkey, value);
 }

Отметим, что нужно реализовать MEMCACHED_COMMAND_MULT, едем дальше. Чуть ниже отметим, что для slab_stats требуется поле mult_hits.

Вот мы и дошли до конца do_add_delta. Подождите, это же do_add_delta… а что такое add_delta? Ах, так она вызывается из двух мест. И в первом из них bool incr устанавливается c->cmd == PROTOCOL_BINARY_CMD_INCREMENT. Поискав через Grep PROTOCOL_BINARY_CMD_INCREMENT выясняем, что здесь в protocol_binary.h есть перечисление всех команд! Следует им воспользоваться. Добавим к этому перечислению PROTOCOL_BINARY_CMD_MULTIPLY и отрефакторим всю ранее сделанную работу так, чтобы использовалось PROTOCOL_BINARY_CMD_{DECREMENT,INCREMENT,MULTIPLY}, а не волшебные числа 0,1,2. int opcode можно оставить в виде int, поскольку, если поискать при помощи grep имя перечисляемого типа (protocol_binary_command) – убедимся, что практически нигде в базе кода этот тип не используется по имени.

Реализовав MEMCACHED_COMMAND_MULT в trace.h, также обнаруживаю, что мне понадобится макрос MEMCACHED_COMMAND_MULT_ENABLED. Где он используется? Нигде. Окей. Все равно его добавим. (Забор Честертона: если я не знаю, для чего существуют эти макросы _ENABLED, то я определенно не должен пытаться сделать что-нибудь новаторское с тем новым _ENABLED, что окажется у меня. Не буду отрываться от коллектива.)

Разобравшись с оставшимися ошибками компилятора, добавлю поле mult_hits в struct slab_stats, сразу за incr_hits и decr_hits. Команда git grep incr_hits показывает, что он используется во множестве мест; когда закончу с ним, git grep mult_hits покажет такое же количество включений. Строчка

out->incr_hits += stats->slab_stats[sid].incr_hits;

коварна, потому что имеющуюся у меня копию этой строчки нужно изменить в двух местах. Также добавлю поле mult_misses в struct thread_stats и изменю

if (c->cmd == PROTOCOL_BINARY_CMD_INCREMENT) {
    c->thread->stats.incr_misses++;
} else {
    c->thread->stats.decr_misses++;
}

на

switch (c->cmd) {
    case PROTOCOL_BINARY_CMD_INCREMENT: c->thread->stats.incr_misses++; break;
    case PROTOCOL_BINARY_CMD_DECREMENT: c->thread->stats.decr_misses++; break;
    case PROTOCOL_BINARY_CMD_MULTIPLY: c->thread->stats.mult_misses++; break;
}

Строго говоря, нам не требуется менять add_delta как таковую, чтобы она, ранее принимавшая const int incr, теперь принимала const int opcode, но мне такая идея нравится – поэтому изменю.

До состояния «код готов» добрался за 25 минут. Что ж, испробуем!

set age 0 3600 2
37
STORED
mult age 10
27

Упс.

Возвращаюсь в ту точку, где предположительно должно происходить умножение…

if (opcode == 2) {
    value *= delta;

Ха! Здесь должен использоваться мой новый вариант PROTOCOL_BINARY_CMD_MULTIPLY. Исправлю это. Фактически, нужно ввести в grep opcode ==  и исправить это еще в нескольких местах, ранее упущенных. За 32 минуты дохожу до состояния «код правда готов». На сей раз кажется, что код действительно работает как надо. Проведу несколько тестов вручную:

set age 0 3600 2
37
STORED
mult age 10
370
mult age 2
740
mult age -1
CLIENT_ERROR invalid numeric delta argument

set fullname 0 3600 10
John Smith
STORED
mult fullname 1
CLIENT_ERROR cannot multiply non-numeric value
mult
ERROR
mult bogus 1
NOT_FOUND

Проверяю это поведение на целочисленном циклическом переносе и также проверяю синтаксис mult age 10 noreply, чтобы убедиться, что и он поддерживается. Поскольку я все реализовал копипастом, в принципе невозможно представить, чтобы эти вещи не работали так же гладко, как в случае с incr и decr.

Хмм… при всем этом ручном тестировании нужно, пожалуй, написать и несколько настоящих тестов. Есть ли эти тесты в репозитории? Да, под t/. Команда make test собирает и выполняет их. Поэтому скопирую t/incrdecr.t в t/mult.t и изменю. Дохожу до стадии «Код и тесты готовы» за 50 минут.

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

Вижу, в binary.t. есть еще тесты. Полагаю, и на них следует взглянуть, хотя и не хочется. Ага, точно, там лежит еще одна копия перечисления команд. Я должен туда добавить, как минимум, CMD_MULTIPLY.

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

Примерно на отметке 60 минут я повторно выхожу на рубеж «код и тесты готовы».

Но, продираясь сквозь t/udp.t, нахожу там множество тестов, посвященных «двоичному протоколу» (а не протоколу в «обычном тексте», о котором шла речь при постановке задачи). Должен ли я изменить двоичный протокол, равно как и обычный? На самом деле, я это уже сделал, благодаря неизбирательному diff в функции dispatch_bin_command.

    case PROTOCOL_BINARY_CMD_INCREMENT:
    case PROTOCOL_BINARY_CMD_DECREMENT:
+   case PROTOCOL_BINARY_CMD_MULTIPLY:
        if (keylen > 0 && extlen == 20 && bodylen == (keylen + extlen)) {
            bin_read_key(c, bin_reading_incr_header, 20);
        } else {
            protocol_error = 1;
        }
        break;

Но выше замечаю «тихие» версии тех же самых кодов операций:

case PROTOCOL_BINARY_CMD_INCREMENTQ:
    c->cmd = PROTOCOL_BINARY_CMD_INCREMENT;
    break;
case PROTOCOL_BINARY_CMD_DECREMENTQ:
    c->cmd = PROTOCOL_BINARY_CMD_DECREMENT;
    break;

Не уверен, зачем они нужны, но, чтобы провернуть мой фокус с копипастом в t/udp.t, придется добавить один из них в mult. (Опять забор Честертона: не знаю, почему важны эти «тихие» коды операций, но, если у incr и decr они есть, то и в mult такой тоже должен быть.) Поэтому добавляю PROTOCOL_BINARY_CMD_MULTIPLYQ и распространяю это изменение на всю базу кода.

На данном этапе я просто раз за разом прогоняю make test и спотыкаюсь о причуды тестового кода (который весь написан на Perl и полон функций о пяти или шести параметрах). full of five- and six-parameter functions). Запоздало осознаю, что некоторые из тестов не проходят только потому, что начинаются с каких-то таинственных пометок вроде “Я планирую прогнать ровно 95 тест-кейсов», а вот я добавляю лишние тесты – и из-за этого план проваливается.

Примерно через 90 минут считаю, что все сделано. Некоторые тесты на Perl, написанные для двоичного кода, по-прежнему не проходят, но я уверен, что проблема здесь с моими тестами, а не с серверным кодом. Здесь кроется тайный изъян подхода «скопипастить и поменять имена»: тесты на Perl для incr в принципе имеют вид

initialize num to zero
check that "incr num 1" returns 1
check that "incr num 1" returns 2
check that "incr num 1" returns 3

(с обфускацией в несколько уровней косвенности), поэтому, когда я проделываю очевидную операцию с умножением, у меня выходит:

initialize num to zero
check that "mult num 1" returns 0
check that "mult num 1" returns 0
check that "mult num 1" returns 0

Этот тест никуда не годится. Что ж, если бы суть этого челленджа была «сделать хорошие тесты», то я бы потратил на это еще час. Или, если бы я решал рабочую задачу, а не писал пост для блога, тоже потратил бы лишний час. Но для этого поста – довольно.

Заключение

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

Эта задача особенно хорошо подобрана для собеседования, поскольку предполагает лишь один верный ответ: «заменить bool incr на int opcode» (или любой изоморфный аналог). Вместе эта база кода и постановка задачи весьма ясно подразумевают, что в настоящий момент есть два кода для арифметических операций, а ваша задача – довести их количество до трех.

Представьте, насколько более разветвленной была бы эта задача, не будь у memcached команды decr! Допустим, команда process_arithmetic_command называлась бы process_increment_command, и add_delta не принимала бы bool incr в качестве параметра, и т.д. Тогда от соискателя требовалось бы более масштабное творческое решение: добавить этот параметр (в какой позиции?) или клонировать весь путь кода (начиная  с какого уровня?). Клонировать даже одну из этих функций – вероятно, не лучшее решение, но мне могло потребоваться минут двадцать, прежде, чем это осознать.

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