استكشاف الأسئلة والأجوبة من مقابلة عمل لوظيفة مطور Java. الجزء 9

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

المجموعات

84. أخبرنا عن التكرارات وكيفية استخدامها

تعد المجموعات موضوعًا مفضلاً في أي مقابلة لمطوري Java. عند الإجابة على أسئلة حول التسلسل الهرمي للمجموعة، غالبًا ما يقول المرشحون إنه يبدأ بواجهة المجموعة . ولكن هذا ليس كذلك. هناك واجهة أخرى بمستوى أعلى: Iterable . تتكون هذه الواجهة من طريقة iterator() ، والتي تتيح لك الوصول إلى كائن Iterator للمجموعة الحالية. وما هو كائن Iterator هذا بالضبط ؟ يوفر كائن Iterator القدرة على التنقل عبر المجموعة والتكرار على عناصرها، ولا يحتاج المستخدم إلى معرفة تفاصيل التنفيذ المحددة للمجموعة. بمعنى آخر، هو نوع من المؤشر إلى عناصر المجموعة، كما لو كان يلقي نظرة خاطفة على أحدها. يحتوي المكرر على طرق مثل:

• hasNext() — يُرجع صحيحًا إذا كان التكرار يحتوي على عنصر آخر (تتيح لك هذه الطريقة معرفة متى وصلت إلى نهاية المجموعة)؛

• next() — يُرجع العنصر التالي في التكرار. إذا لم يكن هناك واحد، فسيتم طرح NoSuchElementException . وهذا يعني أنه قبل استخدام هذه الطريقة، من الأفضل استخدام طريقة hasNext() للتأكد من وجود العنصر التالي؛

• إزالة () - إزالة العنصر الأخير الذي تم استلامه من المجموعة باستخدام الطريقة التالية () . إذا لم يتم استدعاء next() مطلقًا، فإن استدعاء إزالة() سيؤدي إلى طرح IllegalStateException ؛

• forEachRemaining(<Consumer>) — ينفذ الإجراء الذي تم تمريره على كل عنصر من عناصر المجموعة (ظهرت هذه الطريقة في Java 8).

فيما يلي مثال صغير على التكرار عبر قائمة وإزالة جميع عناصرها باستخدام طرق التكرار المختلفة التي نظرنا إليها:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

ستعرض وحدة التحكم ما يلي: وهذا يعني أنه تمت إزالة العناصر بنجاح. بمجرد حصولك على مُكرِّر، يمكنك استخدام طريقة لعرض جميع العناصر على الشاشة:

iterator.forEachRemaining(x -> System.out.print(x));

ولكن بمجرد القيام بذلك، يصبح المكرِّر غير مناسب لمزيد من الاستخدام: لقد اجتاز القائمة بأكملها، ولا يملك المكرِّر العادي طرقًا للتكرار للخلف. وهذا يجعلنا ندخل في مناقشة لطيفة حول LinkedList ، على وجه التحديد، أسلوب listIterator() الخاص به ، والذي يُرجع نوعًا مُحسّنًا من المكرر: ListIterator . بالإضافة إلى أساليب المكرر العادي (القياسي)، فإن هذا النوع يحتوي على ما يلي:

• add(<Element>) — يضيف عنصرًا جديدًا إلى القائمة؛

• hasPrevious() — يُرجع صحيحًا إذا كان هناك عنصر يقع قبل العنصر التالي (إذا كان هناك عنصر سابق)؛

• nextIndex() — يُرجع فهرس العنصر التالي؛

• السابق () - إرجاع العنصر السابق (العنصر الذي يسبق العنصر التالي)؛

• PreviousIndex يُرجع فهرس العنصر السابق.

• set(<Element>) - يستبدل العنصر الأخير الذي تم إرجاعه بواسطة next() أو Previous() .

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

85. ما هو التسلسل الهرمي للمجموعات الموجود في Java Collection Framework؟

هناك نوعان من التسلسلات الهرمية للمجموعات في Java. التسلسل الهرمي الأول هو التسلسل الهرمي للمجموعات، والذي يحتوي على البنية التالية: وينقسم إلى المجموعات الفرعية التالية:

• المجموعة عبارة عن واجهة تصف مجموعة، وهي بنية بيانات تحتوي على عناصر فريدة غير مرتبة (غير متكررة). تحتوي هذه الواجهة على بعض التطبيقات القياسية: TreeSet و HashSet و LinkedHashSet .

