Сегодня на форуме был question, где во время интервью автору была предоставлена полная проблема, и ему явно не сказали, что это одно.Правильно ли задавать разрешение NP-полной проблемы на собеседовании?
Какова цель задать такие вопросы? Какое поведение ожидает интервьюер при запросе таких вещей? Доказательство? Полезная эвристика? И даже законно спросить, если это не известная проблема NP-полной, о которой все должны знать? (есть plenty of them)
Полностью законный для меня. Если вы специалист по компьютерной науке, есть хорошие шансы, что вы можете либо аргументировать неофициально, почему проблема кажется сложной, либо (даже лучше) обеспечивает эскиз сокращения от известной проблемы NP-hard.
Многие проблемы в реальном мире в конечном итоге оказываются NP-жесткими, а stackoverflow также задает вопросы о сложности проблемы, которая оказывается сложной (например, NP-hard).Это важная часть инструментария для профессионалов CS, чтобы иметь возможность распознавать и спорить о проблемах, которые, как известно, трудно решить.
«Предоставьте эскиз редукции к известной проблеме NP-жесткости» - обратите внимание, что вам нужно уменьшить * от * проблемы с NP-трудностью, а не с * на * NP-жесткой проблемой (что обычно слишком просто). – ShreevatsaR
Предоставление эскиза сокращения известной проблемы с NP-проблемой часто бывает затруднительным. Сколько времени вы хотите потратить на один вопрос и сколько веса вы хотите задать, есть ли у кого-нибудь пакет NP-полных вопросов в готовой памяти и может придумать эскиз доказательства во время интервью? –
@David ShreevatsaR Вы правы, я отредактирую и исправлю. –
У меня нет проблем с запросом чего-то подобного. Кроме того, программистам НЕ следует ожидать распознавания NP-полных проблем с помощью rote. Тем не менее, они должны иметь возможность идентифицировать, что их алгоритм потенциально медленный, независимо от того, является ли данная проблема NP-полной.
Действительно? Матричный пример, на который он указывал, очевидно, эквивалентен вычислению тура коммивояжера, поэтому он должен быть NP-полным: P –
@Ben S, между вами * чувствую * проблема NPc и вы * доказываете * это одна минута до бесконечности минут может пройти. –
@Ben S: Если это, очевидно, эквивалентно TSP, то я больше вялый с обеда, чем я думал. Я даже не вижу очевидного отображения из решения матричной задачи в решение TSP. Если вы были в юности в этом замечании, ну, это не очень хорошо переводилось в Интернет. –
Нет, это грубо и признак того, что интервьюеру просто нравится быть в положении власти. Ха-ха, пеон! Я знаю ответ, а ты нет! И мальчик, я люблю, чтобы ты извивался, пытаясь придумать это!
Об одном единственном способе, который может быть даже немного действительным в качестве полезного вопроса для интервью, является вопрос о том, был ли это известный вопрос или тот, который был как-то явно NP-полным, и спросил таким образом, чтобы это способствовало обсуждению осуществимости.
Или я полагаю, что это может быть жизнеспособным, если чрезвычайно важная квалификация для этой работы - «насколько хорошо заявитель мириться с необоснованными просьбами, находясь под давлением». –
Я так не думаю. Этот вопрос позволяет понять, как собеседник реагирует на проблемы, с которыми он не привык решать. Это также позволяет узнать, удобны ли они, запрашивая дополнительную информацию, если они в ней нуждаются. –
Вы можете сделать обе эти вещи, не прося решить NP-полную проблему. Однако попросить их сделать это здорово, если вы хотите увидеть, как они реагируют на проблемы, к которым они не привыкли, чтобы убедиться, что они удобны, запрашивая дополнительную информацию * и быть осламом *. –
Если бы такой вопрос был задан перед интервью (для ответа на интервью), я бы сказал, что все в порядке .. но просто решить такую сложную проблему, как это на месте, определенно не будет сделано хорошо любой программист, и если программист делает это хорошо, просто означает, что они могут действовать на месте (что не всегда лучше всего подходит для программирования, поскольку проектирование вещей требует времени и проверки всех возможных недостатков) или что они видели аналогичная проблема раньше.
Редактировать: Или, возможно, обсуждение проблемы было бы хорошим, как, например, сформулировать план действий, независимо от того, решите ли вы его полностью или нет, и обсудите, насколько это возможно, и если есть быстрый (но сложный) способ делать это и тому подобное. Я бы не сказал, что собеседнику приходится записывать более 50 строк кода C в интервью для его решения, хотя
Конечно, почему бы и нет? NP-complete не означает неразрешимость, это просто означает, что ваше решение будет медленным. Вы можете посмотреть, будет ли кандидат выбирать решение грубой силы или попробовать динамическое программирование. И этот тип вопроса может привести к вопросам о времени выполнения и другой полезной теории.
Я не вижу проблемы с этим, но я несколько сомневаюсь в полезности такого рода вопросов в интервью в целом.
Преимущество таких вопросов, как интервьюер, заключается в том, как человек подходит к проблеме и как они думают. Если вы попросите их поговорить об этом, вы можете узнать немного о том, как они подходят к сложной проблеме.
Это, как говорится, во время интервью, большинство людей не в своих силах - поэтому бросать что-то, что несколько «сложно», как это, часто бывает излишним, ИМО.
Я думаю, что действительно стоит задать вопрос, который, как вы знаете, собеседник не будет знать ответ.
Каждый сталкивается с проблемами, с которыми они не знают ответа. Этот тип вопроса даст вам представление о том, что такое внутренний процесс собеседника. Если они логически завершают работу и начинают формулировать правильный ответ, даже если это не лучший алгоритм динамического программирования для него, это показывает, что они могут хорошо рассуждать и обнаруживать ответ.
Кроме того, поскольку они, вероятно, не знают все о проблеме, этот вопрос позволяет понять, насколько комфортно собеседник с просьбой о помощи или разъяснениях.
Я думаю, что лучший способ ответить на этот вопрос - попросить какие-либо разъяснения, если что-то отсутствует или не известно, а затем постулировать ответ, указывая, почему вы думаете, что это правильно, и почему это, вероятно, не является Лучшее решение.
Не совсем то же самое, но коллега, который пытался за нее. в информатике был спрошен в своем первом курсе интро для вычисления 4-го номера Ackermann (
@ Карл: Я думаю, это иллюстрирует разницу между запросом невозможного («вычислить четвертое число Аккермана») и просто задавать проблему без решения, которое хорошо масштабируется («дать алгоритм вычисления чисел Аккермана»). Решение NP-полной проблемы может быть очень простым (например, путем исчерпывающего поиска). Это когда размер ввода изменяется или не указывается, что вы попадаете в панические станции. –
Все говорят о решении динамического программирования для этой матричной проблемы, но никто не дает решения. Для меня это не похоже на проблему с DP. – PeterAllenWebb
В некоторых странах существует категория вопросов интервью, которые являются незаконными, что обычно относится к личным данным, которые не являются бизнесом работодателя. В стороне, любой вопрос - честная игра, если собеседник чувствует, что это поможет понять идею возможностей интервьюируемого!
Если вы нанимаете должность, которая требует мыслителя, а не просто обезьяну кода, может оказаться полезным бросить эту проблему на заявителя. Кто заботится, если проблема «хорошо известна» как NP? Если парень хорош, он поймет это понимание при анализе проблемы. Это может быть результатом того, что интервьюер хочет увидеть, или заявитель может продолжить еще какой-то предварительный анализ и описать, как он переустанавливает проблему, или какие оптимизации он может придумать, чтобы сделать его более управляемым ,
Проблема с проблемами NPC: их NP-полнота требует много времени, чтобы быть доказанной. Как долго должно быть интервью? –
@Pavel: Я полностью согласен с тем, что я работал над доказательством нескольких NP-полных проблем, и большинство из них берут меня на пару часов в лучшем случае, чтобы уменьшить, некоторые из нас думают о долгих размышлениях. Я думаю, что большинство людей, которые отвечают «да, его штраф, чтобы задать любой вопрос», вероятно, раньше не приходилось делать сложные сокращения. – ldog
Но тогда это было бы проблемой только в том случае, если доказательство было необходимо, работодатель может просто ожидать, что «это кажется NP», а затем обсудите с вами. –
Это своего рода вопрос, чтобы задавать почти невозможные вопросы, не сообщая об этом его собеседнику, но при обнаружении проблемы часто задают вопрос, чтобы вы могли продемонстрировать навыки критического мышления, как вы подходите к решению проблем, и как вы давление или отказ.
Меня задавали вопросы интервью, которые я не мог решить, и я не думаю, что из-за этого я когда-либо «проваливал» интервью.
Хороший комментарий, но я бы отметил, что NP-complete делает * не * равным почти невозможным. Абсолютно возможно выработать решения NP-полных проблем; просто они не будут * масштабироваться *. Если интервьюер специально задает алгоритм, который будет обрабатывать большие экземпляры проблемы, хотя, ну, да, это * означает * ... – itowlson
Да, я должен был сформулировать это лучше. В рамках типичного интервью разработчика программного обеспечения они почти невозможны. Временные ограничения и давление для выполнения не позволят большинству людей решить это. Даже в интервью я обычно получал вибрацию, что вопросы были больше о раскрытии характера и стимулировании обсуждения в области компьютерных наук, чем получении ответа. Или, может быть, я просто компенсировал неудачу с харизмой :) –
Это зло!
Если собеседник задает вопрос с NP-полным вопросом у интервьюера, единственным ответом, который они могут разумно ожидать, является то, что собеседник отвечает доказательством того, что проблема NP-полная. В условиях низкого стресса, таких как вопрос о домашнем задании в университете, обычно это требует яркого ученика 2-3 или более часов, чтобы доказать это. Само доказательство может занять несколько страниц, чтобы полностью выписать, возможно, несколько часов работы. В условиях высокого напряжения, таких как интервью, вы можете ожидать, что собеседник может даже не признать, что это np-complete.
Единственная разумная альтернатива заключается в том, что собеседник создает алгоритм аппроксимации; однако в этом случае интервьюер должен сделать явно ясно, что они штраф с приближениями.
Несмотря на это, большинство приближений приходят только с порядком 2 правильного ответа.
Я предполагаю, что существует еще одна альтернатива: собеседник предполагает, что алгоритм поискового типа может быть наиболее подходящим (например, задача оптимизации целочисленной области, которая является NP-полной, большинство алгоритмов аппроксимации используют ветку и связанный поиск спина на симплексном алгоритме для получения достойных результатов.)
Или собеседник мог бы просто, вы знаете, решить проблему медленным алгоритмом. Многие NP-полные проблемы имеют довольно простые решения, у них просто ужасное время исполнения. – tloach
Я думаю, что в случае, когда собеседник был бы готов принять тривиальный алгоритм, он должен это указать. «Ужасное время исполнения» - это преуменьшение в лучшем случае, для большинства тривиальных алгоритмов потребуется примерно примерно то же время, сколько требуется для создания и уничтожения юниверса, прежде чем они завершатся даже для достаточно небольших размеров ввода. – ldog
«Много NP-полных проблем имеют довольно простые решения». Все проблемы NP имеют очень простое решение (при условии, что задан алгоритм полиномиальной проверки): грубая сила. Вопрос не в том: «ОК, чтобы интервьюер дал вам проблему NP-C, а затем пожаловался, что решение идет медленно», вопрос был: «ОК, чтобы интервьюер дал вам проблему NP-C ». –
Справедливо ли спрашивать в интервью, как умножать цифры?
Это не известно, NP-C, но не полиномиальное время решения [*] не известно, так что, конечно, не известно, что в Р.
Я думаю, что ответ на оба моих вопроса, и исходный вопрос, «да», и по тем же причинам. В некоторых проблемах нет решения, которое хорошо масштабируется, но все равно нужно решать все определенные задачи. Если вам нужны программисты, которые могут справиться с такими проблемами, есть хороший способ дать им возможность доказать это в интервью, и это нужно, чтобы передать их одному и посмотреть, не волнуются ли они.
Если кто-то утверждает фон CompSci, он должен даже обеспечить хорошие решения определенных проблем NP-C по требованию, например, решить проблему с ранцем с динамическим программированием. Я бы счел бессмысленным просить заявителя о задании на программирование, чтобы решить проблему, которую они никогда раньше не видели, и на самом деле доказать, что она NP-полная (например, уменьшая рюкзак до указанной проблемы). Вам не нужно очень много программистов для каждой компании, которые могут это сделать (обычно 0), и все, что вы, скорее всего, обнаружите, это то, как долго кандидат держится на ней, прежде чем пытаться изменить тему и сделать что-то более ценное с временем интервью. ..
[*] полином размера входного бита, то есть. Вы часто видите, что люди обсуждают алгоритмическую сложность целочисленных задач, таких как факторизация, в терминах размера числа, представленного входом, например. «sqrt (N)». Но это не так, как определены NP и NP-C.
Имея фон CompSci, я не помню, как решить проблему ранца с динамическим программированием. Я знаю, где бы я мог быстро разобраться, и это нормально для всех практических целей, кроме ответов на вопросы интервью. –
Да, возможно, я бы сказал * недавний * CompSci фон. Я решил рюкзак в Uni, c.10 лет назад, по математике. Я почти уверен, что могу описать алгоритм из памяти, с несколькими ошибками, но я уверен, что не смог бы заглушить код. Для почти любого конкретного алгоритма можно сказать: «Я не помню деталей, но это в Кнуте». Но интервьюер захочет увидеть доказательства того, что я знаю * хотя бы один алгоритм. Итак: динамическое программирование что-то, что я должен был бы воспроизвести по запросу, например, я могу воспроизвести бинарный поиск по требованию? Зависит от работы и моего резюме. –
Точно так же я сосать на доске код, потому что я никогда не пишу его в реальной жизни. Обычно я программирую с открытой ссылкой для всех, кроме самых обычных задач. Я все еще признаю необходимость писать код в интервью, у меня просто не было смелости взять с собой мои книги ;-). Если это означает, что я в конечном итоге говорю: «Гм, в этот момент я бы посмотрел аргументы в mmap», тогда, хорошо, я должен упасть на милость интервьюера. Точно так же я ожидаю, что кто-то изучил проблему с рюкзаком, чтобы описать, как ее решить, если не все детали. –
Приятно задавать вопрос, на который трудно ответить, чтобы узнать, как программист объясняет проблему.
Но все зависит от того, как интервьюер задает вопрос и подсказывает программисту решение, если они не являются математическим гением (т. Е. Видеть, как они рассуждают, и как они реагируют на такие вопросы, как «это хорошо» start, но что, если ... "), а не обнаруживать, являются ли они аутистами и могут обеспечить оптимальное решение за 4,3 секунды).
Следует помнить, что интервью - это очень напряженные дела, в которых многие люди находят такие вопросы очень трудными, чтобы ответить на них - гораздо более простой вопрос, как правило, достаточен, если собеседник не подвергнется чрезмерному стрессу/давлению.
Если вы это намеренно пытаетесь понять, как они справляются со стрессом, это просто глупо - это не тот стресс, с которым программист должен иметь дело в своей работе, поэтому вы не испытываете ничего стоящего.
Я предпочитаю попросить их доказать, что P! = NP или P == NP. Когда-нибудь кандидат ответит на это, я украду их ответ и буду знаменит!
На более серьезной ноте я считаю, что это совершенно справедливо. Большинство NP-задач легко решить, они работают очень медленно. Если работа не требует, чтобы они много знали о теории сложности, все, что им нужно продемонстрировать, заключается в том, что они понимают, что решение будет медленным. Бонусные очки, если они знают, что это не полиномиальное время, золотая звезда, если они знают, что NP завершен.
Для обеспечения простого решения проблемы NP-c понадобится человеку, обладающему сложностью теории, за несколько минут, поскольку он будет последним, о котором он думает. Лично под напряжением интервью я бы даже сказал, что «я не могу его решить», потому что подход грубой силы слишком тупой, чтобы быть «решением». –
Не забудьте цену, которую вы получите! http://www.claymath.org/millennium/ – Gumbo
Сначала я прочитал, что вы предпочитаете попросить их доказать, что P == NP :) – psihodelia
Нет ничего плохого в том, чтобы дать NP-полную проблему как вызов программирования во время интервью. Я вижу только что-то не так, ожидая найти многомиллионное решение проблемы во время интервью.
Интервьюер должен посмотреть, как кандидат имеет дело с различными ситуациями - в том числе ситуациями, которые кандидат не может найти для простого решения. «Невозможные» вопросы показывают, как реагирует кандидат, когда нет простого решения. Кандидат просто сдался? Сколько попыток поиска кандидатов? Насколько далеко продвинулись решения? Когда кандидат просит о помощи - и как? Кандидат жалуется, что проблема «несправедлива»?
Короче говоря, такой вопрос не о решении P = NP ... это психологический ответ.
Вы можете обсуждать, являются ли они законными вопросами или нет, но потенциальный работодатель может решить спросить их в любом случае. Самое главное, как вы реагируете на них. –
@ Роберт Харви, ну, вот что я имел в виду под термином «что ожидали интервьюеры?». –
Он имеет в виду этот вопрос ОС: http://stackoverflow.com/questions/1720737/from-an-interview-removing-rows-and-columns-in-an-nn-matrix-to-maximize-the-sum – Frank