Сегодня там было question, где автору была предоставлена полная проблема NP во время интервью, и ему, очевидно, не сказали, что это был одним.
Какова цель задавать такие вопросы? Какое поведение ожидает интервьюер при запросе таких вещей? Доказательство? Полезная эвристика? И даже законно спросить кого-нибудь, если это не известная проблема NP-полной, о которой все должны знать? (там много их)
Полностью законный для меня. Если вы профессионал в области компьютерных наук, есть хорошие шансы, что вы можете либо аргументировать неофициально, почему проблема кажется сложной, либо (даже лучше) обеспечивает эскиз сокращения от известной проблемы NP-hard.
Многие проблемы реального мира в конечном итоге оказываются NP-жесткими, а stackoverflow также задает вопросы о сложности проблемы, которая оказывается сложной (например, NP-hard). Это важная часть инструментария для профессионалов CS, чтобы иметь возможность распознавать и обсуждать проблемы, которые, как известно, трудно решить.
Я не вижу никаких проблем с запросом чего-то подобного. Кроме того, программистам НЕ следует ожидать распознавания NP-полных проблем с помощью rote. Тем не менее, они должны иметь возможность идентифицировать, что их алгоритм потенциально медленный, независимо от того, является ли данная проблема NP-полной.
Конечно, почему бы и нет? NP-complete не означает неразрешимость, это просто означает, что ваше решение будет медленным. Вы можете посмотреть, будет ли кандидат выбирать решение грубой силы или попробовать динамическое программирование. И этот вопрос может привести к вопросам о времени выполнения и другой полезной теории.
В некоторых странах существует категория вопросов интервью, которые в некоторых странах являются незаконными, что обычно связано с личными данными, которые не являются бизнесом работодателя. В любом случае, любой вопрос - честная игра, если собеседник чувствует, что это поможет получить представление о возможностях интервьюируемого!
Если вы нанимаете должность, которая требует мыслителя, а не просто обезьяну кода, может быть полезно бросить эту проблему на заявителя. Кто заботится, если проблема "хорошо известна" как NP? Если парень хорош, он поймет это понимание при анализе проблемы. Это может быть результатом того, что интервьюер хочет увидеть, или заявитель может продолжить еще какой-то предварительный анализ и описать, как он переустанавливает проблему, или какие оптимизации он может придумать, чтобы сделать его более управляемым.
Я не вижу проблемы с этим, но я несколько сомневаюсь в полезности такого рода вопросов в интервью вообще.
Преимущество таких вопросов, как это, как интервьюер, заключается в том, как человек подходит к проблеме и как они думают. Если вы попросите их поговорить об этом, вы можете узнать немного о том, как они подходят к сложной проблеме.
Говоря об этом, во время интервью большинство людей не в своих силах - поэтому бросать что-то, что несколько "сложно", как это, часто бывает излишним, ИМО.
Я думаю, что правильно задать вопрос, который, как вы знаете, собеседник не знает ответа.
Каждый сталкивается с проблемами, с которыми они не знают ответа. Этот тип вопроса даст вам представление о том, что такое внутренний процесс собеседника. Если они логически завершают работу и начинают формулировать правильный ответ, даже если это не лучший алгоритм динамического программирования для него, это показывает, что они могут хорошо рассуждать и обнаруживать ответ.
Кроме того, поскольку они, вероятно, не знают все о проблеме, этот вопрос позволяет понять, насколько комфортно собеседник с просьбой о помощи или разъяснениях.
Я думаю, что лучший способ ответить на этот вопрос - попросить какие-либо разъяснения, если что-то отсутствует или не известно, а затем постулировать ответ, указывая, почему вы считаете, что это правильно, и почему это, вероятно, t лучшее решение.
Хорошо спросить вопрос, который трудно ответить, чтобы понять, как программист объясняет проблему.
Но все зависит от того, как интервьюер задает вопрос и подсказывает программисту решение, если они не являются математическим гением (т.е. видеть, как они рассуждают, и как они реагируют на такие вопросы, как "хороший старт", но что, если... "), а не для обнаружения аутизма и может обеспечить оптимальное решение за 4,3 секунды).
Стоит вспомнить, что интервью - это очень напряженные дела, в которых многие люди находят такие вопросы очень трудными, чтобы ответить на них - гораздо более простой вопрос, как правило, достаточен, если собеседник не подвергнется чрезмерному стрессу/давлению.
Если вы это намеренно пытаетесь понять, как они справляются со стрессом, это просто глупо - это не тот стресс, с которым программист должен справиться в своей работе, поэтому вы не тестируете ничего стоящего.
Это похоже на то, чтобы задавать почти невозможные вопросы, не сообщая об этом собеседнику, но в наблюдаемом решении проблемы часто задают вопрос, чтобы вы могли продемонстрировать навыки критического мышления, как вы подходите к решению проблем и как вы справляетесь давления или отказа.
Мне задавали вопросы интервью, которые я не мог решить, и я не думаю, что из-за этого я когда-либо "проваливал" интервью.
Справедливо ли спрашивать в интервью, как делить числа?
Не известно, что это NP-C, но никакого решения полиномиального времени [*] не известно, поэтому, как известно, оно не известно в P.
Я думаю, что ответ на мой вопрос и оригинальный вопрос - это "да" и по тем же причинам. В некоторых проблемах нет решения, которое хорошо масштабируется, но все равно нужно решать все определенные задачи. Если вам нужны программисты, которые могут справляться с такими проблемами, есть хороший способ дать им возможность подтвердить это в интервью, и чтобы передать их одному и посмотреть, не волнуются ли они.
Если кто-то утверждает фон CompSci, то они даже должны быть в состоянии обеспечить хорошие решения некоторых проблем NP-C по требованию, например, решить проблему ранца с динамическим программированием. Я бы счел бессмысленным просить заявителя о задании на программирование, чтобы решить проблему, которую они никогда раньше не видели, и на самом деле доказать, что она NP-полная (например, уменьшая рюкзак до указанной проблемы). Вам не нужно очень много программистов для каждой компании, которые могут это сделать (обычно 0), и все, что вы, скорее всего, обнаружите, это то, как долго кандидат держится на ней, прежде чем пытаться изменить тему и сделать что-то более ценное с временем интервью...
[*] полином по размеру ввода в битах, то есть. Вы часто видите, что люди обсуждают алгоритмическую сложность целочисленных задач, таких как факторизация, в терминах размера числа, представленного входом, например. "sqrt (N)". Но это не так, как определены NP и NP-C.
Нет, это грубо и признак того, что интервьюеру просто нравится быть в положении власти. Ха-ха, пеон! Я знаю ответ, а ты нет! И мальчик, я люблю, чтобы ты извивался, пытаясь придумать это!
О том, как это может быть даже немного полезно, поскольку полезный вопрос для интервью - это, если это был известный вопрос или тот, который был как-то явно NP-полным, и спросили таким образом, чтобы это способствовало обсуждению осуществимости.
Нет ничего плохого в том, чтобы дать NP-полную проблему как проблему программирования во время интервью. Я вижу только что-то не так, ожидая найти многомиллионное решение проблемы во время интервью.
Интервьюер должен посмотреть, как кандидат имеет дело с различными ситуациями - в том числе и с ситуациями, которые кандидат не может найти для простого решения. "Невозможные" вопросы показывают, как реагирует кандидат, когда нет простого решения. Кандидат просто сдался? Сколько попыток поиска кандидатов? Насколько далеко продвинулись решения? Когда кандидат просит о помощи - и как? Кандидат жалуется, что проблема "несправедлива"?
Короче говоря, такой вопрос интервью касается не решения P = NP... это психологический ответ.
Если бы такой вопрос был задан перед интервью (для ответа на интервью), я бы сказал, что это нормально... но просто решить такую сложную проблему, как на месте, определенно не будет хорошо программист, и если программист делает это хорошо, просто означает, что они могут действовать на месте (что не всегда лучше всего подходит для программирования, поскольку проектирование вещей требует времени и проверки всех возможных недостатков) или что они видели аналогичную проблема раньше.
Изменить: Или, возможно, обсуждение проблемы было бы хорошим, как, например, сформулировать план действий, независимо от того, решите ли вы его полностью или нет, и обсудите, насколько это возможно, и если есть быстрый (но сложный) способ сделать это и так далее. Я бы не сказал, что собеседнику приходится записывать более 50 строк кода C в интервью, чтобы решить его, хотя
Это зло!
Если интервьюер задает вопрос с NP-полным вопросом у интервьюера, единственным ответом, который они могут разумно ожидать, является то, что собеседник отвечает доказательством того, что проблема NP-полная. В условиях низкого стресса, таких как вопрос о домашнем задании в университете, обычно это требует яркого ученика 2-3 или более часов, чтобы доказать это. Само доказательство может занять несколько страниц, чтобы полностью выписать, возможно, несколько часов работы. В условиях высокого напряжения, таких как интервью, вы можете ожидать, что собеседник может даже не признать, что это np-complete.
Единственная разумная альтернатива заключается в том, что собеседник создает алгоритм аппроксимации; однако в этом случае интервьюер должен четко указать , что они отлично с приближениями.
Тем не менее, большинство приближений приходит только с порядком 2 правильного ответа.
Я предполагаю, что существует еще одна альтернатива: собеседник предполагает, что алгоритм поискового типа может быть наиболее подходящим (например, задача оптимизации целых доменов, которая является NP-полной, большинство алгоритмов аппроксимации используют ветвь и связанный поиск на симплексном алгоритме для получения достойных результатов.)
Я предпочитаю попросить их доказать, что P!= NP или P == NP. Когда-нибудь кандидат ответит на него, я украду их ответ и буду знаменит!
Однако, более серьезное замечание, я думаю, это совершенно справедливо. Большинство NP-задач легко решить, они работают очень медленно. Если работа не требует, чтобы они много знали о теории сложности, все, что им нужно продемонстрировать, заключается в том, что они понимают, что решение будет медленным. Бонусные очки, если они знают это не полиномиальное время, золотая звезда, если они знают, что NP завершен.