• القائمة عبارة عن واجهة تصف بنية البيانات التي تخزن تسلسلاً مرتبًا للكائنات. يمكن إدراج الكائنات الموجودة في القائمة وإزالتها بواسطة فهرسها في القائمة (مثل المصفوفة، ولكن مع تغيير الحجم الديناميكي). تحتوي هذه الواجهة أيضًا على بعض التطبيقات القياسية: ArrayList و Vector ( مهمل وغير مستخدم فعليًا ) و LinkedList .

• قائمة الانتظار هي واجهة تصف بنية البيانات التي تقوم بتخزين العناصر في قائمة انتظار First In First Out (FIFO) . تحتوي هذه الواجهة على التطبيقات القياسية التالية: LinkedList (هذا صحيح، فهي تنفذ أيضًا قائمة الانتظار ) و PriotityQueue .

التسلسل الهرمي للمجموعة الثانية هو التسلسل الهرمي للخريطة ، والذي يحتوي على البنية التالية: لا يحتوي التسلسل الهرمي للمجموعة هذا على أقسام إلى مجموعات فرعية (نظرًا لأن التسلسل الهرمي للخريطة نفسه عبارة عن مجموعة فرعية مستقلة عن بعضها البعض). تطبيقات الخريطة القياسية هي Hashtable (مهمل) و LinkedHashMap و TreeMap . من الناحية العملية، عندما يسأل الناس عن المجموعات ، فإنهم عادةً ما يقصدون كلا التسلسلين الهرميين.

86. ما هو الهيكل الداخلي لقائمة ArrayList؟

ArrayList يشبه المصفوفة، لكنه يمكن أن يتوسع ديناميكيًا . ماذا يعني ذالك؟ تحت الغطاء، يستخدم ArrayList مصفوفة عادية، أي أنه يخزن عناصره في مصفوفة داخلية حجمها الافتراضي هو 10 خلايا. بمجرد امتلاء المصفوفة الداخلية، يتم إنشاء مصفوفة جديدة. يتم تحديد حجم المصفوفة الجديدة بهذه الصيغة:

<size of the current array> * 3 / 2 + 1

لذلك، إذا كان حجم المصفوفة لدينا هو 10، فسيكون حجم المصفوفة الجديدة: 10 * 3 / 2 + 1 = 16. ثم يتم نسخ جميع القيم من المصفوفة الأصلية (القديمة) إليها باستخدام المصفوفة المضمنة طريقة System.arraycopy() ، ويتم حذف المصفوفة الأصلية. باختصار، هذه هي الطريقة التي تطبق بها ArrayList تغيير الحجم الديناميكي. دعونا نفكر في طرق ArrayList الأكثر شيوعًا : 1. add(<Element>) - يضيف عنصرًا إلى نهاية المصفوفة (في آخر خلية فارغة)، بعد التحقق أولاً مما إذا كانت هناك خلية متاحة في المصفوفة. إذا لم يكن الأمر كذلك، فسيتم إنشاء مصفوفة جديدة، ويتم نسخ العناصر فيها. التعقيد الزمني لهذه العملية هو O(1). توجد طريقة إضافة (<Index>, <Elelement>) مشابهة . فهو يضيف عنصرًا ليس إلى نهاية القائمة (المصفوفة)، بل إلى الخلية المحددة التي يشير إليها الفهرس الذي يأتي كوسيطة. في هذه الحالة، سيختلف التعقيد الزمني حسب المكان الذي تضيف فيه:

• إذا كانت الإضافة قريبة من بداية القائمة، فسيكون التعقيد الزمني قريبًا من O(N)، لأن جميع العناصر الموجودة على يمين العنصر الجديد يجب نقلها خلية واحدة إلى اليمين؛
• إذا تم إدراج العنصر في المنتصف، فسيكون O(N/2)، لأننا نحتاج فقط إلى نقل نصف عناصر القائمة خلية واحدة إلى اليمين.

أي أن التعقيد الزمني لهذه الطريقة يتراوح من O(1) إلى O(N)، اعتمادًا على مكان إدراج العنصر. 2.set (<Index>, <Element>) - يكتب عنصرًا إلى الموضع المحدد في القائمة. إذا كان العنصر موجودًا بالفعل في هذا الموضع، فستقوم الطريقة بالكتابة فوقه. التعقيد الزمني لهذه العملية هو O(1)، لأنها لا تتضمن أي عمليات إزاحة: نحن فقط نستخدم الفهرس لحساب عنوان الخلية في المصفوفة، التي لها تعقيد O(1)، ثم نكتب العنصر الجديد . 3.remove (<index>) — يزيل عنصرًا حسب فهرسه في المصفوفة الداخلية. عند إزالة عنصر غير موجود في نهاية القائمة، يجب نقل جميع العناصر الموجودة على يمين العنصر المحذوف خلية واحدة إلى اليسار لسد الفجوة التي تنتج عن الحذف. وبناءً على ذلك، سيكون التعقيد الزمني هو نفسه بالنسبة إلى add(<Index>, <Element>) عند إضافة عنصر في المنتصف: O(N/2). بعد كل شيء، تحتاج إلى تحويل نصف العناصر خلية واحدة إلى اليسار. وإذا كنا نتحدث عن البداية، إذن O(N). أو إذا كان في النهاية، ثم O(1)، لأنك لا تحتاج إلى نقل أي شيء.

