Правильно ли просить решить NP-полную задачу на собеседовании?[закрыто]
https://stackoverflow.com/questions/1724673
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Сегодня был вопрос на SO, где автору во время интервью была поставлена NP-полная задача, и ему, очевидно, не сказали, что это таковая.
Какова цель задавать такие вопросы?Какого поведения ожидает интервьюер, задавая такие вопросы?Доказательство?Полезная эвристика?И можно ли вообще спрашивать, не является ли это широко известной NP-полной проблемой, о которой должен знать каждый?(есть их много)
Решение
Полностью законно для меня. Если вы профессионал в области компьютерных наук, есть хорошие шансы, что вы можете не неофициально спорить, почему проблема кажется сложной, либо (даже лучше) предоставить набросок сокращения от известной проблемы NP-Hard.
Многие проблемы в реальном мире в конечном итоге оказываются NP-Hard, и Stackoverflow также время от времени задает вопросы о сложности проблемы, которая оказывается сложной (например, NP-Hard). Это важная часть инструментарии для профессионалов CS, чтобы иметь возможность распознавать и спорить о проблемах, которые, как известно, трудно решить.
Другие советы
Я не вижу проблем с вопросом чего -то подобного. Кроме того, не следует ожидать, что программисты будут распознавать проблемы с NP-полными по Rote. Они должны, однако, иметь возможность определить, что их алгоритм потенциально медленный, независимо от того, является ли данная проблема, завершенная NP.
Конечно, почему бы и нет? NP-Complete не означает неразрешимо, это просто означает, что ваше решение будет медленным. Возможно, вы посмотрите, выберет ли кандидат решение для грубой силы или попробовать решение для динамического программирования. И этот тип вопроса может привести к вопросам о времени выполнения и другой полезной теории.
Существует категория вопросов на собеседовании, которые являются незаконными в некоторых странах и обычно касаются личных данных, которые не имеют отношения к работодателю.Кроме того, любой вопрос — это честная игра, если интервьюер считает, что он поможет получить представление о способностях интервьюируемого!
Если вы нанимаете на должность, которая требует мыслителя, а не просто программиста, может быть полезно бросить такого рода проблему на соискателя.Кого волнует, если проблема «хорошо известна» как NP?Если парень хороший, он придет к этому пониманию, анализируя проблему.Это вполне может быть тот результат, который хочет видеть интервьюер, или заявитель может продолжить предварительный анализ и описать, как он решит проблему методом грубой силы, или какие оптимизации он может применить, чтобы сделать ее более управляемой. .
Я не вижу проблем с этим, но я несколько сомневаюсь в полезности подобных вопросов в интервью в целом.
Преимущество задания подобных вопросов, как интервьюера, заключается в том, как человек подходит к проблеме и как он думает. Если вы скажете им обсудить это, вы можете немного узнать о том, как они подходят к сложной проблеме.
При этом, во время интервью большинство людей не в своих лучших проявлениях - так что бросить что -то, что несколько «хитрый», как это часто, - ИМО.
Я думаю, что справедливо задать вопрос, который, как вы знаете, собеседник не узнает ответ.
Все сталкиваются с проблемами, на которые они не знают ответа. Этот тип вопроса даст вам представление о том, каким является внутренний процесс собеседника. Если они логически завершают вещи и начинают сформулировать правильный ответ, даже если это не лучший алгоритм динамического программирования для него, это показывает, что они могут хорошо рассуждать и открыть для себя ответ.
Кроме того, поскольку они, вероятно, не знают все о проблеме, этот вид вопросов позволяет вам увидеть, насколько комфортно собеседник с просьбой о помощи или разъяснении.
Я думаю, что лучший способ ответить на этот тип вопроса - задать какие -либо разъяснения, если чего -то не хватает или не хорошо известно, а затем постулировать ответ, указывая на то, почему вы думаете, что это правильно, и почему это, вероятно, не самое лучшее решение.
Хорошо задать вопрос, на который трудно ответить, чтобы увидеть, как программист рассматривает проблему.
Но все зависит от того, как интервьюер задает вопрос, и побуждает программиста к решению, если он не математический гений (т.е., чтобы увидеть, как они рассуждают, и как они реагируют на такие вопросы, как «Это хорошее начало, но что Если ... ») вместо того, чтобы обнаружить, являются ли они аутичными и могут обеспечить оптимальное решение за 4,3 секунды).
Стоит помнить, что интервью - это очень стрессовые дела, в которых многие люди считают очень трудно ответить на такие вопросы - обычно достаточно более простого вопроса, не подвергая собеседника под чрезмерным стрессом/давлением.
Если вы сделаете это, чтобы сознательно попытаться посмотреть, как они справляются со стрессом, просто глупо - это не тот стресс, с которым программист должен иметь дело в своей работе, так что вы не тестируете ничего стоящего.
Это вроде значит задавать непосредственные вопросы, не сообщая об этом на собеседника, но в решении наблюдаемых проблем часто задают вопрос, чтобы вы могли продемонстрировать навыки критического мышления, как вы приближаетесь Анкет
Мне задавали вопросы интервью, которые я не мог решить, и я не думаю, что когда -либо «провалил» интервью из -за этого.
Справедливо ли спрашивать в интервью, как учитывать числа?
Это не известно, как NP-C, но никакое полиномиальное решение [*] не известно, поэтому, конечно, не известно, что он находится в P.
Я думаю, что ответ как на мой вопрос, так и на первоначальный вопрос - «да» и по тем же причинам. Некоторые проблемы не имеют решения, которое хорошо масштабируется, но все равно нужно решить для определенных входов. Если вам нужны программисты, которые могут решить такие проблемы, есть хороший способ доказать им это в интервью, и это выдвинуть их и посмотреть, пугаются ли они.
Если кто-то претендует на фон COMPSCI, то он даже должен быть в состоянии предоставить хорошие решения определенных задач NP-C по требованию, таких как решение проблемы рюкзака с динамическим программированием. Я бы счел бессмысленным, прося кандидата на работу по программированию, чтобы решить проблему, которую они никогда не видели раньше, и фактически доказывают это NP-полное (например, путем уменьшения рюкзака до указанной проблемы). Вам не нужно очень много программистов на одну компанию, которая может сделать это (обычно 0), и все, что вы, вероятно, обнаружите, это то, как долго кандидат остается в этом, прежде чем пытаться изменить предмет и сделать что -то более ценное со временем интервью. ..
*] Полином в размере ввода в битах, то есть. Вы часто видите, как люди обсуждают алгоритмическую сложность целочисленных задач, таких как факторизация с точки зрения размера числа, представленного входным, например, «Испытания SQRT (N)». Но это не то, как определены NP и NP-C.
Нет, это грубо и признак того, что интервьюеру просто нравится быть в положении власти. Ха -ха, Пон! Я знаю ответ, а ты нет! И мальчик, люблю ли я, чтобы ты заставлял тебя извиваться, пытаясь придумать это!
Единственный способ, которым это могло быть даже немного обоснован, в качестве полезного вопроса интервью, это был ли это хорошо известный вопрос или тот, который был каким-то образом, очевидно, NP-полным, и задавал таким образом, чтобы поощрять обсуждение осуществимости.
Нет ничего плохого в том, чтобы дать проблему, завершенную NP в качестве задачи по программированию во время интервью. Я вижу только что-то не так с ожиданием найти проблему за полиномиальное время во время интервью.
Интервьюер должен захотеть посмотреть, как кандидат имеет дело с различными ситуациями, включая ситуации, которые кандидат не может найти простого решения. «Невозможные» вопросы показывают, как реагирует кандидат, когда нет простого решения. Кандидат просто сдается? Сколько разных попыток ищет кандидат? Насколько далеко пробовали решения? Когда кандидат просит помощи - и как? Кандидат жалуется на то, что проблема «не справедливо»?
Короче говоря, такой вопрос интервью не о решении p = np ... это психологический ответ.
Если бы такой вопрос был задан перед собеседованием (чтобы ответить на собеседовании), я бы сказал, что это нормально..но просто решить такую сложную задачу на месте ни один программист определенно не сможет сделать хорошо, и если программист сделает это хорошо, это просто означает, что он может действовать на месте (что не всегда является лучшим вещь для программирования, поскольку проектирование вещей требует времени и проверки всех возможных недостатков) или что они уже сталкивались с подобной проблемой раньше.
Редактировать:Или, возможно, было бы полезно обсудить проблему, например, составить план действий независимо от того, решите ли вы ее полностью или нет.и обсуждение того, насколько это осуществимо и существует ли быстрый (но сложный) способ сделать это и тому подобное.Я бы не сказал, что интервьюируемому придется записать более 50 строк кода на C, чтобы решить эту задачу.
Это зло!
Если интервьюер задает вопрос о том, что в интервьюеру задает вопрос, единственный ответ, который они могут разумно ожидать, это то, что собеседник отвечает доказательством того, что проблема является NP-полным. В такой среде с низким уровнем стресса, как вопрос о домашнем задании университета, это обычно требует яркого студента 2-3 или более часов, чтобы доказать. Само доказательство может занять несколько страниц, чтобы полностью написать, возможно, несколько часов работы. В такой среде высокого стресса, как интервью, вы можете ожидать, что собеседник может даже не признать, что это NP-полное.
Единственная разумная альтернатива заключается в том, что собеседник производит алгоритм приближения; Однако в этом случае интервьюер должен сделать это явно ясно, что они отлично с приближениями.
Несмотря на это, большинство приближений поставляются только с порядком 2 правильного ответа.
Я предполагаю, что есть еще одна альтернатива: интервьюируемый предполагает, что алгоритм поискового типа может быть наиболее подходящий (например, задача оптимизации целочисленного домена, которая является NP-полным, большинство алгоритмов приближения Используйте ветвь и связанный поиск на Simplex Алгоритм для получения достойных результатов.)
Я предпочитаю попросить их доказать, что p! = Np или p == np. Когда -нибудь кандидат ответит на это, я украду их ответ и буду знаменитым!
Тем не менее, на более серьезной ноте, я думаю, это совершенно справедливо. Большинство полных проблем NP легко решить, они просто работают очень медленно. Если работа не требует, чтобы они много знали о теории сложности, все, что им нужно, это продемонстрировать, это то, что они понимают, что решение будет медленным. Бонусные баллы, если они знают, что это не полиномиальное время, золотая звезда, если они знают, что это завершено NP.
