면접에서 NP- 완료 문제를 해결하는 것이 맞습니까? [닫은
https://stackoverflow.com/questions/1724673
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian해결책
나에게 완전히 합법적입니다. 컴퓨터 과학 전문가라면 문제가 왜 어려운지에 대해 비공식적으로 논쟁 할 수있는 좋은 기회가 있습니다.
많은 실제 문제는 결국 NP-Hard로 밝혀졌으며 Stackoverflow는 이제 어려운 문제로 판명되는 문제의 복잡성에 대한 질문을 가지고 있습니다 (예 : NP-HARD). CS 전문가 도구 상자의 중요한 부분은 해결하기 어려운 것으로 알려진 문제를 인식하고 논쟁 할 수있는 중요한 부분입니다.
다른 팁
나는 이와 같은 것을 묻는 데 아무런 문제가 없습니다. 또한 프로그래머는 Rote의 NP- 완료 문제를 인식 할 것으로 예상해서는 안됩니다. 그러나 주어진 문제가 NP- 완성인지 여부에 관계없이 알고리즘이 잠재적으로 느리다는 것을 식별 할 수 있어야합니다.
물론, 왜 안돼? NP- 완성은 해결할 수 없다는 것을 의미하지는 않지만 솔루션이 느려질 수 있습니다. 응시자가 무차별 대구 솔루션을 선택하거나 동적 프로그래밍 솔루션을 시도하는지 확인할 수 있습니다. 그리고 이러한 유형의 질문은 런타임 및 기타 유용한 이론에 대한 질문으로 이어질 수 있습니다.
일부 국가에서는 불법적 인 인터뷰 질문의 범주가 있으며, 일반적으로 고용주의 사업이 아닌 개인 정보와 관련이 있습니다. 면접관이 인터뷰 대상자의 능력에 대한 아이디어를 얻는 데 도움이 될 것이라고 생각한다면 모든 질문은 공정한 게임입니다!
코드 원숭이가 아닌 사상가를 요구하는 입장을 고용하는 경우 신청자에게 이런 종류의 문제를 던지는 것이 유용 할 수 있습니다. 문제가 NP로 "잘 알려진"경우 누가 신경 쓰나요? 그 사람이 좋으면 문제를 분석 할 때 그 이해에 올 것입니다. 그것은 면접관이보고 싶어하는 결과 일 수도 있고, 신청자가 계속해서 더 많은 사전 분석을 수행하고 그가 문제를 무차별 한 방법, 또는 더 관리하기 쉽게하기 위해 적용 할 수있는 최적화를 설명 할 수 있습니다. .
나는 이것에 문제가 없지만, 인터뷰에서 이런 종류의 질문의 유용성에 대해 다소 의문을 제기합니다.
면접관으로서 이와 같은 질문의 이점은 그 사람이 문제에 어떻게 접근하는지와 그들이 어떻게 생각하는지 보는 것입니다. 당신이 그들에게 그것을 말하라고 말하면, 당신은 그들이 어려운 문제에 어떻게 접근 할 것인지에 대해 상당히 알 수 있습니다.
즉, 인터뷰 중에 대부분의 사람들은 최선을 다하지 않습니다. 따라서 이것과 같이 다소 "까다로운"것을 던지는 것은 종종 과잉입니다.
인터뷰 대상자가 답을 알지 못하는 질문을하는 것이 유효하다고 생각합니다.
모든 사람은 답을 모르는 문제를 겪습니다. 이러한 유형의 질문은 인터뷰 대상자의 내부 프로세스가 무엇인지에 대한 통찰력을 제공합니다. 그들이 논리적으로 결론을 내리고 정답을 공식화하기 시작한다면, 그것이 최고의 동적 프로그래밍 알고리즘이 아니더라도, 그들이 잘 추론하고 답을 발견 할 수 있음을 보여줍니다.
또한, 그들은 문제에 대한 모든 것을 알지 못하기 때문에 이런 종류의 질문을 통해 인터뷰 대상자가 도움이나 설명을 요청하는 데 얼마나 편안한 지 알 수 있습니다.
이런 유형의 질문에 대답하는 가장 좋은 방법은 무언가 빠진 것인지 잘 알려지지 않은지 설명하고 답을 가정하여 왜 그것이 올바른지, 왜 최고가 아닌지를 지적하는 것입니다. 해결책.
대답하기 어려운 질문을하고 프로그래머가 문제를 통한 이유를 확인하는 것이 좋습니다.
그러나 그것은 면접관이 어떻게 질문을하는지에 달려 있으며, 수학적 천재가 아닌 경우 프로그래머에게 솔루션을 향해 유명합니다 (즉, 그들이 어떻게 추론하는지, 그리고 그들이 좋은 시작이지만 무엇이 좋은 질문에 반응하는지 알아보기 위해 만약 ... ") 자폐증이 있고 4.3 초 안에 최적의 솔루션을 제공 할 수 있는지 감지하지 않고).
인터뷰는 많은 사람들이 그러한 질문에 대답하기가 매우 어렵다는 매우 스트레스가 많은 일이라는 것을 기억할 가치가 있습니다. 인터뷰 대상자에게 과도한 스트레스/압력을받지 않으면 서 훨씬 간단한 질문으로 충분합니다.
의도적으로 그들이 스트레스를 다루는 방법을 보려고한다면, 프로그래머가 직장에서 다루어야 할 스트레스는 아니기 때문에 가치있는 것을 테스트하지 않습니다.
인터뷰 대상자에게 알리지 않고 눈에 띄는 질문을하는 것은 일종의 의미이지만, 관찰 된 문제 해결에서 문제는 종종 비판적 사고 기술, 문제 해결 방법 및 압력 또는 실패를 처리하는 방법을 보여줄 수 있도록 종종 질문을받습니다. .
나는 해결할 수없는 인터뷰 질문을 받았으며, 나는 인터뷰에 "실패한"적이 없다고 생각합니다.
인터뷰에서 숫자를 촉진하는 방법을 물어 보는 것이 공정합니까?
그것은 NP-C로 알려져 있지 않지만 다항식 시간 솔루션 [*]는 알려져 있지 않으므로 P에있는 것으로 알려져 있지 않습니다.
내 질문과 원래 질문 모두에 대한 답은 "예"이며 같은 이유로 생각합니다. 일부 문제에는 확장 된 솔루션이 없지만 특정 입력을 위해 어쨌든 해결해야합니다. 그러한 문제를 처리 할 수있는 프로그래머가 필요하다면 인터뷰에서 그것을 증명할 수있는 좋은 방법이 있으며, 이는 그들을 던지고 그들이 놀라게하는지 확인하는 것입니다.
누군가 CompSCI 배경을 주장하면 동적 프로그래밍으로 배낭 문제를 해결하는 것과 같은 주문시의 특정 NP-C 문제에 대한 좋은 솔루션을 제공 할 수 있어야합니다. 나는 신청자에게 프로그래밍 작업을 요청하여 이전에 본 적이없는 문제를 해결하고 실제로 NP- 완성 (예 : 지정된 문제로 배낭을 줄임)을 증명하는 것이 무의미하다고 생각합니다. 당신은 그것을 할 수있는 회사당 많은 프로그래머가 필요하지 않으며 (보통 0), 당신이 발견 할 수있는 것은 후보자가 주제를 바꾸고 인터뷰 시간에 더 가치있는 일을하기 전에 후보자가 얼마나 오래 유지하는지입니다. ..
*] 비트의 입력 크기의 다항식. 당신은 종종 사람들이 입력에 의해 표시되는 숫자의 크기와 같은 인수 분해와 같은 정수 문제의 알고리즘 복잡성을 논의하는 것을 종종 볼 수 있습니다. 그러나 그것은 NP와 NP-C가 정의되는 방식이 아닙니다.
아니요, 면접관이 권력의 위치에있는 것을 좋아한다는 것은 무례하고 신호입니다. 하하, 모자! 나는 대답을 알고 있으며 당신은 그렇지 않습니다! 그리고 소년, 나는 당신이 그것을 생각해 내려고 노력하는 것을 좋아합니까!
유용한 인터뷰 질문으로서 약간 유효 할 수있는 유일한 방법은 잘 알려진 질문이거나 어쨌든 NP가 완성되었고 타당성에 대한 토론을 장려하는 방식으로 물었다.
인터뷰 중에 프로그래밍 과제로 NP- 완료 문제를 제시하는 데 아무런 문제가 없습니다. 인터뷰 중에 문제에 대한 다항식 시간 해결책을 찾을 것으로 기대하는 데 문제가 있습니다.
면접관은 후보자가 쉬운 해결책을 찾을 수없는 상황을 포함하여 후보자가 다양한 상황을 어떻게 다루는 지 확인해야합니다. "불가능한"질문은 간단한 해결책이 없을 때 후보자가 어떻게 반응하는지 보여줍니다. 후보자는 그냥 포기합니까? 후보자는 몇 가지 다른 시도를 검색합니까? 솔루션은 얼마나 광범위하게 시도 되었습니까? 후보자는 언제 도움을 요청합니까? 후보자는 문제가 "공정하지 않다"고 불평합니까?
요컨대, 그러한 인터뷰 질문은 p = np를 해결하는 것이 아닙니다. 그것은 심리적 대답입니다.
인터뷰 전에 그러한 질문이 주어진다면 (인터뷰에서 답변하기 위해) 괜찮다고 말할 것입니다. 그러나 그 자리에있는 그와 같은 어려운 문제를 해결하는 것은 프로그래머가 잘 수행되지 않을 것입니다. 프로그래머가 잘 수행한다면, 그 자리에서 행동 할 수 있음을 의미합니다 (시간이 걸리고 가능한 모든 결함을 점검 해야하는 것들을 설계해야하기 때문에 항상 프로그래밍에 가장 적합한 것은 아닙니다) 또는 이전에 비슷한 문제를 보았습니다.
편집 : 또는 문제에 대한 논의는 문제에 대한 논의가 좋을 것입니다. 행동 계획을 완전히 해결했는지 여부를 말하고, 얼마나 실행 가능한지, 빠르지만 어려운 방법이 있는지 논의하는 것과 같은 문제가 좋습니다. 인터뷰 대상자가 인터뷰에서 50 줄 이상의 C 코드를 기록해야한다고 말하지는 않을 것입니다.
그것은 악입니다!
면접관이 면접관에서 NP- 완료 질문을한다면 합리적으로 기대할 수있는 유일한 응답은 인터뷰 대상자가 문제가 NP- 완성이라는 증거로 응답한다는 것입니다. 대학 숙제 질문과 같은 스트레스가 적은 환경에서는 일반적으로 밝은 학생이 2-3 시간 이상이 걸립니다. 증명 자체는 여러 페이지를 완전히 작성하여 완전히 기록 할 수 있습니다. 인터뷰와 같은 스트레스가 많은 환경에서는 인터뷰 대상자가 이것이 NP- 완성임을 인식하지 못할 수도 있습니다.
유일한 합리적인 대안은 인터뷰 대상자가 근사 알고리즘을 생성한다는 것입니다. 그러나이 경우 면접관은 명시 적으로 그들이 있음을 분명히합니다 좋아 근사치.
그럼에도 불구하고 대부분의 근사치는 정답 중 2 개 순서 만 제공됩니다.
인터뷰 대상자는 검색 유형의 알고리즘이 가장 적합 할 수 있다고 제안합니다 (예 : NP- 완료 인 정수 도메인 최적화 문제는 단순한 근사화 알고리즘을 사용하고 단순한 검색 스핀을 사용합니다. 괜찮은 결과를 생성하기위한 알고리즘.)
나는 그들에게 p! = np 또는 p == np임을 증명하도록 요구하는 것을 선호합니다. 언젠가 후보자가 대답 할 것입니다. 나는 그들의 대답을 훔쳐서 유명해질 것입니다!
그러나 더 진지하게 말하면, 나는 그것이 완전히 공정하다고 생각합니다. 대부분의 NP 완전한 문제는 해결하기 쉽고 매우 느리게 실행됩니다. 그 직업이 복잡성 이론에 대해 많은 것을 알아야한다는 한, 그들이 입증해야 할 것은 솔루션이 느려질 것이라는 것을 이해한다는 것입니다. 보너스 포인트가 비 폴리 동맥 시간이라는 것을 알고 있다면, NP가 완료되었다는 것을 알고 있다면 골드 스타.
