أهم التقنيات لمقاربة أسئلة مقابلات البرمجة وحلها

أكبر مخاوف معظم المرشحين خلال مقابلة البرمجة هو: ماذا لو علقتُ في السؤال ولم أعرف كيف أحله؟ لحسن الحظ، هناك طرق منظمة لمقاربة أسئلة مقابلات البرمجة تزيد فرصك في حلها. من كيفية إيجاد حل أو نهج، إلى تحسين الـtime complexity والمكاني، إليك بعضاً من أهم النصائح وأفضل الممارسات التي ستساعدك على حل أسئلة مقابلات البرمجة.

كيف تجد حلولاً لمسائل مقابلات البرمجة

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

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

1. تصوّر المسألة برسمها

هل تساءلت يوماً لماذا تُجرى مقابلات البرمجة تقليدياً على السبورات البيضاء، ولماذا تميل الفيديوهات التي تشرح إجابات أسئلة البرمجة إلى استخدام الـGraphs؟ السبورات البيضاء تسهّل رسم الـGraphs مما يساعد على حل المسائل! جزء كبير من البرمجة هو فهم كيف تتغير الحالة الداخلية للبرنامج، والـGraphs أدوات مفيدة جداً لتمثيل حالة Data Structures الداخلية. إذا كنت تجد صعوبة في فهم كيفية الوصول إلى الحل، فأوجد تمثيلاً بصرياً للمسألة، وعند الضرورة، للحالات الداخلية في كل خطوة.

هذه التقنية مفيدة خصوصاً إذا كان المدخل يتضمن Trees أو رسوماً بيانية أو Arrays أو قوائم متصلة.

مثال

كيف تعيد جميع عناصر Array بترتيب حلزوني؟ رسم الـArray والخطوات التي يحتاج مُكرِّرك اتخاذها في كل اتجاه سيساعد كثيراً في إتاحة رؤية النمط أمامك.

2. فكر في كيفية حل المسألة يدوياً

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

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

مثال

كيف تتحقق من أن Tree هي Binary Search Tree صالحة دون كتابة أي شيفرة؟ تتحقق أولاً من أن الـTree الفرعية اليسرى تحوي قيماً أصغر من الجذر فقط، ثم تتحقق أن الـTree الفرعية اليمنى تحوي قيماً أكبر من الجذر فقط، ثم تكرر ذلك لكل عقدة. تبدو هذه العملية قابلة للتنفيذ. الآن عليك فقط تحويلها إلى شيفرة.

3. أوجد المزيد من الأمثلة

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

4. قسّم السؤال إلى أجزاء أصغر مستقلة

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

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

مثال

مسألة Group Anagrams يمكن تقسيمها إلى جزأين — حساب بصمة الـString، وتجميع الـStrings معاً. كل جزء يمكن حله على حدة بتفاصيل تنفيذ مستقلة. يمكنك البدء بهذه الشيفرة:

def group_anagrams(strings):
  def hash(string):
    # Fill in later
    pass

  def group_strings(strings_hashes):
    # Fill in later
    pass

  strings_hashes = [(string, hash(string)) for string in strings]
  return group_strings(strings_hashes)

ثم تتابع لتملأ تنفيذ كل دالة. لكن لاحظ أن الحلول الأكثر كفاءة أحياناً تتطلب كسر بعض التجريدات وإجراء عدة عمليات في مرور واحد على المدخل. إذا طلب منك المُقابِل التحسين انطلاقاً من حلك المجرد جيداً، فذلك أحد المسارات الممكنة للمضي قدماً.

5. جرّب تطبيق Data Structures والـAlgorithms الشائعة على المسألة

على خلاف هندسة البرمجيات في العالم الحقيقي حيث تكون المسائل عادة مفتوحة النهايات وقد لا تكون لها حلول واضحة، تميل مسائل مقابلات البرمجة إلى أن تكون أصغر بطبيعتها ومصممة لتكون قابلة للحل ضمن مدة المقابلة. ويمكنك أيضاً توقع أن المعرفة المطلوبة لحل المسألة ليست خارقة وقد دُرست خلال الجامعة. لحسن الحظ، عدد Data Structures والـAlgorithms الشائعة محدود، ونهج مفعّل يعمل من تجربتي هو محاولة المرور على جميع Data Structures الشائعة وتطبيقها على المسألة.

