أهم هياكل البيانات التي يجب أن تعرفها عن مقابلتك البرمجية

كتب نيكلاوس ويرث ، عالم الكمبيوتر السويسري ، كتابًا في عام 1976 بعنوان الخوارزميات + هياكل البيانات = البرامج .

بعد أكثر من 40 عامًا ، تظل هذه الهوية صالحة. هذا هو السبب في أن الباحثين عن عمل الذين يريدون أن يصبحوا مبرمجين يجب أن يثبتوا أنهم يعرفون هياكل البيانات وأنهم قادرون على تطبيقها.

يحتاج المرشح في جميع المهام تقريبًا إلى فهم عميق لهياكل البيانات. في الوقت نفسه ، ليس من المهم للغاية سواء كنت خريجًا (تخرج من جامعة أو دورات برمجة) ، أو لديك عشرات السنين من الخبرة خلفك.

في بعض الأحيان في أسئلة المقابلة ، يتم ذكر بنية بيانات واحدة أو أخرى بشكل مباشر ، على سبيل المثال ، "إعطاء شجرة ثنائية". في حالات أخرى ، تتم صياغة المهمة بطريقة أكثر حجابًا ، على سبيل المثال ، "تحتاج إلى تتبع عدد الكتب التي لدينا من كل مؤلف".

دراسة هياكل البيانات هي عمل لا غنى عنه ، حتى إذا كنت تحاول فقط تحسين مهنيًا في وظيفتك الحالية. لنبدأ بالأساسيات.

ترجم إلى Alconost

ما هو هيكل البيانات؟

باختصار ، بنية البيانات هي حاوية يتم فيها ترتيب المعلومات بطريقة مميزة. بفضل هذا "التخطيط" ، ستكون بنية البيانات فعالة في بعض العمليات وغير فعالة في عمليات أخرى. هدفنا هو فهم هياكل البيانات بطريقة يمكنك من بينها الاختيار الأنسب منها لحل المشكلة المحددة التي تواجهها.

لماذا نحتاج إلى هياكل البيانات؟

نظرًا لأن هياكل البيانات تُستخدم لتخزين المعلومات بطريقة منظمة ، والبيانات هي أهم ظاهرة في علوم الكمبيوتر ، فإن القيمة الحقيقية لهياكل البيانات واضحة.

لا يهم نوع المهمة التي تقوم بحلها ، بطريقة أو بأخرى ، سيكون عليك التعامل مع البيانات ، سواء كانت راتب الموظف أو أسعار الأسهم أو قائمة المنتجات للذهاب إلى المتجر أو دليل الهاتف العادي.

اعتمادًا على السيناريو المحدد ، يجب تخزين البيانات بتنسيق مناسب. لدينا تحت تصرفنا عدد من هياكل البيانات التي تزودنا بمثل هذه التنسيقات المختلفة.

هياكل البيانات المشتركة

أولاً ، دعنا نسرد هياكل البيانات الأكثر شيوعًا ، ثم نحلل كل منها بدوره:

1. المصفوفات
2. الأكوام
3. قوائم الانتظار
4. القوائم المرتبطة
5. الأشجار
6. التهم
7. الأزيز (في الأساس ، هذه أيضًا أشجار ، ولكن يجب اعتبارها منفصلة).
8. جداول التجزئة

المصفوفات

الصفيف هو أبسط هيكل للبيانات وأكثرها شيوعًا. يتم اشتقاق تراكيب البيانات الأخرى ، مثل المداخن وقوائم الانتظار ، من المصفوفات.

يظهر هنا صفيف بسيط من الحجم 4 يحتوي على عناصر (1 و 2 و 3 و 4).

يتم تعيين قيمة رقمية موجبة لكل عنصر بيانات يسمى الفهرس ويقابل موضع هذا العنصر في الصفيف. في معظم لغات البرمجة ، يتم ترقيم العناصر في الصفيف من 0.

هناك نوعان من المصفوفات:

