اتبع هذه الخطوات لحل أي مشكلة في مقابلة البرمجة الديناميكية

على الرغم من امتلاك خبرة كبيرة في بناء منتجات البرمجيات ، يشعر العديد من المهندسين بالقلق من فكرة إجراء مقابلة ترميز تركز على الخوارزميات. لقد أجريت مقابلات مع مئات المهندسين في Refdash ، و Google ، وفي الشركات الناشئة التي كنت جزءًا منها ، وبعض الأسئلة الأكثر شيوعًا التي تجعل المهندسين غير مرتاحين هي تلك التي تتضمن البرمجة الديناميكية (DP).

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

البرمجة الديناميكية - يمكن التنبؤ بها والتحضير لها

أحد الأسباب التي تجعلني أعتقد شخصيًا أن أسئلة DP قد لا تكون أفضل طريقة لاختبار القدرة الهندسية هو أنها يمكن التنبؤ بها وسهلة المطابقة. إنها تسمح لنا بتصفية المزيد من أجل الاستعداد بدلاً من القدرة الهندسية.

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

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

7 خطوات لحل مشكلة البرمجة الديناميكية

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

  1. كيفية التعرف على مشكلة DP
  2. تحديد متغيرات المشكلة
  3. التعبير بوضوح عن علاقة التكرار
  4. تحديد الحالات الأساسية
  5. قرر ما إذا كنت تريد تنفيذه بشكل تكراري أو متكرر
  6. أضف المذكرات
  7. تحديد مدى تعقيد الوقت

عينة DP مشكلة

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

عرض المشكلة:

في هذه المشكلة ، نحن على كرة قفز مجنونة ، نحاول التوقف ، مع تجنب المسامير على طول الطريق.

فيما يلي القواعد:

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

مثال على تمثيل مجموعة:

2) لقد أعطيت سرعة البدء S. S هي عدد صحيح غير سالب في أي نقطة معينة ، وهي تشير إلى مدى تقدمك في القفزة التالية.

3) في كل مرة تهبط فيها في مكان ما ، يمكنك ضبط سرعتك بما يصل إلى وحدة واحدة قبل القفزة التالية.

4) تريد التوقف بأمان في أي مكان على طول المدرج (لا يلزم أن تكون في نهاية المصفوفة). تتوقف عندما تصبح سرعتك 0. ومع ذلك ، إذا هبطت على ارتفاع في أي وقت ، فإن كرة القفز المجنونة تنفجر وتنتهي اللعبة.

يجب أن يكون ناتج وظيفتك منطقيًا يشير إلى ما إذا كان بإمكاننا التوقف بأمان في أي مكان على طول المدرج.

الخطوة الأولى: كيفية التعرف على مشكلة البرمجة الديناميكية

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

إن الاعتراف بإمكانية حل مشكلة ما باستخدام DP هو الخطوة الأولى والأكثر صعوبة في الغالب في حلها. ما تريد أن تسأله لنفسك هو ما إذا كان يمكن التعبير عن حل مشكلتك كوظيفة من الحلول لمشاكل أصغر مماثلة.

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

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

غالبًا ما يكون التعرف على مشكلة البرمجة الديناميكية هو أصعب خطوة في حلها. هل يمكن التعبير عن حل المشكلة كدالة لحل مشاكل أصغر مماثلة؟

الخطوة 2: تحديد متغيرات المشكلة

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

عادة في المقابلات ، سيكون لديك واحد أو اثنين من العوامل المتغيرة ، ولكن من الناحية الفنية قد يكون هذا أي رقم. المثال الكلاسيكي لمشكلة المتغير الواحد هو "تحديد رقم فيبوناتشي رقم n". مثال على مشكلة ذات متغيرين هو "حساب مسافة التعديل بين السلاسل". إذا لم تكن معتادًا على هذه المشكلات ، فلا تقلق بشأنها.

