هل صحيح أن نسأل حل مشكلة NP كاملة في مقابلة عمل؟ [مغلق

Question

اليوم كان هناك سؤال على ذلك، حيث تم إعطاء صاحب البلاغ مشكلة كاملة من NP أثناء مقابلة، ومن الواضح أنه لم يخبر أنه كان واحدا.

ما هو الغرض من طرح مثل هذه الأسئلة؟ ما هو السلوك الذي يتوقعه القائم بإجراء المقابلة عند طرح مثل هذه الأشياء؟ دليل؟ الاستدلال المفيدة؟ وهل هو أكثر شرعية أن نسأل واحدة إذا لم تكن مشكلة كاملة من NP - يجب أن يعرف الجميع؟ (هناك الكثير منهم)

Answer 1

شرعية تماما بالنسبة لي. إذا كنت مهنيا علوم الكمبيوتر، فهناك فرص جيدة يمكنك إما الوسيطة بشكل غير رسمي لماذا يبدو أن المشكلة صعبة، أو (حتى أفضل) تقديم رسم تخفيض من مشكلة NP الصعبة المعروفة.

تتحول العديد من مشاكل العالم الحقيقي في نهاية المطاف إلى NP-Hard، كما أن Stackoverflow لديها الآن ثم أسئلة حول تعقيد مشكلة تحولت إلى أن تكون صعبة (NP-Hard، على سبيل المثال). إنه جزء مهم من Toolbox من محترفين CS لتكون قادرا على التعرف على المشكلات التي من المعروف أنها من الصعب حلها.

Answer 2

لا أرى أي مشكلة في طرح شيء مثل هذا. أيضا، يجب ألا يتوقع من المبرمجين أن يتعرفون على مشاكل NP-Complete by Rote. ومع ذلك، ينبغي أن يكونوا قادرين على تحديد أن خوارزمهم يحتمل أن تكون بطيئة بغض النظر عما إذا كانت مشكلة معينة كاملة.

Answer 3

طبعا، لم لا؟ NP-Complete لا يعني غير قابل للحل، فهذا يعني أن الحل الخاص بك سيكون بطيئا. قد تبحث لمعرفة ما إذا كان المرشح سيختار حل القوة الغاشمة، أو جرب حل برمجة ديناميكية. وهذا النوع من السؤال يمكن أن يؤدي إلى أسئلة حول وقت التشغيل ونظرية مفيدة أخرى.

Answer 4

هناك فئة من أسئلة المقابلة غير القانونية في بعض البلدان، والتي تتعلق عادة بالتفاصيل الشخصية التي لا تعد من عمل صاحب العمل. جانبا، أي سؤال هو لعبة عادلة إذا شعر القائم بإجراء المقابلة أنه سوف يساعد في الحصول على فكرة عن قدرات الشخص الذي تمت مقابلته!

إذا كنت توظيفا للموقف الذي يدعو إلى المفكر بدلا من مجرد قرد من التعليمات البرمجية، فقد يكون من المفيد رمي هذا النوع من المشكلة في مقدم الطلب. من يهتم إذا كانت هناك مشكلة "معروفة" لتكون NP؟ إذا كان الرجل جيدا، فسوف يأتي إلى هذا الفهم في تحليل المشكلة. قد تكون هذه النتيجة التي يريدها المقابلة يرغب في رؤيتها، أو يمكن لمقدم الطلب أن يستمر في القيام ببعض التحليلات المسبقة ووصف كيفية دفع المشكلة الغاشمة، أو ما التحسنيات التي يمكن أن يفكر فيها بالتقدم لجعلها أكثر قابلية للإدارة وبعد

Answer 5

لا أرى مشكلة في ذلك، لكنني أفعل سؤالا إلى حد ما فائدة هذه الأنواع من الأسئلة في مقابلات بشكل عام.

إن فائدة طرح الأسئلة مثل هذا، كقائم مقابلة، ترى كيف يقترب الشخص من مشكلة، وكيف يفكرون. إذا أخبرتهم أن يتحدثون بها، فيمكنك معرفة بعض الشيء حول كيفية اقترابها من مشكلة صعبة.

ويقال ذلك، خلال مقابلة، معظم الناس ليسوا في أفضل حالاتهم - لذلك رمي شيء ما "صعبة" إلى حد ما مثل هذا غالبا ما يكون مبالغا فيه، IMO.

Answer 6

أعتقد أنه من الصريح طرح سؤال تعرفه، لن يعرف الشخص الذي أجريته الإجابة عليه.

يواجه الجميع المشاكل التي لا يعرفون الإجابة عليها. هذا النوع من الأسئلة سوف يمنحك نظرة ثاقبة حول ما هي العملية الداخلية التي تمت مقابل المقابلة. إذا اختتموا أشياء وتبدأ في صياغة إجابة صحيحة، حتى لو لم تكن أفضل خوارزمية برمجة ديناميكية لذلك، فإنها تظهر أنها يمكن أن يستجيبوا جيدا واكتشفوا إجابة.

أيضا، نظرا لأنهم على الأرجح لا يعرفون كل شيء عن المشكلة، فإن هذا النوع من السؤال يتيح لك رؤية مدى مريح قابل المقابلة مع طلب المساعدة أو التوضيح.

أعتقد أن أفضل طريقة للإجابة على هذا النوع من الأسئلة هي طلب أي توضيحات إذا كان هناك شيء ما في عداد المفقودين أو غير معروف جيدا، ثم افترض إجابة، مشيرا إلى السبب في أن تعتقد أنه صحيح، ولماذا ليس من المحتمل أن يكون الأفضل المحلول.

Answer 7

من الجيد طرح سؤال يصعب الإجابة عليه، لمعرفة كيف أسباب مبرمجة من خلال مشكلة.

ولكن كل هذا يتوقف على كيفية طلب القائم بإجراء المقابل عن السؤال، ويطالب المبرمج باتجاه حل إذا لم تكن عبقرية رياضية (أي أن نرى كيف سبب السبب، وكيف يتفاعلون مع أسئلة مثل "بداية جيدة، ولكن ماذا إذا ... ") بدلا من اكتشاف ما إذا كانت تتمتع بالتوحد ويمكن أن توفر حلا الأمثل في 4.3 ثانية).