هذه Data Structures التي ينبغي وضعها في الاعتبار وتجربتها، مرتبة حسب تكرار ظهورها في أسئلة مقابلات البرمجة:

• Hash Tables (Hash Maps): مفيدة لجعل البحث عن القيم كفوءاً. هذه أكثر هيكل بيانات شيوعاً في المقابلات ومن المؤكد أنك ستضطر لاستخدامه.
• Graphs: إذا قُدّمت إليك البيانات كارتباطات بين كيانات، فقد تتمكن من نمذجة السؤال كـGraph واستخدام بعض Graph Algorithms الشائعة لحل المسألة.
• Stack وQueue: إذا كنت بحاجة إلى تحليل String ذات خصائص متداخلة (كمعادلة رياضية)، فستحتاج شبه مؤكد إلى استخدام الـStacks.
• Heap: السؤال يتضمن جدولة/ترتيباً بناءً على أولوية ما. مفيدة أيضاً لإيجاد أكبر K/أصغر K/وسيط العناصر في مجموعة.
• Tree أو Trie: هل تحتاج إلى تخزين Strings بكفاءة مساحية والبحث عن وجود سلاسل (أو أجزاء منها على الأقل) بسرعة كبيرة؟

الإجراءات

• الترتيب
• الـBinary Search: مفيد إذا كانت Array المدخل مرتبة وتحتاج إلى بحث أسرع من O(n)
• الـSliding Window
• Two Pointers
• Union find
• BFS/DFS
• الاجتياز من النهاية
• الترتيب الطوبولوجي

سنضيف مستقبلاً نصائح حول كيفية التعرف بشكل أفضل إلى Data Structures والإجراءات الأكثر صلة بناءً على المسألة.

كيف تحسّن نهجك أو حلك

بعد أن تتوصل إلى حل أولي لمسألة مقابلة البرمجة، من المرجح أن يدفعك المُقابِل لتحسين الحل بسؤال "هل يمكننا فعل ما هو أفضل؟". التقنيات التالية تساعدك على تحسين الـtime complexity والمكاني لحلك بصورة أكبر:

كيف تحسّن الـtime complexity

1. حدد أفضل تعقيد زمني نظري للحل

أفضل تعقيد زمني نظري (BTTC) للحل هو تعقيد زمني تعلم أنك لا تستطيع تجاوزه.

بعض الأمثلة المبسطة:

• أفضل تعقيد نظري لإيجاد مجموع الأرقام في Array هو O(n) لأنك مضطر للنظر إلى كل قيمة في الـArray مرة واحدة على الأقل
• أفضل تعقيد نظري لإيجاد عدد مجموعات الكلمات المتبادلة الحروف هو O(nk) حيث n عدد الكلمات وk الحد الأقصى لعدد الحروف في الكلمة، لأنك مضطر للنظر إلى كل كلمة مرة واحدة على الأقل والنظر إلى كل حرف في كل كلمة مرة واحدة على الأقل
• أفضل تعقيد نظري لإيجاد عدد الجزر في Array هو O(nm) حيث n عدد الصفوف وm عدد الأعمدة، لأنك مضطر للنظر إلى كل خلية في الـArray مرة واحدة على الأقل

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

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

• إيجاد رقم سيكون O(log(n)) لأنك تستطيع استخدام Binary Search.
• إيجاد أكبر رقم سيكون O(1) لأنه آخر قيمة في الـArray.

لهذا من المهم الانتباه إلى كل تفصيل معطى عن السؤال. احذر أن تحدد تعقيداً نظرياً خاطئاً بسبب عدم الانتباه لتفاصيل السؤال!

وبتحديد التعقيد النظري الصحيح، تعلم الآن أن الـtime complexity للحل الأمثل يقع بين حلك الأولي والتعقيد النظري، ويمكنك شق طريقك نحوه. إذا كان حلك قد بلغ التعقيد النظري أصلاً والمُقابِل يطلب تحسيناً إضافياً، فعادةً هناك شيئان يبحث عنهما:

• إنجاز عمل أقل. قد يكون حلك O(n) لكنه يمر على الـArray مرتين، والمُقابِل يبحث عن الحل الذي يستخدم مروراً واحداً.
• استخدام مساحة أقل. راجع القسم أدناه حول تحسين الـspace complexity.

2. حدد الحسابات المتداخلة والمكررة

