В сети есть уйма постов и видео, где разбираются ответы на вопросы LeetCode. Но обычно рассмотрение в них происходит с позиции соискателя, а не работодателя. В этой же статье я приведу разбор собственной задачи по программированию, которую использовал при приёме людей на работу в Amazon, Google и Microsoft.
За 25 лет в сфере Big Tech я провёл более тысячи собеседований: чуть больше восьмисот в Amazon в качестве Bar Raiser, пару сотен в Microsoft и около сотни в Google.
Моя награда AWS Top Bar Raiser Q1.2020
В сфере Big Tech проводится три вида собеседований на должность инженера ПО: [1] по программированию, [2] по проектированию систем, [3] по навыкам управления и работы с людьми, пониманию культуры и так далее. Циклы собеседований обычно представляют комбинацию этих видов. Например, для кандидатов на должность SDE-I (младший инженер по проектированию систем) может присутствовать 3 собеседования по программированию, 1 по проектированию систем и 1 по навыкам управления. При этом на должность старшего инженера может проводиться 1 собеседование по программированию, 2 по проектированию систем и 3 по управленческим навыкам. Лично я предпочитаю не ограниченные временем собеседования по навыкам управления, так как они позволяют лучше понять кандидатов. Но всё же проверять навыки программирования тоже нужно, и этот этап является необходимым злом.
Дисклеймер: все собеседования по программированию ужасны, включая мои. Вам даётся всего 45 минут, чтобы сформировать рекомендацию о найме либо отказе, которая может изменить чью-то жизнь. И при этом люди никогда не раскрываются по-настоящему, так как находятся под давлением временны́х рамок, испытывают волнение и нервное истощение. При этом задаваемые вопросы должны вписаться в установленный промежуток времени и дать интервьюеру определённые сигналы. Я предпочитаю задавать более простые вопросы, чтобы построить качественный диалог, в котором смогу проанализировать ход соискателя.
Для меня гораздо важнее сама беседа, чем код, который человек пишет на доске. Какие при этом существуют компромиссы? Как найти между ними баланс? Выступая в роли интервьюера, именно я должен обеспечить для соискателя качественный процесс, понять, когда нужно дать подсказки или задать наводящие вопросы, и как корректировать свои ожидания с учётом конкретного контекста.
В собеседованиях по программированию я часто ставил перед соискателями описанную далее задачу, отчасти основанную на реальных процессах компании. И сегодня я вас с ней познакомлю, продемонстрировав, что именно я стремился понять с её помощью о соискателе.
Условие задачи
Предположим, у нас есть сайт, и мы отслеживаем просматриваемые посетителями страницы на предмет бизнес-метрик.
Каждый раз, когда кто-то заходит на сайт, мы делаем запись в журнал, отмечая Timestamp, PageId и CustomerId. К концу дня у нас формируется большой файл со множеством подобных записей, и для каждого нового дня заводится новый такой файл.
Располагая двумя файлами журнала (для дня 1 и дня 2), мы хотим сгенерировать список «лояльных клиентов», отвечающих следующим критериям: (а) они посещали сайт в первый и второй день, (b) они посетили не менее двух уникальных страниц.
Это не сильно сложный вопрос, но он требует некоторых размышлений, а также понимания сложности кода и структур данных. Можно легко определить клиентов, посещавших сайт в оба дня, а также тех, кто посетил не менее двух уникальных страниц. А вот чтобы найти пересечение этих двух показателей, потребуется немного постараться.
Я задавал соискателям эту задачу где-то раз 500, что позволило мне достаточно хорошо её откалибровать. В результате я выяснил, что рекомендация о найме/отказе на её основе совпадает с итоговым решением о найме примерно в 95% случаев. Я также могу масштабировать эту задачу для кандидатов более высокого уровня, что делает её очень гибкой. При этом в ходе решения я также могу в случае затруднений дать человеку ряд намёков или подсказок.
Уточняющие вопросы
Наиболее грамотные кандидаты, прежде чем переходить к написанию кода, должны задавать уточняющие вопросы. Я рассчитываю увидеть в соискателях проявление рассудительности, так как в описанных условиях задачи присутствует двусмысленность.
Имел ли я ввиду посещение двух уникальных страниц в день или всего?
Это значительно влияет на решение. Я имею в виду «всего 2 уникальных страницы», поскольку так задача становится намного интереснее. Около половины соискателей сразу же переходят к решению, не уточняя этого нюанса, и половина из них ошибочно предполагают, что я подразумевал «2 уникальных страницы в день». Если передо мной менее опытный кандидат, то я изначально даю ему подсказки, прежде чем он переходит к коду. Если же кандидат опытный, я некоторое время ожидаю и смотрю, возникнут ли у него вопросы в ходе продумывания алгоритма.
В реальности инженеры постоянно сталкиваются с неоднозначностью, и корень большинства программных проблем можно найти в плохо определённых требованиях. Поэтому я хочу получить сигнал о том, что человек заметил присутствующую двусмысленность и хочет её прояснить.
Есть ещё один важный уточняющий вопрос, который упускают 90% соискателей: «А как быть с повторами?» Имеется в виду посещение одной и той же страницы в один день или в разные дни. В моей задаче под повторами подразумевается именно это.
Третий значимый уточняющий вопрос относится к предполагаемому масштабу. Умещаются ли собранные данные в памяти? Можно ли загрузить в неё содержимое одного из журналов? А обоих?
В основу этой задачи легла реальная система под названием Clickstream, над которой я работал в Amazon. Она отвечала за отслеживание поведения пользователей на amazon.com. Мы обрабатывали петабайты событий от миллионов одновременных пользователей на гигантском кластере Hadoop, включающем десяток тысяч хостов, и за обслуживание этой системы у нас отвечала целая команда инженеров. Однако в рамках 45-минутного собеседования мы берём гораздо меньший масштаб и представляем, что собранные данные в памяти умещаются.
И последний существенный уточняющий вопрос был связан с тем, насколько важно соотношение производительность – память – обслуживаемость. Существует простейшее решение, которое выполняется за O(n²) времени, но использует всего O(1) памяти. Есть более эффективное решение, выполняющееся за O(n) времени, но использующее O(n) памяти. А есть промежуточный вариант, при котором выполняется предварительная обработка за O(n log n), требующая O(k) памяти, что позволяет выполнять основной алгоритм за O(n), задействуя O(1) памяти.
У каждого решения есть свои плюсы и минусы. Некоторые из эвристик, которые вы можете использовать для повышения быстродействия или оптимизации потребления памяти, могут усложнить восприятие и последующее расширение кода. В случае более опытных кандидатов я надеялся, что у нас по этому поводу возникнет интересная беседа.
А нельзя просто использовать базу данных?
В теории можно написать простой SQL-запрос и, конечно, крупные компании имеют огромные хранилища, в которых вы можете запросто подобное реализовать. Но в рамках собеседования нам это не нужно. Поскольку эта задача не относится к распределённым системам, и обрабатываемые данные умещаются в память, зачем вносить излишнюю сложность и зависимости от базы данных для того, что можно решить с помощью всего 20 строк простого кода?
▍ Простейшее решение
Отправная точка:
Около 80% кандидатов сначала пробуют простейшее решение. Оно самое лёгкое и естественное. Это решение представляет некую форму алгоритма «для каждого элемента файла 1 перебрать всё содержимое файла 2 в поиске элементов с тем же id посетителя, параллельно отслеживая просмотренные им страницы».
Проблема такого решения в том, что оно требует O(n²) времени.
Я не возражаю, когда человек начинает с простейшего варианта, но хочу в итоге увидеть в нём осознание того, что выполнение за O(n²), пожалуй, не станет приемлемым ни для какой задачи. Причём хочется, чтобы это осознание пришло как можно раньше и без подсказок. Ни один первоклассный инженер не должен прибегать к алгоритму, выполняющемуся за O(n²), если только не работает в условиях недостаточной памяти или иных неустранимых ограничений.
Когда соискатель излагает это решение, требующее O(n²) времени, я вежливо улыбаюсь и жду. В этот момент я реально надеюсь, что следующими его словами будут «…но этот алгоритм имеет сложность O(n²). Удастся ли мне повысить его эффективность?» Тогда я задаю наводящий вопрос: «А каково время выполнения этого решения?» Чаще всего после такой подсказки соискатель осознаёт, в чём суть и переходит к реализации более эффективного варианта.
▍ Превращение O(n²) в O(n)
В этот момент вам нужно подумать о том, какую структуру данных следует использовать, и как вы будете сохранять данные.
Слабые кандидаты прибегают к связанным спискам или массивам. Вам неизвестен размер данных наперёд, поэтому массивы использовать нельзя. А в связанных списках поиск происходит за О(n), значит, вы снова придёте к тому же алгоритму O(n²), как бы ни старались. Можно использовать дерево, но так как в нём поиск происходит за O(log n), в лучшем случае вы получите O(n log n).
Более грамотные специалисты догадываются, что скорость поиска O(1), необходимую для превращения O(n²) в O(n), может обеспечить словарь (Map). Лучшие же кандидаты предусмотрительно отмечают недостаток такого подхода, заключающийся в использовании O(n) памяти. Здесь повышение скорости достигается за счёт увеличенного потребления памяти.
Если вы используете словарь, то что будет ключом, а что – значением? На этот вопрос я получал всевозможные ответы. Некоторые кандидаты используют в качестве ключа PageId, а в качестве значения – CustomerId, но это не поможет. После этого человек пробует поменять их местами. Но это тоже не решит проблему, поскольку упускается тот факт, что для каждого посетителя у вас может присутствовать множество страниц, а не одна. Другие кандидаты догадываются, что в качестве значения словаря нужно использовать коллекцию страниц, но они прибегают к списку, что меня расстраивает, так как в этом случае не учитывается возможное присутствие повторов. Когда человек учитывает обработку повторов, это позволяет оценить, насколько он понимает отличия между списками и множествами.
Итак, нам подойдёт Map <CustomerId, Set<PageId>>. Но станете ли вы загружать содержимое обоих файлов в один словарь? Или же используете две, по одной для каждого? А, может, вы обойдётесь просто загрузкой содержимого файла 1 в словарь и обработаете файл 2, не сохраняя?
Самые грамотные кандидаты понимают, что могут пойти третьим путём. Это потребует намного меньше памяти и создаст более простой алгоритм. Хорошие кандидаты тоже до этого додумываются, но не без подсказок.
Выполнить условие «клиенты, посетившие сайт в оба дня» довольно просто: вы считываете запись посетителя из дня 2, и если он находится в словаре из дня 1, значит, это наш человек:
А вот условие «клиенты, посетившие не менее двух уникальных страниц», правильно выполнить чуть сложнее, поэтому в случае затруднений я даю подсказку: «У вас есть множество страниц из дня 1 и одна страница из дня 2…как определить, что это не менее двух уникальных страниц?»
Слабые кандидаты используют перебор элементов множества (Set) на предмет присутствия среди них страницы из дня 2. Такой подход снова превращает алгоритм O(n) в O(n²). И меня удивило количество людей, выбравших этот вариант. Более грамотные соискатели выполняют функцию .contains() для множества, обрабатывающую набор хэшей за O(1). Но и в этой логике есть подвох.
Рассуждение для получения правильного решения будет таким: если вы находитесь внутри цикла If, и клиент посетил не менее двух страниц в день 1, а также посетил любую страницу в день 2, то он является лояльным независимо от того, какая это была страница. В противном случае он посетил в день 1 только одну страницу, что ведёт к вопросу: «Отличается ли эта страница от страницы из дня 2?» Если да, то посетитель лоялен. В ином случае это повтор, а значит, остаются сомнения, и нужно продолжать цикл.
Здесь важно внимание к деталям, таким как использование > вместо >= или упущение ! во втором условии. Я видел такое довольно часто. Лучшие кандидаты быстро замечали такие нюансы, когда перепроверяли алгоритм после его завершения. Хорошие кандидаты замечали их после некоторых намёков. Это позволяло мне сделать объективные выводы о навыках отладки.
▍ Оптимизация решения
Лучшие кандидаты зачастую дополнительно проводят некоторую оптимизацию, демонстрируя внимание к мелочам и мастерство. Плюсом при этом выступает обсуждение компромиссов между внесением оптимизации и будущей обслуживаемостью.
Например, если мы работаем в условиях ограниченной памяти, то не нужно сохранять в словаре каждую страницу из дня 1 – будет достаточно двух. Поскольку задача гласит «не менее двух страниц», значит, множество с размером 2 или даже массив такого же размера задействует меньше памяти, чем неограниченное множество.
Либо, если вы уже определили, что посетитель лоялен, то не нужно тратить такты процессора на повторение логики при очередной встрече этого посетителя в файле второго дня.
Про оптимизацию: вы можете поспорить, что в случае изменения требований в будущем эти оптимизации усложнят корректировку алгоритма. Это объективный аргумент. Я рад, когда человек может вести вразумительную дискуссию на тему плюсов и минусов различных решений, предлагая для них сбалансированные альтернативы. В то же время возможность при необходимости оптимизировать алгоритм является чертой грамотного инженера, и вам потребуется порой идти на это в своей работе.
Иное решение
Подавляющее большинство кандидатов в итоге используют подход со словарём, но изредка (не более 5%) встречаются такие, которые прибегают к иному решению.
Что, если предварительно обработать файлы и упорядочить их по CustomerId, а затем по PageId?
Предварительная обработка – это мощный приём в арсенале программиста, особенно если вы собираетесь выполнять операцию многократно. Такую обработку можно произвести при первом выполнении или же заранее, чтобы в перспективе добиться сокращения общего времени выполнения. Упорядочивание файлов может выполняться в константной памяти (constant memory), занимая O(n log n) времени.
Когда файлы упорядочены, задача упрощается, и решить её можно с помощью метода двух указателей, требующего для выполнения O(n) времени и O(1) памяти.
В этом случае вы перемещаете указатели для файла 1 и файла 2 до тех пор, пока они оба не укажут на один CustomerId. Это будет означать, что посетитель заходил на сайт в оба дня. И поскольку вторым ключом сортировки выступает PageId, нужно использовать ещё один метод двух указателей, чтобы определить наличие не менее двух уникальных страниц. В итоге получается метод двух указателей, вложенный в другой метод двух указателей. Забавная задачка! Её реализацию я оставлю в качестве упражнения для заинтересованных читателей.
Итоги
Надеюсь, для вас оказался полезен этот инсайдерский взгляд на выполнение задачи по программированию с разбором слабых, хороших и наиболее грамотных решений.
Удачи вам на будущих собеседованиях!
Автор: Дмитрий Брайт
