Мои вопросы на собеседовании: переверни массив и потерянные монетки

Где-то в 2010–2011 году я начал участвовать в собеседованиях новых людей. Сначала мы просто болтали, и многие нормально, хорошо отвечали на вопросы.

Числа, которые делятся на 5. Однажды пришёл человек, который до этого работал в государственной конторе. Я попросил его написать простую функцию: есть массив чисел, выведи все, которые делятся на 5. Элементарная задача. Я ждал, что он напишет на C# что-то красивое на LINQ:

numbers.Where(x => x % 5 == 0).ToList().ForEach(Console.WriteLine);

А он начал перебирать все числа от нуля до int.MaxValue с шагом 5 и для каждого проверять, есть ли оно в массиве:

for (int i = 0; i != int.MaxValue; i += 5)
    if (numbers.Contains(i))
        Console.WriteLine(i);

Мало того что это перебор двух миллиардов чисел, этот цикл ещё и никогда не закончится. int.MaxValue — это 2 147 483 647, на 5 оно не делится, и i его просто перешагнёт. Дальше переполнение, i уходит в минус, и поиск начинается заново. Человек вообще не понимал, что пишет.

Тогда я понял: людям обязательно нужно дать что-то написать на бумажке. Что-то простое.

Переверни массив. После этого моим любимым заданием стал разворот массива задом наперёд. И люди сразу ловились.

Первая ошибка — стандартная: цикл идёт от первого элемента до последнего, и массив переворачивается дважды.

for (int i = 0; i < a.Length; i++)
{
    int t = a[i];
    a[i] = a[a.Length - 1 - i];
    a[a.Length - 1 - i] = t;
}

Я ещё троллил: «Ну, запускаем — что видим?» А видим ровно то же самое, что было, и человек ломает голову, почему. Дальше я подлавливал на элементе посередине: при нечётной длине он меняется местами сам с собой — «о, блин, да». И классика с индексом: a[a.Length - i] вместо a[a.Length - 1 - i], и на первом же шаге — выход за границу массива.

Однажды пришёл кандидат чуть ли не уровня технического директора или архитектора. Я говорю: напиши программку. Он: «Не буду писать». Я: «Ну тогда до свидания». Он: «Ну до свидания», — и ушёл.

Часто спрашивали: а почему на бумажке, а не на компьютере? Потому что задача элементарная. На компьютере я дал бы что-то большое, на целый вечер. А здесь мы посидим вдвоём пять-десять минут и заодно обсудим теорию. По-моему, нормальный программист прежде всего уточняет задание: какого размера массив, какие числа, какого типа, какие ограничения.

Два потока и один кошелёк. Позже, когда мы делали Blockchain Cuties, у нас работало несколько серверов, а внутри каждого — несколько потоков, и данные в базе терялись. Это был мой первый год на Java: до этого я писал в основном клиентские вещи, однопоточные трансляторы или Unity, где многопоточности почти нет, зато есть 3D и оптимизация. И я с удивлением понял, что мои же коллеги, которые работают с серверами, не понимают, что такое конкурентный доступ.

Так появилась моя классическая задача. Два потока параллельно читают из базы через ORM — Hibernate — один и тот же объект: кошелёк игрока, в нём 10 монет. В одном потоке игрок что-то покупает за 5, остаётся 5. В другом ему что-то продали, надо добавить 3, получается 13. Оба сохраняют. Что в итоге окажется в базе?

Человек чешет репу: «Ну, 13». — «А что не так?» — «Блин, не знаю. Транзакции, наверное, надо». — «А как тебе помогут транзакции?» И начинает путаться.

Сами по себе транзакции тут не спасают. Транзакция гарантирует, что её записи пройдут все или ни одной, но на уровне изоляции по умолчанию обе транзакции спокойно прочитают 10 и каждая запишет своё. Спасают более строгие уровни изоляции — тогда база отменит одну из транзакций, и её придётся повторить, — или явная блокировка строки. Но под нагрузкой блокировки работают медленнее.

Я переводил задачу на жизнь: «Вот ты пишешь программу продажи билетов. Как так выходит, что у тебя иногда будут теряться данные?» — «Блин, да, точно, будут». — «Хорошо, предложи варианты, а я буду подсказывать». И люди начинали городить: будем засекать время, будем проверять, записалось или нет. — «Да, но в середине этой проверки опять может вклиниться другой процесс». — «Ой, ужас, как же делать?»

А хороших решений здесь четыре-пять, и для них не нужно знать особенности Hibernate:

• Атомарный апдейт в SQL: UPDATE wallet SET coins = coins - 5 WHERE id = ? AND coins >= 5 — база сама считает от текущего значения, и в минус не уйти.
• Сериализовать: один сервис-воркер, который обрабатывает операции с кошельком по очереди.
• Леджер: хранить не баланс, а все дельты, и баланс считать из них.
• Пессимистическая блокировка: заблокировать строку на время операции.
• Оптимистическая блокировка: номер версии у записи. Мы обычно ставили её: в 99% случаев конфликта нет, и всё проходит. А если записать не получилось, пересчитываем и перезапускаем транзакцию.

Что я из этого вынес: я не люблю спрашивать про детали устройства фреймворков. Мне интереснее, как человек готов думать и учиться прямо сейчас, вместе со мной: я подсказываю на месте и вижу, как он рассуждает. А маленькая задача на бумажке за пять минут говорит о программисте больше, чем час разговоров.