تجدر الإشارة إلى أن المقابلات هي شؤون مرهقة للغاية، حيث يجد الكثير من الناس مثل هذه الأسئلة من الصعب للغاية الإجابة على ما يرام - وسيقوم سؤال أبسط بكثير عادة دون أن يكفي دون مقابلته تحت ضغط / ضغط لا مبرر له.

إذا قمت بذلك من أجل محاولة عمدا لمعرفة كيفية التعامل مع الإجهاد هو مجرد غبي - هذا ليس نوع التوتر يجب على مبرمج التعامل معه في وظائفهم، لذلك لا تختبر أي شيء يستحق العناء.

Answer 8

إنه نوع من يعني أن نسأل أسئلة مستحيلة قريبة دون إبلاغ الشخص الذي تمت مقابلته، ولكن في حل المشكلات الملحوظة، غالبا ما يتم طرح السؤال بحيث يمكنك إثبات مهارات التفكير النقدي، وكيف تقترب من حل المشكلات، وكيف تتعامل مع الضغط أو الفشل وبعد

لقد طلبت من أسئلة المقابلة لم أستطع حلها، ولا أعتقد أنني "فشلت" لمقابلة بسبب ذلك.

Answer 9

هل من العدل أن تسأل في مقابلة كيفية تأثير الأرقام؟

هذا غير معروف أن يكون NP-C، ولكن لم يعرف أي حل زمني متعدد الحدود [*]، لذلك من المؤكد أنه غير معروف بالتأكيد في P.

أعتقد أن الإجابة على سؤالي، والسؤال الأصلي، هو "نعم"، وللأسباب نفسها. بعض المشاكل ليس لها أي حل يميل جيدا، ولكن يجب حلها على أي حال لبعض المدخلات. إذا كنت بحاجة إلى مبرمجين يمكنهم التعامل مع مثل هذه المشكلات، فهناك طريقة جيدة للسماح لهم بإثبات ذلك في مقابلة، وهذا هو الملعب لهم واحد ومعرفة ما إذا كانوا يخيفون.

إذا ادعي شخص ما خلفية COMPSCI، فعليهم أن يتمكنوا من تقديم حلول جيدة لمشاكل معينة من مشكلات NP-C عند الطلب، مثل حل مشكلة NEASTACK مع البرمجة الديناميكية. أود أن أعتبر أنه لا طائل منه أن يطلب مقدم طلب وظيفة برمجة لأخذ مشكلة لم يسبق له مثيلها من قبل، وتثبت فعلا أنه NP كامل (على سبيل المثال عن طريق تقليل الحرف إلى المشكلة المحددة). لا تحتاج الكثير من المبرمجين لكل شركة يمكنهم القيام بذلك (عادة 0)، وكل ما يكتشفه كل ما يكتشفه هو المدة التي يستمر فيها المرشح في ذلك قبل محاولة تغيير الموضوع والقيام بشيء أكثر قيمة مع وقت المقابلة. ..

*] متعدد الحدود في حجم المدخلات في البتات، وهذا هو. غالبا ما ترى الناس يناقشون تعقيد الخوارزميات للمشاكل الصحيحة مثل العظام من حيث حجم الرقم الذي يمثله المدخلات، مثل أقسام المحاكمة "SQRT (N)". ولكن هذا ليس كيف يتم تعريف NP و NP-C.

Answer 10

لا، إنها وقحة وتوقيع على أن المقابلة يحب أن يكون في موقف السلطة. هاها، بيون! أنا أعرف الجواب، وأنت لا! والصبي، هل أحب أن أجعلك تضخم يحاول التوصل إلى ذلك!

