Как и в большинстве компаний-разработчиков программного обеспечения, почти каждое техническое интервью в Microsoft связано с проблемами программирования. У меня было много разных проблем, которые я использовал за время своего пребывания там. Все они, как правило, обладали характеристиками, позволяющими хорошо обсудить общую проблемную область, проектные решения и компромиссы, но требовалось написать лишь небольшой объем кода, и этот код не был слишком сложным.

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

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

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

Насколько велики целые числа? Я мог бы использовать совсем другой алгоритм для 8-битных целых чисел по сравнению с 64-битными целыми числами. Насколько велик массив? Подход, использующий вспомогательную структуру данных, может оказаться довольно дорогим, если массив большой. Знаю ли я что-нибудь о распределении целых чисел? То есть, даже если значения хранятся в виде 64-битного целого числа, сгруппированы ли фактические значения в небольшом диапазоне? Знаю ли я что-нибудь об ожидаемом количестве уникальных значений? Даже если исходный массив большой, небольшое количество уникальных значений может повлиять на выбор и эффективность определенных алгоритмов. Могу ли я использовать дополнительное хранилище? Функцию можно использовать в контексте, где использование дополнительного хранилища (хранилища, пропорционального вводу) проблематично. Нужно ли мне сохранять исходный порядок уникальных значений или я могу использовать подход, который меняет их порядок?

Как будет использоваться функция? Будет ли он частью библиотеки функций, и поэтому я не могу делать много предположений о том, как он будет использоваться? Является ли это одним из сотен небольших алгоритмов в приложении, поэтому ясность и простота являются наиболее важными? Или это основной алгоритм, который определяет общую производительность моего приложения (возможно, это часть конвейера данных в реальном времени)?

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

По мере того, как мы приступаем к фактическому изучению алгоритмов, вы начинаете понимать, какой реальный опыт программирования имеет кандидат. Некоторые предлагают пройти и «удалить» элементы из массива, не осознавая, что они только что описали потенциально O (N²) алгоритм. Другие говорят о размещении «контрольного» значения в массиве для удаленных элементов (не имея четкого представления, почему это может быть полезным промежуточным шагом и может ли эта концепция существовать на их языке выбора).

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

function RemoveDups(a: array of integer): integer
{
  integer unique_index = 0;
  integer current_index = 0;
  for (; current_index < a.length; current_index++)
    if (is_unique(a[current_index]))
    {
      remember(a[current_index]);
      a[unique_index++] = a[current_index];
    }

  return unique_index;
}

То есть выполнить итерацию по массиву и скопировать уникальные элементы в начало массива, возвращая количество найденных уникальных элементов.

Уловка тогда сводится к тому, как определить, является ли элемент уникальным. Рост богатых библиотек базовых классов практически на всех языках, изучаемых в школах, означает, что многие кандидаты перейдут к использованию класса set для записи и проверки уникальных целых чисел. Меня это устраивало, но затем я попытался выяснить, понимают ли они, как это может быть связано, в частности, с использованием памяти. Именно здесь большинство кандидатов просто убеждены, потому что они написали линейный алгоритм, что нет возможности его улучшить, к сожалению, демонстрируя слабую интуицию о влиянии накладных расходов с постоянным коэффициентом и интенсивного использования памяти.

Я бы также спросил их о подходах, которые не используют дополнительное хранилище. Некоторым кандидатам также пришла в голову идея сначала отсортировать массив, уменьшив проблему до «удаления дубликатов из отсортированного массива», что проще - как указано выше, с несколькими осторожными конечными условиями. В качестве альтернативы они могут просто использовать набор уникальных элементов, которые они собрали в начале массива, для проверки уникальности (наихудший случай O (N²)).

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

Код C ++ выложен на github. Я протестировал несколько различных реализаций. Первый базовый случай заключался в том, чтобы просто пройти и коснуться каждого элемента в массиве, чтобы понять, что на самом деле было O (N). Следующая версия сначала отсортировала массив (используя стандартную реализацию qsort), а затем пошла через сжатие повторяющихся элементов. Следующей версией был алгоритм номинально O (N²), который проверяет уникальность путем обхода набора уникальных записей, которые были найдены до сих пор и перемещены в начало массива. На самом деле это не O (N²), а O (N * U). Следующей версией была написанная мною реализация trie, которая обеспечивает эффективную реализацию множества, если значения кластеризованы. В окончательной версии просто использовалась std::unordered_set реализация, поставляемая с Visual Studio C ++.

Я нашел результаты интересными и местами удивительными. На самом деле, то, как тестировать код, вероятно, потребовало более детального обдумывания, чем фактическая реализация (что на самом деле не так уж необычно). Мои тесты смотрят на диапазон размеров входного массива от 2⁴ до 2²², а затем на распределение количества уникальных значений в том же диапазоне. Затем уникальные значения могут быть либо сгруппированы вместе, либо случайным образом распределены по всему диапазону целых чисел.

  • Результаты сортировки выглядят линейно в зависимости от размера ввода.
  • Скорость сортировки может изменяться в 4 раза в зависимости от количества дубликатов. Намного быстрее отсортировать массив с большим количеством дубликатов (предположительно, потому что последние фазы процесса сортировки можно исключить).
  • Но сортировка в 25–90 раз медленнее, чем базовый линейный обход. То есть скорость подхода к сортировке была линейной по отношению к размеру входных данных, но была намного медленнее, чем простой линейный обход данных.
  • Моя наивная реализация trie превосходит реализацию std::unordered_set до тех пор, пока количество уникальных элементов в наборе не достигнет 2¹⁶ или больше. Это меня немного удивило. С кластеризованными значениями (даже с большим количеством уникальных значений) trie намного лучше, чем реализация set как по размеру памяти, так и по скорости (очевидно, связанные проблемы).
  • Trie имеет намного лучшее поведение памяти, чем std::unordered_set для кластеризованных значений и только примерно в 2 раза хуже для некластеризованных значений (например, trie достигает максимума в 356 МБ, а заданного максимума - 146 МБ для вспомогательной структуры данных).
  • Алгоритм O (N²) превосходит все другие алгоритмы, если имеется 16 или менее уникальных значений (для входного массива любого размера), и превосходит подход сортировки вплоть до 256 уникальных элементов. С этими уникальными элементами в кэше L1 просто линейный обход по-прежнему очень быстр. Затем он становится намного медленнее, чем любой другой алгоритм, поскольку количество уникальных элементов растет (как и ожидалось).

Очень трудно понять общее влияние на производительность больших вспомогательных структур данных, выделенных реализациями set и trie, когда имеется большое количество уникальных значений. Результаты становятся медленнее (от 5 до 10 раз), так как количество уникальных элементов становится очень большим (для trie, только когда они распределяются случайным образом, а не кластеризованы), но общее время надежно остается быстрее, чем подход сортировки, который требует никаких дополнительных ассигнований. Общеизвестно, что в любой действительно сложной программе, состоящей из множества компонентов, сложно понять совокупное влияние использования дополнительной памяти одним компонентом в системе. Это одна из причин, почему узкое внимание к конкретному сценарию производительности часто приводит к тому, что разработчик решает, что некоторый дополнительный уровень кэширования является решением, даже если в совокупности это приводит к чрезмерному использованию памяти, которое в целом более вредно, чем полезно. Это особенно типично для разработчиков стандартных библиотек или промежуточного программного обеспечения, которые имеют лишь ограниченную видимость полного сквозного поведения приложения.

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

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

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