تتمثل إحدى طرق تحديد عدد المعلمات المتغيرة في سرد ​​أمثلة للعديد من المشكلات الفرعية ومقارنة المعلمات. يعد حساب عدد المعلمات المتغيرة أمرًا ذا قيمة لتحديد عدد المشكلات الفرعية التي يتعين علينا حلها. من المهم أيضًا في حد ذاته مساعدتنا على تعزيز فهم علاقة التكرار من الخطوة 1.

في مثالنا ، المعلمتان اللتان يمكن تغييرهما لكل مشكلة فرعية هما:

  1. موضع الصفيف (P)
  2. السرعة (S)

يمكن للمرء أن يقول أن المدرج أمامه يتغير أيضًا ، لكن هذا سيكون زائداً عن الحاجة بالنظر إلى أن المدرج غير المتغير بالكامل والموقع (P) يحملان هذه المعلومات بالفعل.

الآن ، مع هاتين المعلمتين المتغيرة والمعلمات الثابتة الأخرى ، لدينا وصف كامل لمشكلاتنا الفرعية.

تحديد المعلمات المتغيرة وتحديد عدد المشاكل الفرعية.

الخطوة 3: التعبير بوضوح عن علاقة التكرار

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

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

إليك كيف نفكر في الأمر في نموذجنا لمشكلتنا:

نظرًا لأنه يمكنك ضبط سرعتك بما يصل إلى 1 قبل القفز إلى الموضع التالي ، فهناك 3 سرعات ممكنة فقط ، وبالتالي 3 نقاط يمكن أن نكون فيها التاليين.

بشكل رسمي أكثر ، إذا كانت سرعتنا هي S ، الموضع P ، فيمكننا الانتقال من (S ، P) إلى:

  1. (S ، P + S) ؛ # إذا لم نغير السرعة
  2. (ق - 1 ، ف + ق - 1) ؛ # إذا غيرنا السرعة بمقدار -1
  3. (S + 1، P + S + 1) ؛ # إذا قمنا بتغيير السرعة بمقدار +1

إذا تمكنا من إيجاد طريقة للتوقف في أي من المشاكل الفرعية المذكورة أعلاه ، فيمكننا أيضًا التوقف عن (S ، P). هذا لأنه يمكننا الانتقال من (S ، P) إلى أي من الخيارات الثلاثة المذكورة أعلاه.

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

canStop (S، P) = canStop (S، P + S) || canStop (S - 1، P + S - 1) || canStop (S + 1، P + S + 1)

رائع ، يبدو أن لدينا علاقة التكرار!

علاقة التكرار: بافتراض أنك قمت بحساب المشكلات الفرعية ، كيف ستحسب المشكلة الرئيسية؟

الخطوة 4: تحديد الحالات الأساسية

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

السبب في عدم إمكانية تبسيط المشكلة بشكل أكبر هو أن إحدى المعلمات ستصبح قيمة غير ممكنة نظرًا لقيود المشكلة.

في مسألة المثال لدينا ، لدينا متغيران ، S و P. دعونا نفكر في القيم المحتملة لـ S و P التي قد لا تكون قانونية:

  1. يجب أن تكون P داخل حدود المدرج المحدد
  2. لا يمكن أن يكون P على هذا النحو المدرج [P] خطأ لأن هذا يعني أننا نقف على ارتفاع
  3. لا يمكن أن تكون S سالبة ، وتشير S == 0 إلى أننا انتهينا

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

في مثالنا:

  1. ف <0 || P> = يبدو أن طول المدرج هو الشيء الصحيح الذي ينبغي عمله. قد يكون البديل هو اعتبار m aking P == نهاية المدرج حالة أساسية. ومع ذلك ، من الممكن أن تنقسم المشكلة إلى مشكلة فرعية تتجاوز نهاية المدرج ، لذلك نحتاج حقًا إلى التحقق من عدم المساواة.
  2. يبدو هذا واضحًا جدًا. يمكننا ببساطة التحقق مما إذا كان المدرج [P] خاطئًا .
  3. على غرار رقم 1 ، يمكننا ببساطة التحقق من S <0 و S == 0. ومع ذلك ، يمكننا هنا التفكير في أنه من المستحيل أن تكون S <0 لأن S تنخفض بنسبة 1 على الأكثر ، لذلك يجب أن تمر عبر S == 0 حالة مسبقًا. لذلك فإن S == 0 هي حالة أساسية كافية للمعامل S.

