Это корректно, чтобы попросить решать полную NP проблему на собеседовании? [закрытый]

Я не вижу проблем в том, чтобы задать что-то подобное. Также НЕ следует ожидать, что программисты будут распознавать NP-полные задачи наизусть. Однако они должны быть в состоянии определить, что их алгоритм потенциально медленный, независимо от того, является ли данная проблема NP-полной.

Конечно, а почему бы и нет? NP-Complete не означает неразрешимость, это просто означает, что ваше решение будет медленным. Возможно, вы захотите увидеть, выберет ли кандидат решение методом перебора или попробует решение динамического программирования. И этот тип вопросов может привести к вопросам о времени выполнения и другой полезной теории.

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

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

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

Польза от таких вопросов как интервьюер, это увидеть, как человек подходит к проблеме и как он думает. Если вы скажете им, чтобы они это обсудили, вы сможете немного узнать о том, как они подойдут к трудной проблеме.

При этом, во время интервью, большинство людей не в лучшей форме - поэтому бросайте что-то, что несколько "хитрость", как это, часто бывает излишней, ИМО.

Я считаю правильным задать вопрос, на который вы знаете, что собеседник не знает ответа.

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

Кроме того, поскольку они, вероятно, не знают всего. Что касается проблемы, этот тип вопросов позволяет увидеть, насколько комфортно респонденту просить о помощи или разъяснениях.

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

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

Но все зависит от того, как интервьюер задает вопрос и подсказывает программист к поиску решения, если он не является математическим гением (то есть, чтобы увидеть, как они рассуждают и как они реагируют на такие вопросы, как «это хорошее начало, но что, если ...»), а не определять, являются ли они аутистами и может предоставить оптимальное решение за 4,3 секунды).

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

Если вы делаете это, чтобы сознательно попытаться увидеть, как они справляются со стрессом, это просто глупо - это не так »Это стресс, с которым программист сталкивается в своей работе, поэтому вы не тестируете ничего стоящего.

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

Мне задавали вопросы на собеседовании, которые я не мог решить, и я не думаю, что когда-либо "проваливал" собеседование из-за этого.

Нет, это грубо и признак того, что интервьюеру просто нравится находиться у власти. Ха-ха, батя! Я знаю ответ, а ты нет! И мальчик, как мне нравится заставлять тебя извиваться, пытаясь это придумать!

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

Справедливо ли спросить в интервью, как разложить числа на множители?

Это не известно как NP-C, но не известно решение с полиномиальным временем [*], поэтому оно конечно, не известно, что он находится в P.

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

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

[*] многочлен от размера ввода в битах, т.е. Вы часто видите людей, обсуждающих алгоритмическую сложность целочисленных задач, таких как факторизация, с точки зрения размера числа, представленного входными данными, например, «sqrt (N) пробные деления». Но это не то, как определяются NP и NP-C.

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

Интервьюер должен захотеть увидеть, как кандидат справляется с различными ситуациями, включая ситуации, которые кандидат не может найти. простое решение. «Невозможные» вопросы показывают, как кандидат реагирует, когда нет простого решения. Кандидат просто сдается? Сколько разных попыток ищет кандидат? Насколько далеко продвинуты испробованные решения? Когда кандидат просит о помощи и как? Кандидат жалуется, что проблема «несправедлива»?

Короче говоря, такой вопрос интервью не касается решения P = NP ... it?

Это зло!

Если интервьюер задает NP-полный вопрос у интервьюера, единственный ответ, который они могут разумно ожидать, - это то, что интервьюируемый ответит доказательством того, что проблема NP- полный. В среде с низким уровнем стресса, например, при выполнении домашнего задания в университете, способному студенту обычно требуется 2-3 или более часов, чтобы доказать это. Само доказательство может занять несколько страниц, чтобы полностью выписать его, возможно, несколько часов работы. В стрессовой обстановке, такой как собеседование, вы можете ожидать, что собеседник может даже не осознавать, что это неполноценно.

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

Даже так,

Я предпочитаю спрашивать их чтобы доказать, что P! = NP или P == NP. Когда-нибудь кандидат ответит на него, я украду его ответ и стану знаменитым!

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

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

Изменить: Или, возможно, было бы хорошо обсудить проблему, например, сформулировать план действий, независимо от того, решите ли вы ее полностью ... и обсудить, насколько осуществимо и есть ли быстрый (но трудный) способ сделать это и тому подобное. Я бы не сказал, что интервьюируемый должен записать более 50 строк кода C в интервью, чтобы решить эту проблему