ملخص Sorting and Searching للمقابلات البرمجية
مقدمة
الترتيب هو عملية إعادة ترتيب العناصر في تسلسل وفق نظام معين، سواء كان ترتيباً عددياً أو أبجدياً، وتصاعدياً أو تنازلياً.
يعمل عدد من الـAlgorithms الأساسية بزمن O(n2) ولا ينبغي استخدامها في المقابلات. وفي مقابلات الـAlgorithms، من غير المرجح أن تحتاج إلى تطبيق أي من Sorting Algorithms من الصفر. وبدلاً من ذلك ستحتاج إلى ترتيب المدخلات باستخدام دالة الترتيب الافتراضية في لغتك حتى تتمكن من إجراء Binary Search عليها.
في Array عناصر مرتبة، وبالاستفادة من خاصية الترتيب، يمكن إجراء البحث فيها بزمن أسرع من O(n) باستخدام الـBinary Search. يقارن الـBinary Search القيمة المستهدفة مع العنصر الأوسط في الـArray، مما يُعلم الـAlgorithm ما إذا كانت القيمة المستهدفة تقع في النصف الأيسر أم الأيمن، ويستمر هذا المقارنة على النصف المتبقي حتى يُعثر على الهدف أو يفرغ النصف المتبقي.
مصادر التعلم
مع أنه من غير المرجح أن يُطلب منك تطبيق Algorithm ترتيب من الصفر أثناء مقابلة، فمن الجيد أن تعرف التعقيدات الزمنية المختلفة لSorting Algorithms المتنوعة.
- قراءات
- Sorting Out The Basics Behind Sorting Algorithms، basecs
- Binary Search، Khan Academy
- إضافية (فقط إذا كان لديك وقت)
- Exponentially Easy Selection Sort، basecs
- Bubbling Up With Bubble Sorts، basecs
- Inching Towards Insertion Sort، basecs
- Making Sense of Merge Sort (Part 1)، basecs
- Making Sense of Merge Sort (Part 2)، basecs
- Pivoting To Understand Quicksort (Part 1)، basecs
- Pivoting To Understand Quicksort (Part 2)، basecs
- Counting Linearly With Counting Sort، basecs
- Getting To The Root Of Sorting With Radix Sort، basecs
- فيديوهات
- Heapsort (الشرائح)، Samuel Albanie، University of Cambridge
- Quicksort (الشرائح)، Samuel Albanie، University of Cambridge
- Lower bounds for comparison sorts (الشرائح)، Samuel Albanie، University of Cambridge
- Counting sort (الشرائح)، Samuel Albanie، University of Cambridge
- Radix sort (الشرائح)، Samuel Albanie، University of Cambridge
- Bucket sort (الشرائح)، Samuel Albanie، University of Cambridge
الـtime complexity
| الـAlgorithm | الزمن | المساحة |
|---|---|---|
| الترتيب الفقاعي | O(n2) | O(1) |
| ترتيب الإدراج | O(n2) | O(1) |
| ترتيب الاختيار | O(n2) | O(1) |
| الترتيب السريع | O(nlog(n)) | O(log(n)) |
| ترتيب الدمج | O(nlog(n)) | O(n) |
| Heap Sort | O(nlog(n)) | O(1) |
| الترتيب بالعدّ | O(n + k) | O(k) |
| الترتيب الجذري | O(nk) | O(n + k) |
| الـAlgorithm | Big-O |
|---|---|
| الـBinary Search | O(log(n)) |
أمور يجب الانتباه إليها أثناء المقابلات
تأكد من أنك تعرف الـtime complexity والمكاني لSorting Algorithm الافتراضية في لغتك! فالـtime complexity هو بالتأكيد تقريباً O(n log n). ونقاط إضافية إذا استطعت تسمية Sorting Algorithm. في Python 3.11+، إنها Powersort التي حلت محل Timsort كSorting Algorithm الافتراضية. وفي Java، يُستخدم تطبيق لـ Timsort لترتيب الكائنات، ويُستخدم Dual-Pivot Quicksort لترتيب الأنواع البدائية.
الحالات الحدّية
- تسلسل فارغ
- تسلسل بعنصر واحد
- تسلسل بعنصرين
- تسلسل يحتوي عناصر مكررة
تقنيات
المدخلات المرتبة
عندما يكون التسلسل المعطى مرتباً (سواء تصاعدياً أو تنازلياً)، ينبغي أن يكون استخدام الـBinary Search من أوائل ما يخطر ببالك.
ترتيب مدخلات ذات نطاق محدود
الترتيب بالعدّ هو ترتيب غير قائم على المقارنة يمكنك استخدامه على أعداد تعرف نطاق قيمها مسبقاً. أمثلة: H-Index
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.