الخطوة 5: حدد ما إذا كنت تريد تنفيذه بشكل متكرر أو متكرر

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

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

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

في مشكلتنا الخاصة ، قمت بتطبيق كلا الإصدارين. إليك كود Python لذلك:

حل متكرر: (يمكن العثور على مقتطفات التعليمات البرمجية الأصلية هنا)

حل تكراري: (يمكن العثور على مقتطفات التعليمات البرمجية الأصلية هنا)

الخطوة 6: إضافة memoization

Memoization هي تقنية مرتبطة ارتباطًا وثيقًا بـ DP. يتم استخدامه لتخزين نتائج مكالمات الوظائف باهظة الثمن وإرجاع النتيجة المخزنة مؤقتًا عند حدوث نفس المدخلات مرة أخرى.

لماذا نضيف memoization إلى العودية لدينا؟ نواجه نفس المشكلات الفرعية التي يتم حسابها بشكل متكرر بدون حفظ. غالبًا ما تؤدي هذه التكرارات إلى تعقيدات زمنية أسية.

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

هذا يعني أنه يجب عليك:

  1. تخزين نتيجة وظيفتك في ذاكرتك قبل كل بيان عودة
  2. ابحث في الذاكرة عن نتيجة الوظيفة قبل البدء في إجراء أي عملية حسابية أخرى

إليك الكود من الأعلى مع المذكرات المضافة (يتم تمييز الأسطر المضافة): (يمكن العثور على مقتطفات الشفرة الأصلية هنا)

لتوضيح فعالية الحفظ والأساليب المختلفة ، دعنا نجري بعض الاختبارات السريعة. سأقوم باختبار جميع الطرق الثلاث التي رأيناها حتى الآن. هنا هو الإعداد:

  1. لقد أنشأت مدرجًا بطول 1000 مع مسامير في أماكن عشوائية (اخترت أن يكون هناك احتمال أن يكون الارتفاع في أي مكان معين 20 ٪)
  2. initSpeed ​​= 30
  3. قمت بتشغيل جميع الوظائف 10 مرات وقياس متوسط ​​وقت التنفيذ

ها هي النتائج (بالثواني):

يمكنك أن ترى أن النهج العودي الخالص يستغرق حوالي 500 مرة أكثر من الأسلوب التكراري وحوالي 1300 مرة أكثر من الأسلوب التكراري مع الذاكرة. لاحظ أن هذا التناقض سينمو بسرعة مع طول المدرج. أنا أشجعك على محاولة تشغيله بنفسك.

الخطوة 7: تحديد مدى تعقيد الوقت

هناك بعض القواعد البسيطة التي يمكن أن تجعل تعقيد وقت الحوسبة لمشكلة البرمجة الديناميكية أسهل بكثير. فيما يلي خطوتان عليك القيام بهما:

  1. عد عدد الحالات - سيعتمد هذا على عدد المعلمات المتغيرة في مشكلتك
  2. فكر في العمل المنجز في كل ولاية. بمعنى آخر ، إذا تم حساب كل شيء آخر باستثناء حالة واحدة ، فما مقدار العمل الذي يتعين عليك القيام به لحساب تلك الحالة الأخيرة؟

في مشكلتنا كمثال ، عدد الحالات هو | P | * | S | ، أين

  • P هي مجموعة جميع المواضع (| P | تشير إلى عدد العناصر في P)
  • S هي مجموعة السرعات

العمل المنجز لكل حالة هو O (1) في هذه المشكلة لأنه ، بالنظر إلى جميع الحالات الأخرى ، علينا ببساطة النظر في 3 مشاكل فرعية لتحديد الحالة الناتجة.

كما أشرنا في الكود ، | S | مقيد بطول المدرج (| P |) ، لذلك يمكننا القول أن عدد الحالات هو | P | ² ولأن العمل المنجز لكل حالة هو O (1) ، فإن التعقيد الزمني الإجمالي هو O (| P | ²).

