Какие простые алгоритмы или проблемы «белой доски», связанные со структурой данных, вы считаете эффективными в процессе отбора кандидатов?
У меня есть несколько простых, которые я использую для проверки навыков решения проблем, и их можно просто выразить, но есть возможность применить некоторые эвристики.
Одна из основных тем, которые я использую для младших разработчиков:
Write a C# method that takes a string which contains a set of words (a sentence) and rotates those words X number of places to the right. When a word in the last position of the sentence is rotated it should show up at the front of the resulting string.
Когда кандидат отвечает на этот вопрос, я смотрю, есть ли у него доступные структуры и методы данных .NET (string.Join, string.Split, List и т. д.) Для решения проблемы. Я также ищу их, чтобы выявить особые случаи для оптимизации. Как и количество раз, которое нужно повернуть слова, на самом деле не X, а X% количества слов.
Какие проблемы на белой доске вы используете для собеседования с кандидатом, и что вы ищете в ответе (не нужно публиковать фактический ответ).
Я ищу возможность эффективно использовать доску и свое время на собеседовании. Согласованные регулярные выражения не подходят для большинства вещей. Для такого надуманного примера вы действительно поместили бы такие ограничения времени выполнения? В общем, .net, где находится мой опыт, вы не проверяете свой код на тактовый цикл. Если бы это было так, вы бы действительно не смогли справиться с этим.
Что такое хак для 3-го? Замена |; | с каким-то другим символом, которого нет в строке?
@AksharPrabhuDesai да, обычно с чем-то вроде пи или тета, так что это не типичный ввод, для этого случая
Мне нравится классическая фраза: «В чем разница между LinkedList и ArrayList (или между связанным списком и массивом / вектором) и почему вы выбрали тот или иной?»
Я надеюсь, что ответ будет включать обсуждение:
Вот подробные инструкции: chaoticjava.com/posts/linkedlist-vs-arraylist
@AksharPrabhuDesai - Я бы не советовал читать эту связанную запись в блоге как хороший способ узнать о LinkedList и ArrayList. Автор делает несколько вводящих в заблуждение заявлений (особенно относительно поведения изменения размера ArrayList) и опускает некоторые ключевые моменты (некоторые из которых, по общему признанию, были заполнены Стивеном Колебурном в комментариях блога).
@DavidCitron, можете ли вы указать на какой-нибудь блог / статью, которая включает обсуждение всех отмеченных пунктов в вашем ответе ниже.
Однажды, когда я проходил собеседование в Microsoft в колледже, парень спросил меня, как определить цикл в связанном списке.
Обсудив на прошлой неделе в классе оптимальное решение проблемы, я начал рассказывать ему.
Он сказал мне: «Нет, нет, все предлагают мне это решение. Дайте мне другое».
Я утверждал, что мое решение было оптимальным. Он сказал: «Я знаю, что это оптимально. Назовите мне неоптимальный вариант».
В то же время это неплохая проблема.
+1 Какой урок! Я предполагаю, что их больше заботило то, как вы придумаете ответ, а не сам ответ, оптимальный или нет.
Я бы сказал, хэшируйте адреса узлов и помещайте их в карту. если вы встретите узел, который уже был отображен. бинго !.
Верно, но для этого требуется O (N) дополнительной памяти.
Другой способ - просто сохранить начало и текущий указатель. Откуда текущий перемещается (от начала до конца), а начало перемещается между началом и текущим. Для каждой итерации тока проверяйте все узлы между начальным и текущим. Если next встречает null, цикла нет, если когда-либо next равно start, то у нас есть цикл
Вот вариант для нестандартного решения - скажем, вы знаете, что можете перебирать список с определенной скоростью (# узлов / сек) и знаете, сколько памяти выделено для этого списка и размер узлов, тогда вы должны получить до конца списка за время, пропорциональное соотношению этих двух, так что отследите это. Усложняется, принимая во внимание вытеснение задач, эффекты кеширования, виртуальную машину и то, что вся выделенная память, вероятно, не для списка, поэтому, возможно, вычислите ее как худший случай, но это может быть творческой альтернативой, демонстрирующей некоторую умственную гибкость.
Если вам известен размер связанного списка n, просто переходите по ссылкам, увеличивая счетчик. Если счетчик идет на n + 1, чем размер списка, есть цикл, вы можете остановиться. В противном случае вы остановитесь на n.
Мне нравится просматривать код, который на самом деле написал человек, и просить его объяснить мне это.
Во время недавнего собеседования меня часто просили реализовать структуру данных, обычно LinkedList или HashMap. И то, и другое достаточно просто, чтобы выполнить за короткое время, и достаточно сложно, чтобы избавиться от невежественных людей.
В ответ на любой подобный вопрос задайте следующий вопрос: «Как вы могли бы улучшить этот код, чтобы разработчик, который его обслуживает, мог понять, как он легко работает?»
Графы сложны, потому что большинство нетривиальных задач с графами, как правило, требуют приличного количества реального кода для реализации, если требуется больше, чем набросок алгоритма. Многие из них, как правило, сводятся к тому, знает ли кандидат кратчайший путь и алгоритмы обхода графа, знаком ли он с типами цикла и обнаружением, а также знает ли он границы сложности. Я думаю, что многие вопросы по этому поводу сводятся скорее к пустякам, чем к творческому мышлению на месте.
Я думаю, что проблемы, связанные с деревьями, как правило, покрывают большинство трудностей, связанных с вопросами о графах, но без особой сложности кода.
Мне нравится задача Project Euler, которая просит найти самый дорогой путь вниз по дереву (16/67); общий предок - хорошая разминка, но многие люди это видели. Если попросить кого-нибудь спроектировать древовидный класс, выполнить обходы, а затем выяснить, по каким обходам они могут перестроить дерево, также можно получить некоторое представление о структуре данных и реализации алгоритма. Задача программирования Стерна-Брокота также интересна и быстро реализуется на доске (http://online-judge.uva.es/p/v100/10077.html).
SSSP = кратчайший путь от одного источника; APSP = Кратчайший путь для всех пар; DFS = поиск в глубину; BFS = поиск в ширину
Тривиальный вариант - попросить их написать код поиска в дереве с нуля. Да, если вы знаете, что делаете, это тривиально. Но многие программисты не знают, как с этим справиться.
Еще один, который я считаю более полезным, заключается в следующем. Я привел это на нескольких языках, вот версия 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;
}
}
}
Затем я задаю им следующие вопросы. Я спрашиваю их медленно, даю людям время подумать и готов их подтолкнуть:
Если они предложат слегка (или очень) неправильное решение, следующий глупый набор данных найдет большинство ошибок, с которыми вы столкнетесь:
@a = qw(
hello
world
hello
goodbye
earthlings
);
@b = qw(
earthlings
say
hello
earthlings
);
Я предполагаю, что около 2/3 кандидатов не ответят на этот вопрос. Я еще не встречал грамотного программиста, у которого были бы проблемы с этим. Я обнаружил, что люди с здравым смыслом и очень небольшим опытом программирования справляются с этим лучше, чем среднестатистические программисты с несколькими годами опыта.
Я бы предложил использовать эти вопросы в качестве фильтров. Не нанимайте кого-то, потому что он может ответить на эти вопросы. Но если они не могут ответить на эти вопросы, не нанимайте их.
Попросить их написать рекурсивный алгоритм для хорошо известного итеративного решения (например, Фибоначчи и т. д. - мы даем им итеративную функцию, если необходимо), а затем просим их вычислить время выполнения для этого.
Часто рекурсивная функция включает древовидную структуру данных. Меня сбивает с толку количество раз, когда человек не мог распознать это. Становится немного сложно подсчитать время выполнения, пока вы не увидите, что это древовидная структура ...
Я считаю, что эта проблема охватывает многие области. А именно, их способность читать код (если им дана итеративная функция), способность писать код (поскольку они пишут рекурсивную функцию), алгоритм, структуру данных (для времени выполнения) ...
Реализуйте функцию, которая, учитывая связанный список, который может быть круговым, меняет местами первые два элемента, третий с четвертым и т. д.
Это не обязательно касается возможностей ООП, но в нашем последнем наборе интервью мы использовали выбранный код с ошибками из списка Ошибка месяца. Наблюдение за кандидатами на поиск ошибок показывает их аналитические способности, показывает умение интерпретировать чужой код.
«Напишите метод, который принимает строку и возвращает истину, если эта строка является числом. (Что-либо с регулярным выражением в качестве наиболее эффективного ответа)». Я уверен, что это идеально подходит для вашей работы, но где я работаю, если вы ответите на этот вопрос с помощью решения с регулярным выражением, которое будет считаться очень плохим. Эффективно с точки зрения времени программиста, но не времени выполнения. Контекст важен даже для таких простых задач.