حول الطريقة الوحيدة التي يمكن أن تكون صالحة حتى قليلا كمسألة مقابلة مفيدة هو أن يكون سؤالا معروفا أو أحدهما كان من الواضح أنه من الواضح أن np-complete، وسأل بطريقة تشجع في مناقشة الجدوى.

Answer 11

لا حرج في إعطاء مشكلة كاملة من NP كتحدي برمجة أثناء مقابلة. أرى شيئا خطأ فقط في توقع إيجاد حل زمني متعدد الحدود للمشكلة أثناء المقابلة.

يجب أن يرغب أحد المقابل في معرفة كيف يتعامل المرشح مع مجموعة متنوعة من المواقف - بما في ذلك الحالات التي لا يمكن للمرشح العثور على حل سهل. الأسئلة "المستحيلة" تظهر كيف يتفاعل المرشح عندما لا يوجد حل بسيط. هل المرشح يستسلم فقط؟ كم عدد المحاولات المختلفة التي يبحث فيها المرشح؟ ما مدى استمرار المحاليل؟ متى يطلب المرشح المساعدة - وكيف؟ هل يشتكي المرشح من أن المشكلة "ليست عادلة"؟

باختصار، مثل هذا السؤال المقابلة ليس حول حل P = NP ... إنها إجابة نفسية.

Answer 12

إذا تم تقديم مثل هذا السؤال قبل مقابلة (سيتم الرد عليه في مقابلة)، أود أن أقول أنه على ما يرام .. ولكن فقط لحل مثل هذه المشكلة الصعبة مثل ذلك على الفور لن يتم بالتأكيد أي مبرمج، و إذا كان المبرمج يفعل ذلك جيدا، فهذا يعني أنهم فقط يمكنهم أن يتصرفون على الفور (الذين ليسوا دائما أفضل شيء للبرمجة حيث يحتاج تصميم الأشياء إلى اتخاذ بعض الوقت وتحقق من كل عيب ممكن) أو أنهم شاهدوا مشكلة مماثلة من قبل.

تحرير: أو ربما مناقشة حول المشكلة ستكون جيدة، مثل القول وضع خطة عمل ما إذا كنت تحلها تماما .. ومناقشة مدى قدرتها وإذا كان هناك طريقة سريعة (ولكن صعبة) للقيام بذلك ومثلها. لن أقول إن الشخص الذي تمت مقابلته يجب أن يكتب أكثر من 50 خطا من كود C في مقابلة لحلها على الرغم من

Answer 13

هذا شرير!

إذا كان المقابلة يسأل سؤالا غير متكامل في القائم بإجراء مقابلة، فإن الاستجابة الوحيدة التي يمكن أن تتوقعها بشكل معقول هو أن يستجيب الشخص الذي تمت مقابلته دليلا على أن المشكلة تكمل NP. في بيئة منخفضة الإجهاد مثل سؤال الواجبات المنزلية الجامعية، فإن هذا عادة ما يأخذ طالب مشرق 2-3 ساعات أو أكثر لإثبات. يمكن أن يستغرق الدليل نفسه عدة صفحات للكتابة تماما، ربما عدة ساعات من العمل نفسها. في بيئة عالية الإجهاد مثل مقابلة، يمكنك أن تتوقع أن لا يتعرف ذلك على أن هذا هو NP-Complete.

البديل الوحيد المعقول هو أن يستنتج معاديله خوارزمية تقريبية؛ ومع ذلك، في هذه الحالة يجب على القائم بإجراء المقابلة جعله صراحة واضح أنهم بخير مع التقريب.

ومع ذلك، فإن معظم التقديرات تأتي فقط بأمر 2 من الإجابة الصحيحة.

أعتقد أن هناك 1 بديلا آخر: يقترح المقابلة أن خوارزمية من نوع البحث ربما تكون الأنسب (تأخذ على سبيل المثال مشكلة تحسين المجال عدد صحيح والتي تعد NP-Complete، معظم خوارزميات التقريبات تستخدم فرع وتدور بحث ملزم على البسيط خوارزمية لإنتاج نتائج لائقة.)

Answer 14

أنا أفضل أن أطلب منهم إثبات أن P! = NP أو P == NP. في يوم من الأيام سوف يجيب المرشح عليه، سأرقم إجابته ويكون مشهورا!

في ملاحظة أكثر خطورة، على الرغم من ذلك، أعتقد أنه من المعارض تماما. معظم مشاكل NP كاملة من السهل حلها، فهي تعمل ببطء شديد. ما لم تتطلب الوظيفة منهم معرفة الكثير عن نظرية التعقيد، على الرغم من أن كل ما يحتاجون إليه للتظاهر هو أنهم يفهمون الحل سيكون بطيئا. نقاط المكافأة إذا كانوا يعرفون الوقت غير متعدد الحدود، نجم الذهب إذا كان يعرفون أن NP كاملة.