Вопросы об Интервью Дизайна Алгоритма/Структуры данных [закрываются]

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

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

Он сказал мне, "Нет, нет, все дают мне то решение. Дайте мне различный".

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

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

Я наслаждаюсь классиком, "каково различие между LinkedList и ArrayList (или между связанным списком и массивом/вектором) и почему Вы выбрали бы один или другой?"

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

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

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

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

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

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

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

1. Запись метод, который берет строку и возвращает true, если та строка является числом. (что-либо с regex как самый эффективный ответ для интервью)
2. запишите абстрактный метод фабрики, который не содержит переключатель и возвращает типы с базовым типом "X". (Поиск шаблонов, ища отражение, еще ища их к не шаг стороны и использование, если, если)
3. разделите строку "каждый; вещь |; | еще |; | в |; | он; ре" маркером "|; |". (много символьные маркеры не позволяются, по крайней мере, в .net, таким образом ища креативность, лучшим решением является общий взлом)

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

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

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

Тот, который я нахожу более полезными все еще, следующие. Я дал это на многих языках, вот версия 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;
    }
  }
}

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

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

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

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

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

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

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

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

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

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