#реалити
Начало истории тут
Итак, я успешно прошёл первое собеседование в компанию "5 ns" (название выдумано) на позицию senior C++ developer. Сегодня расскажу, что было на втором.
Напомню, цель таких историй — показать, что на самом деле важно знать и уметь, чтобы устроиться разработчиком. У меня нет цели разоблачать компании, поэтому я либо меняю название (как здесь), либо не даю много деталей о задачах.
На интервью было отведено 90 минут, за которые предполагалось решить "одну или две задачи". Задачи расскажу AS IS, потому что знание условий в данном случае вообще никак не помогает пройти интервью 😆
1️⃣ Первая задача — написать аллокатор для объектов типа
Т, все методы должны работать за O(1) и не должны использовать динамическую аллокацию. Интерфейс:template <class T, size_t N>
class Allocator {
public:
Allocator();
template <typename... Args>
T* AllocateAndConstruct(Args&&...);
void DeallocateAndDestroy(T* ptr);
};
Дополнительное требование — наложить как можно меньше ограничений на тип
Т. Что я применил в своём решении:
— ручная реализация вставки и удаления в/из односвязного списка
—
placement new и ручной вызов деструктора 🤔— выравнивание сырой невыровненной памяти
Чтобы такое закодить без багов и оставить себе время на вторую задачу, нужен большой опыт в С++ 🥵. Онлайн-курсов тут точно недостаточно. Хотя работу со связным списком можно в совершенстве освоить на «Алгоритмическом фундаменте» 😉
Я реализовал своё решение так, что осталось достаточно времени на вторую задачу.
2️⃣ Формулировка второй задачи крайне проста: "Реализовать multiple producer single consumer очередь для uint64_t. Самое главное — максимальная скорость записи"
Ничё так, правда? Как вторая задача на 90-минутном собесе 🤯
Очевидный вариант, приходящий в голову, — мьютекс и
std::queue — естественно, не устроил интервьюера по скорости. Я озвучил пару неудачных идей, а потом вспомнил, что в далёких 2015-2016 гг. много интересовался lock free структурами данных. И понял, что здесь хорошо подойдёт односвязный lock free список. Каждый producer добавляет в начало списка свои данные, а consumer подменяет его голову на
nullptr и спокойно вычитывает все данные без contention'а.Вообще ручная реализация любой lock-free структуры данных — это большой геморрой 🤕, если не сталкиваешься с этим регулярно (а я не сталкиваюсь). Но здесь простейшая из всех возможных ситуация (из списка даже не надо удалять), так что написать можно.
Я успел это всё реализовать. В момент, когда истекла 90-я минута, интервьюер сказал: "Ок, у меня больше нет вопросов к коду" 👍
❗️Итого, чтобы справиться с задачами на втором собеседовании в компанию "5 ns" пригодились:
— умение самому реализовывать односвязный список — рассказывайте после этого, что алгоритмы не нужны разработчикам 😜
— понимание, что делают операторы
new и delete, и умение работать с placement new— работа с выравниванием памяти
— знакомство с single/multiple producer, single/multiple consumer очередями
— знакомство с lock free структурами данных и понимание, как они реализуются на
atomic'ах— а ещё понимание, что работа С++ бекендером на крутом фреймворке, который большинство задач решает за вас, ваще никак не готовит вас к такому собесу 🤔 (это я про свои три года в Яндекс Еде)
Если пост наберёт 100 🔥, выложу код своих решений. А в следующем посте расскажу, какой фидбек я получил по итогу двух этих собеседований.
Пересылайте пост знакомым, чтобы расширять осведомлённость сообщества о том, к чему себя надо готовить.
⬇️ Продолжение истории ⬇️