Вопросы, связанные с построением алгоритма/структуры данных

Question

Каковы некоторые простые алгоритмы или структуры данных, связанные с проблемами «белого посадки», которые вы находите эффективными во время процесса отбора кандидатов?

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

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

Написать метод C#, который принимает строку, которая содержит набор слов (предложение) и вращает эти слова X число мест к правильно. Когда слово в последней позиции предложения повернуто, оно должно появиться в начале результирующей строки.

Когда кандидат отвечает на этот вопрос, я вижу, что они имеют доступные структуры и методы данных .NET (string.Join, string.Split, List и т. Д.) Для решения проблемы. Я также ищу их для выявления особых случаев для оптимизации. Как и количество раз, когда слова нужно поворачивать, на самом деле это не X, а X% количество слов.

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

Answer 1

1. Написать метод, который принимает строку и возвращает истину, если эта строка является числом. (Все, что с регулярным выражением, как наиболее эффективный ответ на интервью)
2. Пожалуйста напишите абстрактный фабричный метод, который Безразлично» t содержит переключатель и возвращает типы с базовым типом «X». (Ищите шаблоны, ища отражение, ища их не на боковом шаге, а используйте if if if)
3. Пожалуйста, разделите строку «every; thing |; | else |; | in |; | he; re» на токен «|; |». (многозначные жетоны не допускаются, по крайней мере, в .net, поэтому поиск креативности, лучшее решение - общий взлом)

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

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

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

Answer 8

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

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

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

Answer 9

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

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

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

Answer 10

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

Answer 11

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