Вопросы по выбору алгоритма/структуры данных

Ответ 1

Мне нравится классика "какая разница между LinkedList и ArrayList (или между связанным списком и массивом/вектором) и почему вы выбираете тот или иной?"

Ответ, на который я надеюсь, относится к обсуждению:

• производительность вставки
• производительность итераций
• распределение памяти/воздействие перераспределения
• Влияние удаления элементов с начала/середины/конца
• как знание (или не знание) максимального размера списка может повлиять на решение

Ответ 2

Однажды, когда я брал интервью у Microsoft в колледже, парень спросил меня, как определить цикл в связанном списке.

Обсудив в классе предыдущую неделю оптимальное решение проблемы, я начал рассказывать ему.

Он сказал мне: "Нет, нет, все дают мне это решение. Дайте мне другое".

Я утверждал, что мое решение было оптимальным. Он сказал: "Я знаю, что это оптимально. Дайте мне субоптимальный".

В то же время это довольно хорошая проблема.

Ответ 3

При опросе в последнее время меня часто просили внедрить структуру данных, обычно LinkedList или HashMap. Оба они достаточно легки для выполнения в течение короткого времени и достаточно трудны, чтобы устранить бессознательные.

Ответ 4

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

Ответ 5

• Напишите метод, который принимает строку, и возвращает true, если эта строка является числом. (что-либо с регулярным выражением как наиболее эффективным ответом для интервью)
• Пожалуйста, напишите абстрактный метод factory, который не содержит переключатель и возвращает типы с базовым типом "X". (Ищите шаблоны, ища отражение, ища их не на боковом шаге, а используйте if else if)
• Разделите строку "every; thing |; | else |; | in |; | he; re" на токен "|; |". (многозначные жетоны не разрешены, по крайней мере, в .net, поэтому поиск для творчества лучшее решение - это полный хак).

Ответ 6

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

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

Мне нравится проблема Эйлера проекта, которая просит найти самый дорогой путь по дереву (16/67); общий предок - это хороший разогрев, но многие люди его видели. Попросив кого-нибудь создать древовидный класс, выполните обходы, а затем выясните, из каких обходов они могли перестроить дерево, также дает некоторое представление о структуре данных и реализации алгоритма. Задача программирования Stern-Brocot также интересна и быстро развивается на доске (http://online-judge.uva.es/p/v100/10077.html).

Ответ 7

Мне нравится проходить код, который написал на самом деле, и попросить его объяснить его мне.

Ответ 8

Следуйте следующим вопросам: "Как вы можете улучшить этот код, чтобы разработчик, который его поддерживает, может понять, как он работает легко?"

Ответ 9

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

Ответ 10

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

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

# @a and @b are two arrays which are already populated.
my @int;
OUTER: for my $x (@a) {
  for my $y (@b) {
    if ($x eq $y) {
      push @int, $x;
      next OUTER;
    }
  }
}

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

• Что такое @int, когда этот код выполнен?
• Этот код запущен в производство, и есть проблема с производительностью, которая отслеживается с помощью этого кода. Объясните потенциальную проблему производительности. (Если они борются, я спрошу, сколько сравнений требуется, если у @a и @b у каждого есть 100 000 элементов. Я не ищу какую-то определенную терминологию, просто оценку конверта.)
• Без кода предлагайте сделать это быстрее. (Если они предлагают направление, которое легко кодировать, я попрошу их закодировать его. Если они думают о решении, которое приведет к тому, что @int будет каким-либо образом изменен (например, обычный порядок), я буду нажать, чтобы увидеть осознают ли они, что они не должны кодировать исправление, прежде чем проверять, имеет ли это значение.)

Если они придумают небольшое (или очень) неправильное решение, следующий глупый набор данных найдет большинство ошибок, с которыми вы сталкиваетесь:

@a = qw(
  hello
  world
  hello
  goodbye
  earthlings
);
@b = qw(
  earthlings
  say
  hello
  earthlings
);

Я бы предположил, что около 2/3 кандидатов не могут ответить на этот вопрос. Мне еще предстоит встретиться с компетентным программистом, у которого были проблемы с этим. Я обнаружил, что люди с хорошим здравым смыслом и очень небольшим программирующим фоном делают это лучше, чем средние программисты с несколькими годами опыта.

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

Ответ 11

Попросив их написать рекурсивный алгоритм для хорошо известного итеративного решения (т.е. Фибоначчи и т.д. - мы при необходимости даем им итеративную функцию), а затем вычислим время выполнения для него.

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

Я считаю, что эта проблема охватывает многие области. А именно, их способность считывания кода (если им задана итеративная функция), способность писать код (поскольку они пишут рекурсивную функцию), алгоритм, структуру данных (для времени выполнения)...