• أحادي البعد (كما هو موضح أعلاه)
• متعدد الأبعاد (المصفوفات التي يتم فيها تضمين المصفوفات الأخرى)

أبسط عمليات الصفيف

• إدراج - إدراج عنصر في موضع بفهرس معين
• Get - إرجاع عنصر يشغل موضعًا بمؤشر معين
• حذف - حذف العنصر باستخدام الفهرس المحدد
• الحجم - احصل على العدد الإجمالي للعناصر في المصفوفة

مقابلة أسئلة وأجوبة

• ابحث عن عنصر الصفيف الثاني الأدنى
• ابحث عن أعداد صحيحة غير متكررة في صفيف
• ادمج صفيفين مفروزين
• إعادة ترتيب القيم الموجبة والسالبة في صفيف

الأكوام

يعرف الجميع خيار "إلغاء" الشهير ، والذي يتوفر في جميع التطبيقات تقريبًا. هل تساءلت يومًا كيف تعمل؟ المعنى هذا: يتم حفظ الحالة السابقة لعملك في البرنامج (عدد الحالات المحفوظة محدود) ، وهي موجودة في الذاكرة بهذا الترتيب: آخر عنصر محفوظ يأتي أولاً. المصفوفات وحدها لا تستطيع حل هذه المشكلة. هذا هو المكان الذي يكون فيه المكدس مفيدًا.

يمكن مقارنة المكدس بمجموعة كبيرة من الكتب. إذا كنت بحاجة إلى كتاب مستلقٍ بالقرب من مركز المكدس ، فسيتعين عليك أولاً إزالة جميع الكتب أعلاه. هذه هي الطريقة التي يعمل بها مبدأ LIFO (آخر مرة يأتي أولاً).

يبدو ككومة تحتوي على ثلاثة عناصر بيانات (1 و 2 و 3) ، حيث يوجد 3 في الأعلى - وبالتالي ستتم إزالته أولاً:

أبسط عمليات المكدس:

• دفع - لدفع عنصر على المكدس في الأعلى
• Pop - إرجاع العنصر العلوي بعد إزالته من المكدس
• isEmpty - إرجاع صحيح إذا كان المكدس فارغًا
• أعلى - إرجاع العنصر العلوي بدون إزالته من المكدس

مقابلة أسئلة وأجوبة حول المكدس

• حساب تعبير postfix باستخدام المكدس
• فرز القيم على المكدس
• تحقق من الأقواس المتوازنة في التعبير

قوائم الانتظار

قائمة الانتظار ، مثل المكدس ، هي بنية بيانات خطية يتم فيها تخزين العناصر بترتيب تسلسلي. الفرق الوحيد المهم بين المكدس وقائمة الانتظار هو أنه في قائمة الانتظار ، بدلاً من LIFO ، ينطبق مبدأ FIFO (يأتي أولاً ، يذهب أولاً).

مثال واقعي مثالي لقائمة انتظار - هذا هو قائمة انتظار العملاء في مكتب التذاكر. مشتري جديد في ذيل الخط ، وليس في البداية. الشخص الموجود في قائمة الانتظار أولاً سيكون أول من يشتري تذكرة ويتركها أولاً.

فيما يلي صورة لقائمة انتظار بأربعة عناصر بيانات (1 و 2 و 3 و 4) ، حيث يذهب 1 أولاً ويترك قائمة الانتظار أولاً:

عمليات طابور بسيطة

• Enqueue () - إضافة عنصر إلى نهاية قائمة الانتظار
• Dequeue () - إزالة عنصر من مقدمة قائمة الانتظار
• isEmpty () - إرجاع صحيح إذا كانت قائمة الانتظار فارغة
• أعلى () - إرجاع العنصر الأول في قائمة الانتظار

مقابلة أسئلة وأجوبة

• تنفيذ مكدس باستخدام قائمة انتظار
• دفع أول عناصر k في قائمة الانتظار
• إنشاء أرقام ثنائية من 1 إلى n باستخدام قائمة انتظار

