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

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

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

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

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

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

ما هي بنية البيانات؟

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

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

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

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

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

هياكل البيانات شائعة الاستخدام

لنقم أولاً بإدراج هياكل البيانات الأكثر استخدامًا ، ثم سنغطيها واحدة تلو الأخرى:

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

المصفوفات

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

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

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

فيما يلي نوعان من المصفوفات:

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

العمليات الأساسية على المصفوفات

  • إدراج - إدراج عنصر في فهرس معين
  • Get - إرجاع العنصر في فهرس معين
  • حذف - يحذف عنصرًا من فهرس معين
  • الحجم - الحصول على العدد الإجمالي للعناصر في المصفوفة

الأسئلة المتداولة حول مقابلة Array

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

الأكوام

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

قد يكون أحد الأمثلة الواقعية على Stack عبارة عن كومة من الكتب مرتبة بترتيب رأسي. من أجل الحصول على الكتاب الموجود في مكان ما في المنتصف ، ستحتاج إلى إزالة جميع الكتب الموضوعة فوقه. هذه هي الطريقة التي تعمل بها طريقة LIFO (Last In First Out).

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

العمليات الأساسية للمكدس:

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

أسئلة مقابلة Stack المتداولة

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

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

على غرار Stack ، تعد Queue بنية بيانات خطية أخرى تخزن العنصر بطريقة متسلسلة. الاختلاف الوحيد المهم بين Stack و Queue هو أنه بدلاً من استخدام طريقة LIFO ، تطبق قائمة الانتظار FIFOالطريقة ، وهي اختصار لـ First in First Out.

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

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

العمليات الأساسية لقائمة الانتظار

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

أسئلة المقابلة الشائعة في قائمة الانتظار

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

قائمة مرتبطة

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

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

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

فيما يلي تمثيل مرئي للبنية الداخلية لقائمة مرتبطة:

فيما يلي أنواع القوائم المرتبطة:

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

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

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

أسئلة المقابلة ذات القائمة المرتبطة المتداولة

  • عكس قائمة مرتبطة
  • كشف حلقة في قائمة مرتبطة
  • إرجاع العقدة Nth من النهاية في قائمة مرتبطة
  • إزالة التكرارات من قائمة مرتبطة

الرسوم البيانية

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

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

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

في لغة البرمجة ، يمكن تمثيل الرسوم البيانية باستخدام شكلين:

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

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

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

الأسئلة الشائعة في مقابلة الرسم البياني

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

الأشجار

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

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

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

فيما يلي أنواع الأشجار:

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

من بين ما سبق ، فإن Binary Tree و Binary Search Tree هما أكثر الأشجار استخدامًا.

أسئلة مقابلة Tree الشائعة

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

تري

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

فيما يلي توضيح لكيفية تخزين الكلمات الثلاث "أعلى" و "بالتالي" و "هم" في Trie:

يتم تخزين الكلمات من الأعلى إلى الأسفل بالطريقة حيث تشير العقد الملونة باللون الأخضر "p" و "s" و "r" إلى نهاية "top" و "so" و "their" على التوالي.

أسئلة مقابلة Trie الشائعة:

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

جدول تجزئة

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

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

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

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

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

الأسئلة المتداولة حول Hashing للمقابلة

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

ما سبق هو أهم ثمانية هياكل بيانات يجب أن تعرفها بالتأكيد قبل الدخول في مقابلة الترميز.

إذا كنت تبحث عن موارد حول هياكل البيانات لمقابلات التشفير ، فابحث عن الدورات التدريبية التفاعلية والقائمة على التحدي: هياكل البيانات لمقابلات التشفير (Python أو Java أو JavaScript).

لمزيد من الأسئلة المتقدمة ، انظر إلى Coderust 3.0: تحضير أسرع للمقابلة مع التحديات التفاعلية والتصورات.

إذا كنت تستعد لإجراء مقابلات مع هندسة البرمجيات ، فإليك خارطة طريق شاملة للتحضير لمقابلات البرمجة.

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