الحل الساذج/القوة الغاشمة غالباً ينفذ العملية نفسها مراراً وتكراراً. عندما تنفذ الشيفرة عملية مكلفة سبق تنفيذها، خذ لحظة لتتراجع وتفكر فيما إذا كان بإمكانك إعادة استخدام نتائج الحسابات السابقة. الـDynamic Programming (DP) هي أوضح نوع من الأسئلة التي يمكنك الاستفادة فيها كلياً من الحسابات السابقة. وهناك أسئلة غير ديناميكية يمكنها الاستفادة من هذه التقنية أيضاً، وإن لم تكن مباشرة بالقدر نفسه وقد تتطلب خطوة معالجة مسبقة.

مثال

سؤال Product of Array Except Self مثال جيد على مسألة تحوي عملاً متداخلاً/مكرراً. للحصول على قيمة لمؤشر ما، تحتاج لضرب القيم في كل المواضع الأخرى. فعل ذلك لكل قيمة في الـArray سيستغرق O(n²) من الوقت. لكن لاحظ أن:

• result[n]: Product(nums[0] … nums[n-1]) * Product(nums[n + 1] … nums[N - 1])
• result[n + 1]: Product(nums[0] … nums[n]) * Product(num[n + 2] … nums[N - 1])

هناك قدر هائل من العمل المكرر في حساب result[n] مقابل result[n + 1]! هذه فرصة لإعادة استخدام حسابات سابقة أُجريت أثناء حساب result[n] لحساب result[n + 1]. وبالفعل، يمكننا استخدام Array بادئات لمساعدتنا على الوصول إلى الحل النهائي بوقت O(n) على حساب مساحة إضافية.

3. جرّب هياكل بيانات مختلفة

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

هل وقت البحث عن القيم يبطئ خوارزميتك؟ عموماً، معظم عمليات البحث ينبغي أن تكون O(1) بمساعدة Hash Table. إذا كانت عملية البحث في حلك هي عنق الزجاجة لتعقيدها الزمني، فغالباً يمكنك استخدام Hash Table لتحسين البحث.

مثال

سؤال K Closest Points to Origin يمكن حله بأسلوب ساذج بحساب مسافة كل نقطة، وترتيبها، ثم أخذ أصغر K قيمة. يستغرق هذا O(nlog(n)) بسبب الترتيب. لكن باستخدام هيكل بيانات الـHeap، يمكن خفض الـtime complexity إلى O(nlog(k)) لأن الإضافة/الإزالة من الـHeap تستغرق فقط O(log(k)) عندما يكون حجم الـHeap محدوداً بـ K عنصراً. تغيير Data Structure أحدث فرقاً هائلاً في كفاءة الـAlgorithm!

4. حدد العمل الزائد عن الحاجة

إليك بضعة أمثلة على شيفرة تنجز عملاً زائداً عن الحاجة. ومع أن ارتكاب هذه الأخطاء قد لا يغير الـtime complexity الكلي لشيفرتك، إلا أنك تُقيَّم أيضاً على قدراتك البرمجية، لذا من المهم كتابة شيفرة بأكبر كفاءة ممكنة.

لا تتحقق من الشروط دون داعٍ

هذه أمثلة Python يكون فيها التحقق الثاني زائداً عن الحاجة.

• if not arr and len(arr) == 0 - التحقق الأول يضمن أصلاً أن الـArray فارغة، فلا حاجة للتحقق الثاني.
• x < 5 and x < 10 - التحقق الثاني شرط فرعي من التحقق الأول.

انتبه لترتيب التحققات

• if slow() or fast() - هناك عمليتان في هذا التحقق، بمدتين مختلفتين. ما دامت إحدى العمليتين تقيّم إلى true، فالشرط سيقيّم إلى true. معظم الحواسيب تنفذ العمليات بالترتيب من اليسار إلى اليمين، لذا من الأكفء وضع fast() على اليسار.
• if likely() and unlikely() - هذا المثال يستخدم حجة مشابهة لما سبق. إذا نفذنا unlikely() أولاً وكانت false، فلن نضطر لتنفيذ likely().

لا تستدعِ الدوال دون داعٍ

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

الإنهاء المبكر

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

def contains_string(search_term, strings):
  result = False
  for string in strings:
    if string.lower() == search_term.lower():
      result = True
  return result

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

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True # Stop comparing the rest of the array/list because the result won't change.
  return False

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