قائمة مرتبطة

القائمة المرتبطة هي بنية بيانات خطية مهمة أخرى تشبه للوهلة الأولى صفيفًا. ومع ذلك ، تختلف القائمة المرتبطة عن مصفوفة في تخصيص الذاكرة ، والبنية الداخلية ، وكيفية إجراء عمليات الإدراج والحذف الأساسية فيها.

تشبه القائمة المرتبطة سلسلة من العقد ، يحتوي كل منها على معلومات: على سبيل المثال ، البيانات ومؤشر للعقدة التالية في السلسلة. يوجد مؤشر رأس يتوافق مع العنصر الأول في قائمة مرتبطة ، وإذا كانت القائمة فارغة ، فسيتم توجيهها ببساطة إلى null (لا شيء).

يتم استخدام القوائم المرتبطة وأنظمة الملفات وجداول التجزئة وقوائم المجاورة.

هذه هي الطريقة التي يمكنك من خلالها تصور الهيكل الداخلي لقائمة مرتبطة:


هناك أنواع من القوائم المرتبطة:

• قائمة ارتباط واحد (أحادي الاتجاه)
• قائمة مرتبطة مزدوجة (ثنائية الاتجاه)

أبسط العمليات مع القوائم المرتبطة هي:

• InsertAtEnd - إدراج العنصر المحدد في نهاية القائمة المرتبطة.
• InsertAtHead - إدراج العنصر المحدد في بداية القائمة المرتبطة (من الرأس)
• حذف - حذف العنصر المحدد من القائمة المرتبطة.
• DeleteAtHead - حذف العنصر الأول في قائمة مرتبطة.
• بحث - إرجاع العنصر المحدد من القائمة المرتبطة.
• isEmpty - إرجاع صحيح إذا كانت القائمة المرتبطة فارغة

مقابلة أسئلة وأجوبة:

• ادفع قائمة مرتبطة
• ابحث عن الحلقة في القائمة المرتبطة
• قم بإعادة العقدة Nth من أعلى القائمة المرتبطة
• قم بإزالة القيم المكررة من القائمة المرتبطة

التهم

الرسم البياني عبارة عن مجموعة من العقد المتصلة ببعضها البعض في شكل شبكة. تسمى العقد أيضًا القمم. يُدعى الزوج (س ، ص) بالحافة ، مما يعني أن الرأس x متصل بالقمة y . يمكن أن يكون للحافة وزن / تكلفة - وهو مؤشر يصف مدى تكلفة الانتقال من القمة x إلى القمة y.


أنواع الرسوم البيانية:

• رسم بياني غير موجه
• رسم بياني موجه

في لغة البرمجة ، يمكن أن تكون الرسوم البيانية من نوعين:

• مصفوفة المجاورة
• قائمة المجاورة

خوارزميات اجتياز الرسم البياني الشائعة:

• بحث واسع
• بحث العمق

مقابلة أسئلة وأجوبة:

• تنفيذ عمليات بحث واسعة وعميقة
• تحقق مما إذا كان الرسم البياني شجرة أم لا
• عد عدد الحواف في الرسم البياني
• ابحث عن أقصر مسار بين القمتين

الأشجار

الشجرة هي بنية بيانات هرمية تتكون من القمم (العقد) والحواف التي تربطها. تتشابه الأشجار مع الرسوم البيانية ، ومع ذلك ، فإن الفرق الرئيسي بين الشجرة والرسم البياني هو: لا توجد دورات في الشجرة.

تُستخدم الأشجار على نطاق واسع في مجال الذكاء الاصطناعي والخوارزميات المعقدة ، وتعمل كمستودع فعال للمعلومات في حل المشكلات.

في ما يلي مخطط شجري بسيط ومصطلحات أساسية مرتبطة ببنية البيانات هذه:


توجد الأنواع التالية من الأشجار:

• N- شجرة
• شجرة متوازنة
• شجرة ثنائية
• شجرة البحث الثنائية
• شجرة AVL
• خشب الأبنوس الأحمر
• 2-3 شجرة

