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

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

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

Рассмотрим пример.

Когда поиск не похож на поиск

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

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

Этот тип задач особенно вводит в заблуждение, потому что он практически кричит вам в лицо, когда вы впервые смотрите на него: «Я - математическая задача! Реши меня математически! »

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

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

  1. Нам нужно упорядоченное пространство поиска, которое можно аккуратно разделить на подразделы.
  2. Мы должны иметь возможность ставить высокие и низкие границы области поиска.
  3. Учитывая единственный элемент в нашем пространстве поиска, мы должны иметь возможность определить, находится ли то, что мы ищем, выше или ниже этой точки.

Для нашего первого критерия нам нужно упорядоченное пространство поиска, которое мы можем легко разделить. Ну как насчет этого?

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

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

Предположим, например, что мы хотим найти квадратный корень из 36. Наши начальные условия поиска будут иметь нижнюю границу на уровне 0, верхнюю границу на уровне 36 и среднюю точку на уровне (36 + 0) / 2 = 18.

Теперь нам просто нужно проверить нашу среднюю точку, чтобы увидеть, как она сравнивается с n. И как мы это делаем? Выровняйте это. 18² = 324, что намного больше 36, поэтому мы знаем, что нам нужно смотреть в нижнюю половину области поиска. Мы можем сделать это, установив нашу верхнюю границу на 17, что даст новый диапазон поиска с 8 посередине.

Мы можем проверить 8, возведя его в квадрат. 8² = 64, что по-прежнему больше 36, поэтому нам нужно еще раз взглянуть на нижнюю половину нашего диапазона. Мы делаем это, устанавливая нашу верхнюю границу на 7, что дает новую среднюю точку 3.

3² = 9, что меньше 36, поэтому теперь мы знаем, что мы зашли слишком низко, и нам нужно посмотреть на верхнюю половину области поиска. Мы можем сделать это, установив нашу нижнюю границу на 4. Это дает нам новую среднюю точку (4 + 7) / 2 = 5 (помните, целочисленное деление округляется в меньшую сторону).

5² = 25, что по-прежнему меньше 36, поэтому мы снова перемещаем нашу нижнюю границу до 6. Это дает нам среднюю точку (6 + 7) / 2 = 6.

6² = 36, поэтому мы нашли ответ. Мы сократили начальное пространство поиска [0, 36] до [6, 7], что в итоге показало, что квадратный корень из 36 равен 6.

Конечно, в правильной реализации нам понадобится немного больше деталей, чтобы правильно округлить решения без четного целочисленного ответа, но это оптимальное решение по сути. Используя двоичный поиск, мы можем решить эту проблему (и весь этот жанр псевдоматематических задач) за O (log n) времени. Нам просто нужно было распознать проблему, в чем она заключалась на самом деле - проблема поиска.

Соответствие шаблону

Здесь было бы справедливо с вашей стороны возразить: «Все в порядке, но как мне выяснить истинную природу проблемы?»

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

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

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

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

Рассмотрим другой пример.

Все является графиком

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

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

Например, рассмотрим строки «абаб» и «баба». Расстояние между этими двумя строками равно 2. Если поменять местами первые два символа a, они будут преобразованы в «baab», а затем, поменяв местами последние два символа, превратятся в «baba». Таким образом, вы можете преобразовать одну строку в другую как минимум двумя перестановками.

Как решить эту проблему? Уловка концептуализации этой проблемы состоит в том, чтобы признать, что любую серию преобразований можно смоделировать в виде графа. Мы начнем с одной строки, скажем a, и назовем ее узлом на нашем графике. Затем у вас есть выбор из двух любых позиций в строке, которые нужно поменять местами. Вы можете поменять местами 0 на 1, что мы запишем как (0, 1). Вы также можете поменять местами (0, 2) или (0, 3). Или (1, 2), или (1, 3), или (2, 3). Мы будем называть каждую из этих шести возможностей ребром, которое ведет к новому узлу в графе, преобразованной строке. Итак, первый слой нашего графика будет выглядеть так.

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

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

При такой визуализации проблемы остается лишь найти кратчайший путь между исходным узлом «abab» и конечным узлом «baba». Мы превратили полученное непрозрачное описание проблемы в простой поиск кратчайшего пути через невзвешенный граф, который мы можем решить с помощью поиска в ширину. На этом графике на самом деле есть 4 разных пути длиной 2, минимальное расстояние от «абаба» до «баба». Выделим только один.

Два слоя

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

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

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

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

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

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