قلّل العمل داخل الحلقات

لنحسّن المثال أعلاه أكثر لحل السؤال "حدد إن كانت Array من الـStrings تحوي سلسلة ما بغض النظر عن حساسية حالة الأحرف".

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True
  return False

لاحظ أنك تستدعي search_term.lower() مرة في كل تكرار للحلقة! هذا إسراف لأن search_term لا يتغير طوال دورة حياة الدالة.

def contains_string(search_term, strings):
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False

قلّل العمل داخل الحلقات ولا تُعد إنجاز عمل أنجزته أصلاً إذا لم يتغير.

كن كسولاً

التقييم الكسول استراتيجية تقييم تؤجل تقييم التعبير حتى تُحتاج قيمته. لنستخدم المثال نفسه أعلاه. يمكننا تقنياً تحسينه قليلاً:

def contains_string(search_term, strings):
  if len(strings) == 0:
    return False
  # Don't have to change the search term to lower case if there are no strings at all.
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False

يُعد هذا تحسيناً دقيقاً (micro-optimization)، وفي معظم الأحيان لن تكون strings فارغة، لكني أستخدمه لتوضيح المثال حيث لا يتعين عليك إجراء حسابات معينة إذا لم تكن لازمة. ينطبق هذا أيضاً على تهيئة الكائنات التي ستحتاجها في شيفرتك (عادة Hash Tables). إذا كان المدخل فارغاً، فلا حاجة لتهيئة أي متغيرات!

كيف تحسّن الـspace complexity

في معظم الأحيان، الـtime complexity أهم من الـspace complexity. لكن عندما تكون قد بلغت الـtime complexity الأمثل أصلاً، قد يطلب منك المُقابِل تحسين المساحة التي يستخدمها حلك (إذا كان يستخدم مساحة إضافية). إليك بعض التقنيات التي يمكنك استخدامها لتحسين الـspace complexity لشيفرتك.

1. تغيير البيانات في مكانها/الكتابة فوق بيانات المدخل

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

طريقة ممكنة تعمل (لكن يجب ألا تستخدمها أبداً خارج مقابلات البرمجة) هي تعديل الـArray الأصلية واستخدامها كHash Table لتخزين بيانات وسيطة. راجع المثال أدناه.

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

مثال

مسألة Dutch National Flag يمكن حلها بسهولة بوقت O(n) ومساحة O(n) بإنشاء Array جديدة وملئها بالقيم المقابلة بشكل مرتب. وكتحدٍ إضافي وتحسين للمساحة، عادة ما يطلب المُقابِل حلاً بوقت O(n) ومساحة O(1) يتضمن ترتيب Array المدخل في مكانها.

مثال على استخدام الـArray الأصلية كHash Table هو سؤال First Missing Positive. بعد حلقة for الأولى، تكون كل القيم في الـArray موجبة، ويمكنك الإشارة إلى وجود رقم بعكس إشارة القيمة عند المؤشر الموافق للرقم. للإشارة إلى وجود 4، اعكس إشارة nums[4].

2. غيّر Data Structure

Data Structures مجدداً؟! نعم، Data Structures مجدداً! Data Structures أساسية جداً في مقابلات البرمجة، وإتقانها يصنع أداءك في المقابلة أو يكسره. هل تستخدم أفضل هيكل بيانات ممكن للمسألة؟

مثال

لديك قائمة من الـStrings وتريد معرفة كم منها يبدأ ببادئة معينة. ما الطريقة الكفوءة لتخزين السلاسل بحيث تحسب إجابتك بسرعة؟ Trie هي هيكل بيانات شجري كفوء جداً لتخزين الـStrings ويتيح لك أيضاً حساب عدد السلاسل التي تبدأ ببادئة ما بسرعة.

الخطوات التالية

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

• كيف تضع خطة كفوءة لتحضيرك لمقابلات البرمجة - متضمناً أولوية الموضوعات والأسئلة للدراسة بناءً على الوقت المتبقي لديك
• ورقة أفضل ممارسات مقابلات البرمجة - متضمنة كيفية التصرف خلال مقابلة البرمجة لإظهار إشارات التوظيف
• أوراق مرجعية للـAlgorithms - متضمنة ما يجب تذكره واستيعابه لكل هيكل بيانات

المصدر والرخصة

هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.