من الأشجار المذكورة أعلاه ، غالبًا ما يتم استخدام الشجرة الثنائية وشجرة البحث الثنائية.

أسئلة المقابلة المتكررة حول الأشجار:

أوجد ارتفاع شجرة ثنائية
أوجد القيمة القصوى kth في شجرة البحث الثنائية
البحث عن العقد الموجودة "k" من الجذر
ابحث عن أسلاف عقدة معينة في شجرة ثنائية

البورون

البورون ، والمشار إليها أيضًا باسم "شجرة البادئة" ، هي بنية بيانات تشبه الشجرة وهي فعالة بشكل خاص في حل مشاكل السلسلة. يوفر استردادًا سريعًا للبيانات وغالبًا ما يُستخدم للبحث عن الكلمات في القاموس ، وإكمال البحث ، وحتى توجيه IP.

هذه هي الطريقة التي يتم بها تخزين الكلمات الثلاث "أعلى" (أعلى) ، "وبالتالي" (وبالتالي) ، و "هم" (لهم) في الغابة:


يتم ترتيب الكلمات من أعلى إلى أسفل ، وتكتمل العقد الخضراء "p" و "s" و "r" ، على التوالي ، الكلمات "top" و "وهكذا" و "بهم".

أسئلة المقابلة المتكررة حول الأزيز:

• احسب إجمالي عدد الكلمات المخزنة في غابة الصنوبر
  
• عرض جميع الكلمات المخزنة في الغابة.
  
• فرز عناصر الصفيف باستخدام البورون
  
• بناء كلمات المفردات باستخدام البورون
  
• إنشاء قاموس T9
  

طاولة تجزئة

التجزئة هي عملية تُستخدم لتعريف الكائنات بشكل فريد وتخزين كل كائن بواسطة فهرس محسوب مسبقًا يسمى "مفتاحه". وبالتالي ، يتم تخزين الكائن كقيمة رئيسية ، وتسمى مجموعة من هذه الكائنات القاموس. يمكن البحث عن كل كائن بمفتاحه. هناك هياكل بيانات مختلفة مبنية على مبدأ التجزئة ، ولكن غالبًا ما يتم استخدام جدول التجزئة من هذه الهياكل.

كقاعدة ، يتم تنفيذ جداول التجزئة باستخدام المصفوفات.

يعتمد أداء بنية البيانات المجزأة على العوامل الثلاثة التالية:

• وظيفة التجزئة
• تجزئة حجم الجدول
• طريقة معالجة التصادم

يوضح ما يلي كيفية تعيين التجزئة لصفيف. يتم حساب فهرس هذا الصفيف باستخدام دالة التجزئة.

مقابلة الأسئلة المتكررة حول التجزئة:

• ابحث عن أزواج متماثلة في مصفوفة
• تتبع المسار الكامل
• ابحث عما إذا كان الصفيف مجموعة فرعية من صفيف آخر
• تحقق مما إذا كانت الصفائف مفككة

يصف ما سبق هياكل البيانات الثمانية الأكثر أهمية التي تحتاج إلى معرفتها بالتأكيد قبل الانتقال إلى مقابلة البرمجة.

حظا سعيدا والتعلم المثير للاهتمام! :)

عن المترجم

تمت ترجمة المقال بواسطة Alconost.

تقوم Alconost بتوطين الألعاب والتطبيقات والمواقع بـ 68 لغة. مترجمون لغتهم الأم ، اختبار لغوي ، منصة سحابية بواجهة برمجة تطبيقات ، تعريب مستمر ، مدراء مشاريع 24/7 ، أي تنسيق لموارد السلسلة.

ننشئ أيضًا مقاطع فيديو إعلانية وتدريبية - للمواقع التي تبيع ، والصور ، والإعلانات ، والتدريب ، والتشويش ، والشرح ، والمقطورات لـ Google Play و App Store.

مزيد من التفاصيل