ملخص Array للمقابلات البرمجية

مقدمة

تحمل الـArrays قيماً من النوع نفسه في مواضع ذاكرة متجاورة. وفي الـArray، نهتم عادةً بأمرين — موضع/فهرس العنصر والعنصر نفسه. وتطبق لغات البرمجة المختلفة الـArrays داخلياً بطرق مختلفة، وقد يؤثر ذلك في الـtime complexity للعمليات التي تجريها على الـArray. ففي بعض اللغات مثل Python وJavaScript وRuby وPHP، يكون حجم الـArray (أو القائمة في Python) ديناميكياً ولا تحتاج إلى تحديد حجم مسبقاً عند إنشائها. ونتيجةً لذلك، يجد الناس عادةً أن استخدام هذه اللغات في المقابلات أسهل.

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

المزايا

• تخزين عناصر متعددة من النوع نفسه باسم متغير واحد
• الوصول إلى العناصر سريع ما دام لديك الفهرس، بخلاف الـLinked Lists حيث يجب الاجتياز من الرأس.

العيوب

• إضافة العناصر إلى منتصف الـArray وحذفها منها بطيء لأن العناصر المتبقية يجب إزاحتها لاستيعاب العنصر الجديد/المفقود. والاستثناء هو إذا كان الموضع المراد الإدراج/الحذف فيه عند نهاية الـArray.
• في بعض اللغات حيث حجم الـArray ثابت، لا يمكن تغيير حجمها بعد التهيئة. وإذا تسبب إدراج في تجاوز العدد الإجمالي للعناصر الحجمَ المخصص، فيجب تخصيص Array جديدة ونسخ العناصر الموجودة إليها. ويستغرق إنشاء Array جديدة ونقل العناصر زمناً O(n).

مصادر التعلم

• قراءات
  • Array in Data Structure: What is, Arrays Operations، Guru99
• فيديوهات
  • Arrays، University of California San Diego

مصطلحات شائعة

مصطلحات شائعة ستراها عند حل مسائل تتضمن Arrays:

• الـSubarray — نطاق من القيم المتجاورة داخل Array.
  • مثال: في الـArray [2, 3, 6, 1, 5, 4]، تُعد [3, 6, 1] Subarray بينما [3, 1, 5] ليست كذلك.
• الـSubsequence — تسلسل يمكن اشتقاقه من التسلسل المعطى بحذف بعض العناصر أو دون حذف أي منها دون تغيير ترتيب العناصر المتبقية.
  • مثال: في الـArray [2, 3, 6, 1, 5, 4]، تُعد [3, 1, 5] Subsequence لكن [3, 5, 1] ليست كذلك.

الـtime complexity

أمور يجب الانتباه إليها أثناء المقابلات

• وضّح ما إذا كانت هناك قيم مكررة في الـArray. هل يؤثر وجود قيم مكررة في الإجابة؟ وهل يجعل السؤال أبسط أم أصعب؟
• عند استخدام فهرس للتكرار عبر عناصر الـArray، احذر الخروج عن الحدود.
• انتبه عند اقتطاع الـArrays أو تسلسلها في شيفرتك. فعادةً ما يستغرق اقتطاع الـArrays وتسلسلها زمناً O(n). استخدم فهرسي البداية والنهاية لتحديد Subarray/نطاق حيثما أمكن.

الحالات الحدّية

• تسلسل فارغ
• تسلسل بعنصر أو عنصرين
• تسلسل بعناصر مكررة
• قيم مكررة في التسلسل

تقنيات

لاحظ أنه لكون كل من الـArrays والـStrings تسلسلات (فالـString Array من المحارف)، فإن معظم التقنيات هنا ستنطبق على مسائل الـStrings.

الـSliding Window

أتقن تقنية الـSliding Window التي تنطبق على العديد من مسائل الـArrays/السلاسل الفرعية. في الـSliding Window، يتحرك المؤشران عادةً في الاتجاه نفسه ولن يتجاوز أحدهما الآخر أبداً. وهذا يضمن أن كل قيمة تُزار مرتين على الأكثر وأن الـtime complexity يبقى O(n). أمثلة: Longest Substring Without Repeating Characters، Minimum Size Subarray Sum، Minimum Window Substring

Two Pointers

المؤشران صيغة أعم من الـSliding Window حيث يمكن للمؤشرين أن يتقاطعا وأن يكونا على اثنتين من الـArrays المختلفتين. أمثلة: Sort Colors، Palindromic Substrings

عندما تُعطى اثنتين من الـArrays لمعالجتهما، من الشائع أن يكون لكل Array فهرس (مؤشر) لاجتيازهما/مقارنتهما معاً، مع زيادة أحد المؤشرين عند الحاجة. فمثلاً، نستخدم هذا الأسلوب لدمج اثنتين من الـArrays المرتبة. أمثلة: Merge Sorted Array

الاجتياز من اليمين

يمكنك أحياناً اجتياز الـArray بدءاً من اليمين بدلاً من الأسلوب التقليدي من اليسار. أمثلة: Daily Temperatures، Number of Visible People in a Queue

ترتيب الـArray

هل الـArray مرتبة أو مرتبة جزئياً؟ إذا كانت كذلك، فينبغي أن يكون شكل من أشكال الـBinary Search ممكناً. وهذا يعني عادةً أن المحاور يبحث عن حل أسرع من O(n).

هل يمكنك ترتيب الـArray؟ أحياناً قد يبسّط ترتيب الـArray أولاً المسألة كثيراً. ومن الواضح أن هذا لن يعمل إذا كان ترتيب عناصر الـArray يجب المحافظة عليه. أمثلة: Merge Intervals، Non-overlapping Intervals

الحساب المسبق

في الأسئلة التي تتضمن جمع أو ضرب Subarray، قد يكون الحساب المسبق باستخدام التجزئة أو المجموع/حاصل الضرب البادئ/اللاحق مفيداً. أمثلة: Product of Array Except Self، Minimum Size Subarray Sum، أسئلة LeetCode الموسومة بـ "prefix-sum"

الفهرس كمفتاح تجزئة

إذا أُعطيت تسلسلاً وطلب المحاور مساحة O(1)، فقد يكون ممكناً استخدام الـArray نفسها كHash Table. فمثلاً، إذا كانت الـArray تحتوي فقط قيماً من 1 إلى N حيث N طول الـArray، فاعكس إشارة القيمة عند ذلك الفهرس (ناقص واحد) للإشارة إلى وجود ذلك العدد. أمثلة: First Missing Positive، Daily Temperatures

اجتياز الـArray أكثر من مرة

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

أسئلة أساسية

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

• Two Sum
• Best Time to Buy and Sell Stock
• Product of Array Except Self
• Maximum Subarray

أسئلة تدريب موصى بها

هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.

• Contains Duplicate
• Maximum Product Subarray
• Search in Rotated Sorted Array
• 3Sum
• Container With Most Water
• Sliding Window Maximum

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

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