ومع ذلك ، يبدو أن | S | يمكن أن يكون محدودًا بشكل أكبر ، لأنه إذا كان حقًا | P | ، فمن الواضح جدًا أن التوقف لن يكون ممكنًا لأنك ستضطر إلى القفز على طول المدرج بأكمله في الخطوة الأولى.

لذلك دعونا نرى كيف يمكننا وضع حد أكثر إحكامًا على | S |. دعنا نسمي السرعة القصوى S. لنفترض أننا بدأنا من الموضع 0. ما السرعة التي يمكن أن نتوقف بها إذا كنا نحاول التوقف في أسرع وقت ممكن وإذا تجاهلنا الارتفاعات المحتملة؟

في التكرار الأول ، يجب أن نصل على الأقل إلى النقطة (S-1) ، بتعديل سرعتنا عند صفر بمقدار -1. من هناك سنمضي على الأقل بخطوات (S-2) للأمام ، وهكذا.

لمدرج بطول L ، يجب أن يثبت ما يلي:

=> (S-1) + (S-2) + (S-3) +…. + 1 <L

=> S * (S-1) / 2 <L

=> S² - S - 2L <0

إذا وجدت جذور الوظيفة المذكورة أعلاه ، فستكون:

r1 = 1/2 + sqrt (1/4 + 2L) و r2 = 1/2 - sqrt (1/4 + 2L)

يمكننا كتابة عدم المساواة لدينا على النحو التالي:

(S - r1) * (S - r2) < ؛ 0

بالنظر إلى أن S - r2> 0 لأي S> 0 و L> 0 ، نحتاج إلى ما يلي:

S - 1/2 - الجذر التربيعي (1/4 + 2 لتر) < ؛ 0

=> S <1/2 + sqrt (1/4 + 2L)

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

هذا يعني أن التعقيد الزمني الإجمالي يعتمد فقط على طول المدرج L بالشكل التالي:

O (L * sqrt (L)) وهو أفضل من O (L²)

O (L * sqrt (L)) هو الحد الأعلى لتعقيد الوقت

رائع ، لقد نجحت! :)

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

فيما يلي بعض الخطوات التالية التي يمكنك اتخاذها

  1. قم بتوسيع نموذج المشكلة بمحاولة إيجاد مسار لنقطة التوقف. لقد حللنا مشكلة تخبرك بما إذا كان بإمكانك التوقف ، ولكن ماذا لو أردت أيضًا معرفة الخطوات التي يجب اتخاذها للتوقف في النهاية على طول المدرج؟ كيف يمكنك تعديل التطبيق الحالي للقيام بذلك؟
  2. إذا كنت ترغب في ترسيخ فهمك للمذكرات ، وفهم أنها مجرد ذاكرة تخزين مؤقت لنتائج وظيفية ، فيجب أن تقرأ عن المصممين في لغة بايثون أو المفاهيم المماثلة في لغات أخرى. فكر في كيفية السماح لك بتنفيذ المذكرات بشكل عام لأي وظيفة تريد حفظها.
  3. اعمل على المزيد من مشاكل DP باتباع الخطوات التي مررنا بها. يمكنك دائمًا العثور على مجموعة منها عبر الإنترنت (على سبيل المثال ، LeetCode أو GeeksForGeeks). أثناء التدريب ، ضع في اعتبارك شيئًا واحدًا: تعلم الأفكار ، لا تتعلم المشكلات. عدد الأفكار أصغر بكثير وهي مساحة أسهل للتغلب عليها والتي ستفيدك أيضًا بشكل أفضل.

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

نشرت أصلا في مدونة Refdash. Refdash عبارة عن منصة للمقابلات تساعد المهندسين على إجراء مقابلات مع مهندسين ذوي خبرة من أفضل الشركات مثل Google أو Facebook أو Palantir دون الكشف عن هويتهم والحصول على ملاحظات مفصلة. يساعد Refdash المهندسين في اكتشاف فرص عمل مذهلة بناءً على مهاراتهم واهتماماتهم.