87. ما هو الهيكل الداخلي للقائمة المرتبطة؟

تحتوي قائمة ArrayList على عناصر في المصفوفة الداخلية، لكن القائمة المرتبطة تقوم بتخزينها في قائمة مرتبطة بشكل مزدوج. وهذا يعني أن كل عنصر يحتوي على رابط للعنصر السابق والعنصر التالي . العنصر الأول لا يرتبط بالعنصر السابق (بعد كل شيء، هو الأول). ويعتبر أيضًا رأس القائمة، وكائن LinkedList له إشارة مباشرة إليه. وبالمثل، فإن العنصر الأخير لا يحتوي على العنصر التالي، لأنه هو ذيل القائمة. يشير كائن LinkedList أيضًا إليه مباشرةً . وهذا يعني أن التعقيد الزمني للوصول إلى رأس القائمة أو ذيلها هو O(1). في ArrayList ، إذا كبرت القائمة، فإن المصفوفة الداخلية تنمو. كل شيء هنا أسهل: إضافة مرجع أمر بسيط مثل تغيير بعض الروابط. دعونا نلقي نظرة على بعض طرق LinkedList الأكثر استخدامًا: 1. add(<Element>) — يضيف عنصرًا إلى نهاية القائمة، أي بعد العنصر الأخير (5)، سيتم إضافة رابط للعنصر الجديد كما يلي . سيشير المرجع السابق في العنصر الجديد إلى العنصر (5) الذي يسبقه الآن في القائمة. التعقيد الزمني لهذه العملية هو O(1)، نظرًا لأننا نحتاج فقط إلى الارتباط بالعنصر الأخير، وكما تتذكر، فإن كائن LinkedList له إشارة مباشرة إلى الذيل، والوصول إليه له حد أدنى من التعقيد الزمني الثابت. 2. add(<Index>, <Element>) - يضيف عنصرًا حسب الفهرس. عند إضافة عنصر، على سبيل المثال، في منتصف القائمة، تكرر هذه الطريقة أولاً العناصر من الرأس والذيل (في كلا الاتجاهين) حتى يتم العثور على المكان المطلوب. إذا أضفنا عنصرا بين العنصر الثالث والرابع (في الصورة أعلاه)، فإن الرابط التالي للعنصر الثالث سيشير إلى العنصر الجديد. وسيشير العنصر السابق للعنصر المضاف حديثًا إلى العنصر الثالث. بدوره، سيشير الرابط السابق للعنصر الرابع القديم الآن إلى العنصر الجديد، وسيشير الرابط التالي للعنصر الجديد إلى العنصر الرابع الجديد: يعتمد التعقيد الزمني لهذه الطريقة على فهرس العنصر الجديد:

• إذا كان قريبًا من الرأس أو الذيل، فستقترب العملية من O(1)، لأنه لن يكون من الضروري فعليًا التكرار على العناصر؛
• إذا كان قريبًا من المنتصف، فسيكون لدينا O(N/2)، نظرًا لأن الطريقة ستبحث من الرأس والذيل في نفس الوقت حتى يتم العثور على العنصر المطلوب.

3.set (<Index>, <Element>) - يكتب عنصرًا إلى الموضع المحدد في القائمة. سيتراوح التعقيد الزمني لهذه العملية من O(1) إلى O(N/2)، مرة أخرى اعتمادًا على مدى قرب العنصر الجديد من الرأس أو الذيل أو المنتصف. 4.remove (<index>) — يزيل عنصرًا من القائمة عن طريق جعل العنصر قبل العنصر المحذوف ( السابق ) يشير الآن إلى العنصر بعد العنصر المحذوف ( التالي ). والعكس صحيح، أي أن العنصر بعد العنصر المحذوف يشير الآن إلى العنصر الذي قبل العنصر المحذوف: هذه العملية عكس الإضافة بواسطة الفهرس ( add(<Index>, <Element>) ).

88. ما هو الهيكل الداخلي لـ HashMap؟

