جدول المحتويات[يخفي][يعرض]
- 1. كيف تعرف المصفوفة؟
- 2. المصفوفات الديناميكية: ما المقصود بها؟ ما الذي يميزهم عن المصفوفات الأساسية؟
- 3. كيف تختلف المصفوفة والقاموس عن بعضهما البعض؟
- 4. اذكر بعض مزايا وعيوب المصفوفات.
- 5. إلى ماذا تشير "المصفوفة المتفرقة"؟
- 6. متى تختار قائمة مرتبطة على مصفوفة؟
- 7. ما الذي يميز المصفوفة المفهرسة عن المصفوفة الترابطية؟
- 8. ما هي المزايا التي يتمتع بها Heap على المصفوفات التي تم فرزها؟
- 9. هل يمكننا تحديد حجم المصفوفة لتكون سالبة؟
- 10. كيف يمكنك تحديد مكان العدد الصحيح المفقود في مصفوفة مكونة من 1 إلى 100 عنصر؟
- 11. كيف تجد فهرس عنصر في المصفوفة؟
- 12. كيف يمكنك التخلص من عنصر معين من المصفوفة؟
- 13. كيف يمكن التحقق من مساواة المصفوفتين؟
- 14. عندما نناقش المصفوفات ، ماذا تقصد بالعبارات "البعد" و "المخطوطة"؟
- أسئلة المقابلة الترميز
- 15. ابحث عن زوج في مصفوفة لها المجموع المحدد
- 16. الفرز الثنائي مع الزمن الخطي
- 17. أوجد أكبر حاصل ضرب ثنائي في المصفوفة.
- 18. كيفية إزاحة كل أصفار المصفوفة حتى النهاية
- 19. كيفية فرز مصفوفة بإدخالين يتم تبديلهما في عملية واحدة.
- 20. كيفية دمج مصفوفتين تم فرزهما في المكان.
- 21. كيفية إعادة ترتيب مجموعة من العناصر بالتناوب بين المواقع العالية والمنخفضة؟
- 22. كيف نستبدل كل عنصر من عناصر المصفوفة بدون استخدام عامل القسمة بحاصل ضرب كل عنصر في المصفوفة؟
- 23. أوجد أغرب عنصر في المصفوفة في الوقت اللوغاريتمي
- 24. كيف تحصل على العنصر الأكبر التالي لكل عنصر في مصفوفة دائرية؟
- 25. البحث عن عدد الانعكاس المصفوفة؟
- 26. ما هي مشكلة محاصرة مياه الأمطار؟
- وفي الختام
تحتوي مقابلات الترميز على سلسلة من أسئلة DSA. يجب أن تكون ماهرًا في التعامل مع المصفوفات إذا كنت تستعد لمقابلتك التقنية القادمة مع FAANG أو أي شركة تقنية أخرى من المستوى 1.
في معظم مقابلات الترميز ، تأتي في المرتبة الثانية بعد Strings. المصفوفة هي مجموعة من عناصر البيانات ذات الصلة المحفوظة على مقربة من بعضها البعض في الذاكرة.
نظرًا لأنها متصلة بجميع لغات البرمجة ، مثل C و C ++ و Java و Python و Perl و Ruby ، فهي موجودة في كل مكان. استمر في القراءة للتعرف على بعض تحديات الترميز وأسئلة وأجوبة المقابلة بناءً على المصفوفات.
سيتم استخدام Python في هذا المنشور لمعالجة مشكلات الترميز لأنها سهلة الاستخدام والفهم ويجب أن تكون مألوفة لمعظمنا.
هيا نبدأ.
1. كيف تعرف المصفوفة؟
- مجموعة أنواع البيانات ذات الصلة عبارة عن صفيف.
- المصفوفات ثابتة دائمًا.
- يتم تخزين نفس النوع من المتغيرات في عدة أماكن بواسطة كائنات المصفوفة.
- تتوافق كل من الأنواع الأولية ومراجع الكائنات معها.
2. المصفوفات الديناميكية: ما المقصود بها؟ ما الذي يميزهم عن المصفوفات الأساسية؟
يعد القياس التلقائي الذي توفره المصفوفات الديناميكية (يشار إليها أيضًا باسم المصفوفات القابلة للنمو أو المصفوفات القابلة لتغيير الحجم أو المصفوفات القابلة للتغيير أو ArrayLists في Java) ميزة مهمة.
يجب أن تعرف دائمًا عدد العناصر التي ستخزنها المصفوفة مسبقًا نظرًا لأن المصفوفات لها حجم ثابت. من ناحية أخرى ، تنمو المصفوفة الديناميكية مع إضافة أعضاء إضافيين إليها ، لذلك لا تحتاج إلى معرفة حجمها الدقيق مسبقًا.
3. كيف تختلف المصفوفة والقاموس عن بعضهما البعض؟
هذه مجموعة قائمة على الأساسيات من أسئلة المقابلة التي يتم طرحها بانتظام. فيما يلي الفروق الرئيسية بين المصفوفات والقواميس:
- المصفوفة هي قائمة مرتبة من العناصر المتشابهة. من ناحية أخرى ، يحتوي القاموس على أزواج مفتاح - قيمة.
- يمكن أن تتغير أحجام الصفيف ديناميكيًا. هذه الأفكار الديناميكية غير موجودة في القواميس.
- قبل استخدام المصفوفة ، يجب تحديد حجمها. لا يلزم تخصيص أحجام القاموس.
- استخدم تعليمة Redim إذا كنت ترغب في توسيع حجم المصفوفة. في القواميس ، يمكن إضافة عنصر بدون تصريح.
4. اذكر بعض مزايا وعيوب المصفوفات.
مزايا:
- يمكن للمصفوفات فرز عدد من العناصر في وقت واحد.
- أخرى هياكل البيانات، مثل المكدسات ، وقوائم الانتظار ، والقوائم المرتبطة ، والأشجار ، والرسوم البيانية ، وما إلى ذلك ، يمكن تنفيذها في مصفوفة.
- يمكن استخدام الفهرس للوصول إلى عنصر من المصفوفة.
العيوب:
- يجب الإعلان عن حجم المصفوفة مسبقًا. في لحظة إعلان المصفوفة ، قد لا نكون على دراية بالحجم الذي نطلبه.
- هيكل المصفوفة ثابت. وهذا يعني أن حجم الصفيف ثابت دائمًا ولا يمكن زيادة أو تقليل تخصيص الذاكرة.
5. إلى ماذا تشير "المصفوفة المتفرقة"؟
المصفوفة المتفرقة هي مصفوفة بيانات بها الكثير من الإدخالات بقيم صفرية. في المقابل ، تحتوي المصفوفة الكثيفة على غالبية عناصرها بقيم غير صفرية. قد تتضمن مؤشرات المصفوفة المتفرقة ، التي تحول الأرقام إلى كائنات ، فجوات. بالمقارنة مع HashMap ، فهي أكثر كفاءة في الذاكرة.
6. متى تختار قائمة مرتبطة على مصفوفة؟
عند استخدام القوائم المرتبطة بدلاً من المصفوفات ، ضع في اعتبارك:
- لا تحتاج إلى أي عناصر للحصول على وصول عشوائي.
- عندما تكون القدرة على التنبؤ الزمني ضرورية ، فأنت بحاجة إلى عمليات الإدراج والإزالة في الوقت الثابت من القائمة.
- لإنشاء قائمة انتظار ذات أولوية ، قد تحتاج إلى وضع العناصر في وسط القائمة.
- ليس لديك فكرة عن المدة التي ستستغرقها القائمة. إذا زاد حجم المصفوفة ، يجب إعادة التصريح عن الذاكرة وتكرارها ، تمامًا كما هو الحال مع المصفوفات البسيطة.
7. ما الذي يميز المصفوفة المفهرسة عن المصفوفة الترابطية؟
يتم سرد الفروق الأولية بين المصفوفات الترابطية والمفهرسة في الجدول التالي.
- يتم استخدام زوج من المفاتيح والقيمة في تنسيق نصي أو رقمي لفرز مصفوفة ترابطية. جميع مفاتيح المصفوفة المفهرسة رقمية ، وكل مفتاح متصل بقيمة مميزة.
- في المصفوفة الترابطية ، قد يكون المفتاح سلسلة. مصفوفة مفهرسة بمفاتيح أعداد صحيحة تبدأ من 0.
- يحاكي الجدول المكون من عمودين سلوك المصفوفة الترابطية. تشبه المصفوفات المفهرسة الجدول أحادي العمود.
- الخرائط هي نوع مصفوفة ترابطية. مصفوفة الفهرس ليست خريطة.
8. ما هي المزايا التي يتمتع بها Heap على المصفوفات التي تم فرزها؟
تعد الكفاءة الزمنية لاستخدام Heap over Sorted Arrays هي الميزة الرئيسية. بينما تكون عمليات الكومة أسرع ، يتطلب فرز المصفوفة وقتًا طويلاً. يمكن أن تكتشف الكومة أصغر عنصر بسرعة أكبر بكثير من إمكانية فرز المصفوفة.
يمكن ترتيب مجموعة معينة من الأرقام بإحدى طريقتين باستخدام المصفوفات المرتبة. من ناحية أخرى ، بالنسبة لمجموعة معينة من الأرقام ، قد يكون هناك أكثر من كومة محتملة واحدة.
9. هل يمكننا تحديد حجم المصفوفة لتكون سالبة؟
لا ، لا يمكننا تحديد عدد صحيح سالب ليكون بحجم مصفوفة. لن يكون هناك خطأ في وقت الترجمة إذا أعلنا. ومع ذلك ، في وقت التشغيل ، سنواجه NegativeArraySizeException.
10. كيف يمكنك تحديد مكان العدد الصحيح المفقود في مصفوفة مكونة من 1 إلى 100 عنصر؟
يمكن حساب إجمالي السلسلة بتطبيق الوظيفة التالية: n (n + 1) / 2
فقط إذا كانت المصفوفة لا تحتوي على أي تكرارات أو بها أكثر من عدد صحيح مفقود ، فستعمل هذه الوظيفة. سواء كانت المصفوفة تحتوي على عناصر مكررة ، يمكنك فرز المصفوفة لمعرفة ما إذا كان هناك أي عناصر متكافئة.
11. كيف تجد فهرس عنصر في المصفوفة؟
يمكن اكتشاف فهرس عنصر ما عبر بحث خطي أو ثنائي. حتى يتم تحديد تطابق العنصر المطلوب ، تدور وظيفة البحث الخطي فوق كل عنصر في المصفوفة. تقوم بإرجاع الفهرس بمجرد تحديد موقع العنصر المطابق. وبالتالي ، فإن التعقيد الزمني للبحث الخطي هو O. (n). يمكن لكل من المصفوفة التي تم فرزها أو التي لم يتم فرزها استخدام البحث الخطي.
باستخدام البحث الثنائي ، الذي يقسم المصفوفة باستمرار إلى نصفين حتى يتطابق متوسط الفاصل الزمني مع العنصر المطلوب ويوفر الفهرس ، يمكنك الحصول على فهرس العنصر إذا تم فرز المصفوفة. وبالتالي ، فإن التعقيد الزمني للبحث الثنائي هو O. (log n).
12. كيف يمكنك التخلص من عنصر معين من المصفوفة؟
نظرًا لأنه لا يمكنك ببساطة حذف العناصر من المصفوفة الأصلية نظرًا لأنها مجموعات ثابتة ذات حجم محدد ، فإن القائم بإجراء المقابلة يبحث عنك لاقتراح نهج مختلف والتعامل مع المشكلة التي يثيرها السؤال. أفضل مسار للعمل هو إنشاء مصفوفة جديدة لحذف عنصر. يمكنك تكرار العناصر من المصفوفة الأولى في هذه المصفوفة وتضمين العنصر الذي ترغب في حذفه فقط.
تتضمن الإستراتيجية الأخرى إيجاد العنصر الهدف في المصفوفة ثم عكس ترتيب جميع العناصر الموجودة على يمين العنصر الهدف.
13. كيف يمكن التحقق من مساواة المصفوفتين؟
يجب عليك أولاً التحقق من أطوال المصفوفتين المقدمتين. تتم مقارنة العناصر المطابقة لكلا المصفوفتين عندما تتساوى أطوالهما. سيتم اعتبار المصفوفتين متساويتين. إذا كان كل زوج من المكونات في كل مراسلة متساويًا. لا يُنصح بهذا الأسلوب للتحقق من تكافؤ مصفوفتين إذا كانت المصفوفات كبيرة الحجم نظرًا لأن ذلك سيستغرق وقتًا طويلاً. يمكنك أيضًا استخدام طريقة equals () المضمنة في فئة Arrays ، ومع ذلك ، إذا طلب منك القائم بإجراء المقابلة مقارنة مصفوفتين دون استخدام الأساليب المضمنة ، فستكون هذه الطريقة مفيدة.
14. عندما نناقش المصفوفات ، ماذا تقصد بالعبارات "البعد" و "المخطوطة"؟
"بُعد" المصفوفة هو عدد الفهارس ، أو الرموز الفرعية ، المطلوبة لتعريف كل عضو على حدة. قد تكون النصوص والأبعاد غير واضحة. البعد هو وصف لنطاق المفاتيح المسموح بها ، بينما الرمز المنخفض هو رقم. هناك شرط واحد فقط مطلوب لكل بُعد مصفوفة.
على سبيل المثال ، المصفوفة arr [10] [5] لها بعدين. مقاسات 10 على واحد و 5 على الآخر. لمعالجة مكوناته ، تحتاج إلى اثنين من الرموز. كلاهما بين 0 و 4 ؛ واحد بين 0 و 9 ، ضمناً.
أسئلة المقابلة الترميز
15. ابحث عن زوج في مصفوفة لها المجموع المحدد
على سبيل المثال،
الإدخال:
- الأعداد = [8 ، 7 ، 2 ، 5 ، 3 ، 1]
- الهدف = 10
الإخراج:
- تم العثور على زوج (8 ، 2)
- Or
- تم العثور على زوج (7 ، 3)
الإدخال:
- الأعداد = [5 ، 2 ، 6 ، 8 ، 1 ، 9]
- الهدف = 12
الإخراج:
- لم يتم العثور على الزوج
16. الفرز الثنائي مع الزمن الخطي
فرز مجموعة ثنائية في وقت خطي وفي منطقة ثابتة. يجب أن يعرض الإخراج جميع الأصفار أولاً ، ثم كل الأصفار.
على سبيل المثال،
- الإدخال: {1 ، 0 ، 1 ، 0 ، 1 ، 0 ، 0 ، 1}
- الإخراج: {0، 0، 0، 0، 1، 1، 1، 1}
تتمثل الطريقة المباشرة في حساب العدد الإجمالي للمصفوفة من 0s ، على سبيل المثال k ، ثم ملء مؤشرات k الأولى في المصفوفة بـ 0s والمؤشرات المتبقية بـ 1. كبديل ، يمكننا حساب عدد 1s الإجمالي في المصفوفة k ، املأ آخر مؤشرات k في المصفوفة بالرقم 1 ، واترك باقي المؤشرات مملوءة بصفر.
النهج المعطى له تعقيد زمني O (n) ولا يستخدم أي تخزين إضافي ، حيث n هو حجم المدخلات.
17. أوجد أكبر حاصل ضرب ثنائي في المصفوفة.
أوجد أكبر حاصل ضرب عددين في مصفوفة أعداد صحيحة.
فكر في المصفوفة 10 3 5 6 2 كمثال. الزوج (-10 ، -3) أو (5 ، 6) هو أعلى منتج.
التفكير في كل تركيبة عنصر ومعرفة منتجها هو نهج أحمق. إذا كان منتج الزوج الحالي أكبر من الحد الأقصى للمنتج الذي تم الحصول عليه حتى الآن ، فقم بتحديث الحد الأقصى للمنتج. اطبع مكونات المنتج النهائي أخيرًا.
الحل أعلاه ، حيث n هو مقدار الإدخال ، له تعقيد زمني لـ O (n2) ولا يشغل مساحة إضافية.
18. كيفية إزاحة كل أصفار المصفوفة حتى النهاية
انقل كل الأصفار في مصفوفة عدد صحيح إلى النهاية. يجب أن تتجنب الإجابة استخدام مسافة ثابتة وأن تحافظ على الترتيب النسبي لمكونات المصفوفة.
المدخلات: {1,2,3,0,8,0,4,7،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}
سيكون الإخراج {1,2,3,8,4,7,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}
ضع العنصر في الموضع المتاح التالي في المصفوفة إذا لم يكن العنصر الحالي صفراً. املأ جميع الفهارس المتبقية بالرقم 0 بمجرد أن تتم معالجة جميع عناصر المصفوفة.
الحل السابق له تعقيد زمني O (n) ، حيث n هو حجم المدخلات.
19. كيفية فرز مصفوفة بإدخالين يتم تبديلهما في عملية واحدة.
قم بفرز مصفوفة في الوقت الخطي بإعطاء عنصرين مبادلين ومصفوفة بها كل عناصرها مرتبة بترتيب تصاعدي. افترض أن المصفوفة لا تحتوي على تكرارات.
المدخلات: = [1,9,3,4,7,2،9,3,7,2,1,4،2,4,1,7,3,9،XNUMX،XNUMX،XNUMX] أو [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] أو [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX]
الإخراج: = [1,2,3,4,7,9،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX]
بداية من العنصر الثاني في المصفوفة ، الهدف هو مقارنة كل عنصر بسابقه. يتم تخزين موضع النزاع عن طريق أخذ مؤشرين ، x ، و y.
قم بتحديث x إلى فهرس العنصر السابق و y إلى فهرس العنصر الحالي إذا كان الأول أكبر من الأخير. قم بتحديث y إلى فهرس العنصر الحالي إذا تبين أن العنصر السابق أكبر من العنصر الحالي.
أخيرًا ، بدّل العناصر في الفهرين x و y بمجرد أن ننتهي من معالجة كل زوج متجاور من العناصر.
نظرًا لحقيقة أن الطريقة المذكورة أعلاه لا تؤدي إلا مسحًا واحدًا لمصفوفة الإدخال بالحجم n ، فإن تعقيدها الزمني هو O (n). لا توجد مساحة إضافية ضرورية للحل.
20. كيفية دمج مصفوفتين تم فرزهما في المكان.
قم بدمج عناصر المصفوفات X [] و Y [] - مصفوفتان مصنفتان بحجم m و n لكل منهما - عن طريق الاحتفاظ بالترتيب الفرز ، أي بملء X [] بأول m أصغر العناصر وملء Y [] ب العناصر المتبقية.
إذا كان أحد العناصر في المصفوفة X [] موجودًا بالفعل في الموضع الصحيح (أي ، العنصر الأصغر بين العناصر المتبقية) ، فتجاهله ؛ خلاف ذلك ، استبدله بأصغر عنصر ، والذي يحدث أيضًا ليكون العضو الأول في Y []. للاحتفاظ بالترتيب الذي تم فرزه بعد التبديل ، انقل العنصر (الآن عند Y [0]) إلى موقعه الصحيح في Y [].
حجم المصفوفة الأولى هو m وحجم المصفوفة الثانية n ، وتعقيد الوقت هو O (mn).
21. كيفية إعادة ترتيب مجموعة من العناصر بالتناوب بين المواقع العالية والمنخفضة؟
أعد ترتيب مصفوفة عدد صحيح بحيث يكون كل عضو تالٍ أكبر من العناصر السابقة والتالية. افترض أن المصفوفة لا تتضمن أي عناصر مكررة.
لا يعد فرز المصفوفة أو استخدام مساحة إضافية ضروريًا لنهج فعال. الخطة ، في البداية ، هي العضو الثاني في المصفوفة وترتفع بمقدار اثنين لكل تكرار حلقي.
قم بتبديل المكونات إذا تجاوز العنصر الأخير العنصر الأول. على نفس المنوال ، قم بتبديل كلا العنصرين إذا كان العنصر التالي أكبر من العنصر الحالي. سنحصل على المصفوفة المطلوبة التي تتوافق مع القيود المحددة في نهاية الحلقة.
22. كيف نستبدل كل عنصر من عناصر المصفوفة بدون استخدام عامل القسمة بحاصل ضرب كل عنصر في المصفوفة؟
بدون استخدام عامل القسمة ، استبدل كل عنصر في مصفوفة عدد صحيح بحاصل ضرب كل العناصر الأخرى.
في الوقت الخطي والمساحة الثابتة ، يمكننا استخدام العودية لمعالجة هذه المشكلة. الفكرة هي الحساب المتكرر لمنتجات كل عنصر في المصفوفة اليمنى وتمرير منتج الطبقة الفرعية اليسرى كمعلمات دالة.
التعقيد الزمني هو O (n).
23. أوجد أغرب عنصر في المصفوفة في الوقت اللوغاريتمي
بالنظر إلى مصفوفة أعداد صحيحة يكون فيها لكل عضو ما عدا عضوًا واحدًا أعدادًا زوجية من التكرارات ، تكمن المشكلة في تحديد عدد مرات ظهور هذا العنصر الواحد. ابحث عن العنصر الفردي في الوقت اللوغاريتمي والفضاء الثابت إذا حدثت نفس العناصر في أزواج في المصفوفة ولا يمكن أبدًا أن يكون هناك أكثر من مثيلين لعنصر معين في صف واحد.
تمكننا عملية XOR من حل هذه المشكلة في الوقت الخطي. الهدف هو XOR كل عنصر في المصفوفة. تبقى فقط العناصر الفردية التي تحدث بعد أن تلغي العناصر المتساوية بعضها البعض.
يمكن حتى حل هذه المشكلة في وقت O (log (n)).
24. كيف تحصل على العنصر الأكبر التالي لكل عنصر في مصفوفة دائرية؟
يجب تحديد موقع العنصر الأكبر التالي لكل عنصر في مصفوفة عدد صحيح دائري. أول عدد صحيح أكبر بعد العنصر x في المصفوفة هو العنصر الأكبر التالي لهذا العنصر.
من اليمين إلى اليسار ، قد نعمل على عناصر المصفوفة. الهدف هو التكرار لكل عنصر x حتى يصبح المكدس فارغًا أو يكون لدينا عنصر أعلى فوقه. اضبط العنصر الأكبر التالي لـ x ليظهر أعلى المكدس عندما يحدث.
25. البحث عن عدد الانعكاس المصفوفة؟
أوجد العدد الإجمالي لانعكاسات المصفوفة. يُشار إلى الزوج I j) على أنه انعكاس لمصفوفة A إذا كنت j) و (A [i]> A [j]). يجب أن نحسب كل زوج من هؤلاء في المصفوفة.
يعد حساب جميع أعضاء المصفوفة الأقل منها إلى اليمين وإضافة النتيجة إلى الإخراج طريقة مباشرة.
هذا الحل له تعقيد O (n2) ، حيث n هو حجم المدخلات.
26. ما هي مشكلة محاصرة مياه الأمطار؟
يُعرف العثور على أكبر قدر من المياه التي يمكن احتجازها في مجموعة معينة من القضبان بعرض وحدة واحدة بمسألة "سقوط الأمطار".
الهدف هو تحديد أعلى شريط يمكن وضعه على يسار ويمين كل شريط. الحد الأدنى للأشرطة الأمامية إلى اليسار واليمين ، مطروحًا منه ارتفاع العمود الحالي ، هو كمية المياه المخزنة أعلى كل شريط.
وفي الختام
بالمقارنة مع موضوعات بنية البيانات الأخرى ، فإن المصفوفات أبسط. من أجل الحصول على أسئلة مقابلة مصفوفة ، يجب أن يكون لديك فهم أساسي للمصفوفات.
يجب عليك مراجعة أسس المصفوفات على نطاق واسع ، بما في ذلك عمليات المصفوفة (من إعلان / إنشاء مصفوفة إلى الوصول إلى / تعديل عناصر المصفوفة) ، بالإضافة إلى مفاهيم البرمجة مثل الحلقات والتكرار والعوامل الأساسية من أجل الإجابة بنجاح على أسئلة مقابلة الصفيف. تعرف على المشكلة تمامًا.
يجب أن تطلب توضيحًا إذا كان لديك أي استفسارات. فكر في تقسيم المشكلة إلى أجزاء يسهل التعامل معها. تأكد من وضع الخوارزمية في الاعتبار قبل البدء في البرمجة ؛ اكتبها أو تصورها في مخطط انسيابي. ثم ابدأ في كتابة الكود.
اترك تعليق