ملخصات دراسة Data Structures وAlgorithms للمقابلات البرمجية

ما هذا

يتعمق هذا القسم في المعرفة العملية والتقنيات الخاصة بالـAlgorithms وData Structures التي تتكرر في مقابلات الـAlgorithms. وكلما زادت التقنيات في جعبتك، ارتفعت فرص اجتياز المقابلة. فقد تقودك إلى اكتشاف حالات حدّية فاتتك أو حتى تقودك نحو الأسلوب الأمثل!

محتويات كل دليل دراسة

لكل موضوع، يمكنك أن تتوقع إيجاد:

1. نظرة عامة موجزة
2. مصادر تعلم
3. مكتبات خاصة بكل لغة يمكن استخدامها
4. ملخص للتعقيدات الزمنية
5. أمور يجب الانتباه إليها أثناء المقابلات
6. حالات حدّية
7. تقنيات مفيدة مع أسئلة موصى بها للتدريب

قائمة أدلة الدراسة

فيما يلي قائمة Data Structures والـAlgorithms التي ينبغي أن تحضّرها للمقابلات البرمجية وأدلة الدراسة المقابلة لها:

نصائح عامة للمقابلات

وضّح أي افتراضات وضعتها لا شعورياً. فالكثير من الأسئلة ناقصة التحديد عن قصد.

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

هل هناك متطلبات أو قيود على الـtime complexity/المكاني؟

افحص أخطاء الفارق بواحد (off-by-one).

في اللغات التي لا يوجد فيها تحويل تلقائي للأنواع، تحقق من أن القيم المتسلسلة من النوع نفسه: int/str/list.

بعد الانتهاء من شيفرتك، استخدم بعض الأمثلة المدخلة لاختبار حلك.

هل يُفترض أن تعمل الـAlgorithm عدة مرات، كما في خادم ويب مثلاً؟ إذا كان الجواب نعم، فمن المرجح أن تكون المدخلات قابلة للمعالجة المسبقة لتحسين الكفاءة في كل استدعاء.

استخدم مزيجاً من نمطي البرمجة الوظيفية والأمرية:

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

عموماً، لتحسين سرعة البرنامج يمكننا إما: (1) اختيار هيكل بيانات/Algorithm أنسب؛ أو (2) استخدام ذاكرة أكبر. يجسد الخيار الأخير المقايضة التقليدية بين المساحة والزمن، لكن ليس بالضرورة أن تكون السرعة الأفضل على حساب المساحة فقط. ولاحظ أيضاً أن هناك غالباً حداً نظرياً لسرعة برنامجك (من حيث الـtime complexity). فمثلاً، سؤال يتطلب إيجاد أصغر/أكبر عنصر في Array غير مرتبة لا يمكن أن يعمل أسرع من O(N).

Data Structures هي أسلحتك. واختيار السلاح المناسب للمعركة المناسبة هو مفتاح النصر. كن على دراية تامة بنقاط قوة كل هيكل بيانات والتعقيدات الزمنية لعملياته المختلفة.

يمكن تعزيز Data Structures لتحقيق تعقيدات زمنية فعالة عبر عمليات مختلفة. فمثلاً، يمكن استخدام خريطة تجزئة مع Linked List مزدوجة لتحقيق تعقيد زمني O(1) لكل من عمليتي get وput في ذاكرة LRU المؤقتة.

الـHash Table هو على الأرجح Data Structure الأكثر استخداماً في أسئلة الـAlgorithms. إذا علقت في سؤال، فملاذك الأخير أن تعدّد Data Structures الشائعة الممكنة (ولحسن الحظ أنها ليست كثيرة) وتنظر فيما إذا كان كل منها قابلاً للتطبيق على المسألة. وقد نجح هذا معي أحياناً.

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

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

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