قد يكون هذا أحد أسئلة المقابلة الأكثر شيوعًا التي تطرح على مرشحي مطوري Java. تعمل HashMap مع أزواج القيمة الرئيسية . كيف يتم تخزينها داخل HashMap نفسها؟ يحتوي HashMap على مجموعة داخلية من العقد:

Node<K,V>[] table

افتراضيًا، حجم المصفوفة هو 16، ويتضاعف في كل مرة يتم ملؤها بالعناصر (أي عند الوصول إلى LOAD_FACTOR ؛ فهو يحدد العتبة لمدى امتلاء المصفوفة - بشكل افتراضي، هو 0.75 ) . تقوم كل عقدة بتخزين تجزئة للمفتاح، والمفتاح، والقيمة، ومرجع إلى العنصر التالي: في هذه الحالة، يعني "المرجع إلى العنصر التالي" أننا نتعامل مع قائمة مرتبطة بشكل فردي، حيث يحتوي كل عنصر على رابط للعنصر التالي. بمعنى آخر، تقوم HashMap بتخزين بياناتها في مجموعة من القوائم المرتبطة بشكل فردي. ولكن اسمحوا لي أن أقول على الفور أنه عندما تحتوي خلية من مصفوفة الجدول على قائمة مرتبطة بشكل فردي تتكون من أكثر من عنصر واحد، فهذا ليس جيدًا. وتسمى هذه الظاهرة الاصطدام . ولكن أول الأشياء أولا. دعونا نرى كيف يتم حفظ زوج جديد باستخدام طريقة الوضع . أولاً، تحصل الطريقة على hashCode() للمفتاح . وهذا يعني أنه لكي تعمل HashMap بشكل صحيح، يجب أن تكون المفاتيح التي تستخدمها هي فئات تتجاوز هذه الطريقة. يتم بعد ذلك استخدام رمز التجزئة هذا في طريقة التجزئة الداخلية لتحديد فهرس لبعض الخلايا داخل صفيف الجدول. يتيح لنا الفهرس الناتج الوصول إلى خلية معينة من مصفوفة الجدول. لدينا حالتان هنا:

1. الخلية فارغة — في هذه الحالة، يتم تخزين قيمة العقدة الجديدة فيها.
2. الخلية ليست فارغة — في هذه الحالة، تتم مقارنة قيم المفاتيح. إذا كانت متساوية، فستحل قيمة العقدة الجديدة محل القيمة القديمة؛ إذا لم تكن متساوية، فسيتم الوصول إلى القائمة التالية ، ومقارنة مفتاحها... وهكذا، حتى تقوم القيمة الجديدة إما بالكتابة فوق بعض القيمة القديمة أو نصل إلى نهاية القائمة المرتبطة بشكل فردي ثم نقوم بتخزين القيمة الجديدة هناك باسم العنصر الأخير.

عند البحث عن عنصر حسب المفتاح (باستخدام طريقة get(<key>) )، يتم حساب hashCode() للمفتاح ، ثم يتم حساب فهرسه داخل المصفوفة باستخدام hash() . الرقم الناتج هو فهرس الخلية في مصفوفة الجدول ، والذي نبحث عنه بعد ذلك من خلال التكرار على العقد ومقارنة مفتاح العقدة المطلوبة مع مفتاح العقدة الحالية. من الناحية المثالية، تتمتع عمليات الخريطة بتعقيد خوارزمي يبلغ O(1)، لأننا نصل إلى مصفوفة، وكما تتذكر، فهي O(1)، بغض النظر عن عدد العناصر التي تحتوي عليها. لكننا لا نتعامل مع الحالة المثالية. عندما لا تكون الخلية فارغة (2) وتقوم بالفعل بتخزين بعض العقد، يصبح التعقيد الخوارزمي O(N) (خطيًا)، لأنه من الضروري الآن التكرار على العناصر قبل العثور على المكان المناسب. لا يسعني إلا أن أذكر أنه بدءًا من Java 8، إذا كانت العقدة في شكل قائمة مرتبطة بشكل فردي تحتوي على أكثر من 8 عناصر (تصادمات)، فسيتم تحويلها إلى شجرة ثنائية. في هذه الحالة، لم يعد التعقيد الخوارزمي O(N)، بل O(log(N)) — وتلك مسألة أخرى تمامًا، أليس كذلك؟ يعد HashMap موضوعًا كبيرًا، ويحب الأشخاص طرح أسئلة حوله في مقابلات العمل. لذا، أقترح أن تعرفه مثل الجزء الخلفي من يدك. أنا شخصياً لم أجري أي مقابلة لم تتضمن أسئلة حول HashMap . هذا كل شيء لهذا اليوم. يتبع...