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

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

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

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

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% количества слов.

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

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
53
0
140 902
11

Ответы 11

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

«Напишите метод, который принимает строку и возвращает истину, если эта строка является числом. (Что-либо с регулярным выражением в качестве наиболее эффективного ответа)». Я уверен, что это идеально подходит для вашей работы, но где я работаю, если вы ответите на этот вопрос с помощью решения с регулярным выражением, которое будет считаться очень плохим. Эффективно с точки зрения времени программиста, но не времени выполнения. Контекст важен даже для таких простых задач.

jheriko 07.03.2010 18:33

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

DevelopingChris 10.03.2010 00:50

Что такое хак для 3-го? Замена |; | с каким-то другим символом, которого нет в строке?

Eastern Monk 26.11.2011 00:27

@AksharPrabhuDesai да, обычно с чем-то вроде пи или тета, так что это не типичный ввод, для этого случая

DevelopingChris 09.12.2011 19:40

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

Я надеюсь, что ответ будет включать обсуждение:

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

Вот подробные инструкции: chaoticjava.com/posts/linkedlist-vs-arraylist

Eastern Monk 25.11.2011 22:02

@AksharPrabhuDesai - Я бы не советовал читать эту связанную запись в блоге как хороший способ узнать о LinkedList и ArrayList. Автор делает несколько вводящих в заблуждение заявлений (особенно относительно поведения изменения размера ArrayList) и опускает некоторые ключевые моменты (некоторые из которых, по общему признанию, были заполнены Стивеном Колебурном в комментариях блога).

David Citron 23.01.2012 01:12

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

Geek 19.07.2012 17:13

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

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

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

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

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

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

Terry Li 07.10.2011 22:33

Я бы сказал, хэшируйте адреса узлов и помещайте их в карту. если вы встретите узел, который уже был отображен. бинго !.

Kshitij Banerjee 02.02.2012 01:17

Верно, но для этого требуется O (N) дополнительной памяти.

Jim Puls 02.02.2012 05:49

Другой способ - просто сохранить начало и текущий указатель. Откуда текущий перемещается (от начала до конца), а начало перемещается между началом и текущим. Для каждой итерации тока проверяйте все узлы между начальным и текущим. Если next встречает null, цикла нет, если когда-либо next равно start, то у нас есть цикл

fkl 28.05.2012 10:05

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

DavidN 05.04.2013 19:14

Если вам известен размер связанного списка n, просто переходите по ссылкам, увеличивая счетчик. Если счетчик идет на n + 1, чем размер списка, есть цикл, вы можете остановиться. В противном случае вы остановитесь на n.

aledalgrande 10.10.2013 01:38

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

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

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

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

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

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

SSSP = кратчайший путь от одного источника; APSP = Кратчайший путь для всех пар; DFS = поиск в глубину; BFS = поиск в ширину

Binil Thomas 16.09.2008 07:49

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

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

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

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

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

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

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

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

Другие вопросы по теме