ملخص Matrix للمقابلات البرمجية
مقدمة
الـMatrix هي Array ثنائية الأبعاد. وترتبط الأسئلة التي تتضمن Matrices عادةً بـDynamic Programming أو اجتياز الـGraphs.
يمكن استخدام الـMatrices لتمثيل الـGraphs حيث تكون كل عقدة خلية في الـMatrix لها 4 جيران (باستثناء الخلايا الواقعة على الحواف والزوايا). ستركز هذه الصفحة على الأسئلة التي لا تستخدم الـMatrix كـGraph. أما الأسئلة المقصود بها استخدام الـMatrix كـGraph فتجدها في قسم الـGraphs.
الحالات الحدّية
- Matrix فارغة. تحقق من ألا يكون أي من الـMatrices بطول 0
- Matrix 1 × 1
- Matrix ذات صف أو عمود واحد فقط
تقنيات
إنشاء Matrix فارغة بحجم N × M
في الأسئلة التي تتضمن الاجتياز أو الـDynamic Programming، ستحتاج دائماً تقريباً إلى إنشاء نسخة من الـMatrix بالحجم/الأبعاد نفسها مهيأة بقيم فارغة لتخزين حالة الزيارة أو جدول الـDynamic Programming. كن على دراية بهذا الإجراء بلغة البرمجة التي تختارها:
يمكن إنجاز ذلك بسهولة في Python في سطر واحد.
# Assumes that the matrix is non-empty zero_matrix = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
أما نسخ Matrix في Python فيكون:
copied_matrix = [row[:] for row in matrix]
التحويل بين الفهارس الأحادية والثنائية الأبعاد
يمكن التعامل مع Matrix m x n كـArray أحادية البعد تحتوي m * n عنصراً. فإذا كان لديك فهرس يبدأ من الصفر في تلك الـArray، فاقسمه على عدد الأعمدة للحصول على الصف واستخدم الباقي للحصول على العمود:
row = index // num_columns col = index % num_columns
ولتحويل الصف والعمود مرة أخرى إلى فهرس أحادي البعد:
index = row * num_columns + col
يمكن أن تكون هذه التقنية مفيدة عند تطبيق Algorithms مثل الـBinary Search على Matrix.
مداورة الـMatrix
يتم إيجاد مدور الـMatrix بتبديل صفوفها إلى أعمدة أو أعمدتها إلى صفوف.
يمكن نمذجة العديد من الألعاب القائمة على الشبكات كـMatrix، مثل Tic-Tac-Toe وSudoku والكلمات المتقاطعة وConnect 4 وBattleship وغيرها. وليس من غير المألوف أن يُطلب منك التحقق من شرط الفوز في اللعبة. وفي ألعاب مثل Tic-Tac-Toe وConnect 4 والكلمات المتقاطعة، حيث يجب إجراء التحقق عمودياً وأفقياً، تتمثل إحدى الحيل في كتابة شيفرة للتحقق من الـMatrix أفقياً، ثم مداورة الـMatrix، وإعادة استخدام منطق التحقق الأفقي للتحقق من الخلايا التي كانت عمودية في الأصل (والتي أصبحت الآن أفقية).
مداورة Matrix في Python بسيطة:
transposed_matrix = [[matrix[i][j] for i in range(len(matrix))] for j in range(len(matrix[0]))]
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.