בחינת שאלות ותשובות מראיון עבודה למשרת מפתח Java. חלק 9

להיות מתכנת זה לא קל. תמיד יש משהו חדש ללמוד. וכמו בכל מאמץ אחר, הדבר הקשה ביותר הוא להתחיל, לעשות את הצעד הראשון לקראת המטרה שלך. אבל מכיוון שאתה כבר כאן וקורא את המאמר הזה, השלמת את הצעד הראשון. זה אומר שעכשיו אתה צריך לנוע בכוונה לעבר המטרה שלך, מבלי להאט או לסטות הצידה. אני מניח שהמטרה שלך היא להפוך למפתח Java או לחזק את הידע שלך אם אתה כבר מפתח. אם כן, בואו נמשיך להתמודד עם רשימה נרחבת של שאלות ראיונות למפתחי Java. בוא נמשיך!

אוספים

84. ספר לנו על איטרטורים וכיצד הם משמשים

אוספים הוא נושא מועדף בכל ראיון מפתח Java. כאשר עונים על שאלות על היררכיית האוסף, מועמדים אומרים לעתים קרובות שזה מתחיל בממשק האוסף . אבל זה לא כך. יש ממשק נוסף ברמה אחת מעל: Iterable . ממשק זה מורכב משיטה iterator() המאפשרת לך לגשת לאובייקט Iterator עבור האוסף הנוכחי. ומה זה בדיוק האובייקט האיטרטור הזה? האובייקט Iterator מספק את היכולת לעבור באוסף ולחזור על האלמנטים שלו, והמשתמש אינו צריך לדעת את פרטי היישום הספציפיים של האוסף. במילים אחרות, הוא מהווה מעין מצביע על מרכיבי הקולקציה, כאילו הוא מציץ פנימה לאחד מהם. לאיטרטור יש שיטות כגון:

• hasNext() - מחזירה true אם לאיטרציה יש אלמנט אחר (שיטה זו מאפשרת לך לדעת מתי הגעת לסוף האוסף);

• next() - מחזיר את הפריט הבא באיטרציה. אם אין אחד, אז NoSuchElementException נזרק. זה אומר שלפני שאתה משתמש בשיטה זו, עדיף להשתמש בשיטת hasNext() כדי לוודא שקיים אלמנט הבא;

• remove() - מסיר מהאוסף את האלמנט האחרון שהתקבל באמצעות שיטת next() . אם next() מעולם לא נקרא, אז הקריאה remove() תגרום לזריקת 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() - מחזירה true אם יש אלמנט שנמצא לפני האלמנט הבא (אם יש אלמנט קודם);

• nextIndex() - מחזיר את האינדקס של האלמנט הבא;

• previous() - מחזיר את האלמנט הקודם (זה שלפני האלמנט הבא);

• previousIndex מחזיר את האינדקס של האלמנט הקודם.

• set(<Element>) - מחליף את האלמנט האחרון שהוחזר על ידי next() או previous() .

כפי שאתה יכול לראות, לאיטרטור הזה יש פונקציונליות הרבה יותר מעניינת: הוא מאפשר לך ללכת בשני הכיוונים ומספק חופש ניכר בעבודה עם אלמנטים. כדאי גם לדעת שכאשר אנשים מדברים על איטרטורים, הם מתכוונים לפעמים לתבנית העיצוב עצמה.

85. איזו היררכיית אוסף קיימת במסגרת Java Collection?

ישנן שתי היררכיות אוסף בג'אווה. ההיררכיה הראשונה היא היררכיית האוסף, בעלת המבנה הבא: היא מחולקת לתת-אוספים הבאים:

• סט הוא ממשק המתאר סט, מבנה נתונים המכיל אלמנטים ייחודיים לא מסודרים (לא חוזרים). לממשק הזה יש כמה יישומים סטנדרטיים: TreeSet , HashSet ו- LinkedHashSet .

• רשימה היא ממשק המתאר מבנה נתונים המאחסן רצף מסודר של אובייקטים. ניתן להכניס ולהסיר אובייקטים ברשימה לפי האינדקס שלהם ברשימה (כמו מערך, אבל עם שינוי גודל דינמי) . לממשק הזה יש גם כמה יישומים סטנדרטיים: ArrayList , Vector ( הוצא משימוש ולא נעשה בו שימוש בפועל ), ו- LinkedList .

• Queue הוא ממשק המתאר מבנה נתונים המאחסן פריטים בתור First In First Out (FIFO) . לממשק הזה יש את ההטמעות הסטנדרטיות הבאות: LinkedList (נכון, הוא מיישם גם Queue ) ו- 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). יש שיטת add(<Index>, <Elelement>) דומה . הוא מוסיף אלמנט לא לסוף הרשימה (מערך), אלא לתא הספציפי שמצוין על ידי האינדקס שנכנס כארגומנט. במקרה זה, מורכבות הזמן תשתנה בהתאם למקום שבו תוסיף:

• אם ההוספה קרובה לתחילת הרשימה, אז מורכבות הזמן תהיה קרובה ל-O(N), כי כל האלמנטים הממוקמים מימין לחדש יצטרכו להיות מוזזים תא אחד ימינה;
• אם הרכיב יוכנס באמצע, אז הוא יהיה O(N/2), מכיוון שאנו צריכים להזיז רק חצי מפריטי הרשימה תא אחד ימינה.

כלומר, מורכבות הזמן של שיטה זו נעה בין O(1) ל-O(N), תלוי היכן הוכנס האלמנט. 2. set(<Index>, <Element>) - כותב אלמנט למיקום שצוין ברשימה. אם אלמנט כבר קיים במיקום זה, השיטה מחליפה אותו. מורכבות הזמן של פעולה זו היא O(1), מכיוון שהיא אינה כרוכה בפעולות Shift: אנו פשוט משתמשים באינדקס כדי לחשב את כתובת התא במערך, שיש לו מורכבות O(1), ולאחר מכן כותבים את האלמנט החדש. . 3. remove(<index>) - מסיר אלמנט לפי האינדקס שלו במערך הפנימי. בעת הסרת פריט שאינו בסוף הרשימה, יש להזיז את כל הפריטים מימין לפריט שנמחק תא אחד שמאלה על מנת לסגור את הפער הנובע מהמחיקה. בהתאם לכך, מורכבות הזמן תהיה זהה ל- add(<Index>, <Element>) כאשר אלמנט נוסף באמצע: O(N/2). אחרי הכל, אתה צריך להעביר חצי מהאלמנטים תא אחד שמאלה. ואם בהתחלה עסקינן, אז O(N). או אם בסוף, אז O(1), כי אתה לא צריך להזיז שום דבר.

87. מהו המבנה הפנימי של LinkedList?

ArrayList מכיל אלמנטים במערך הפנימי, אך LinkedList מאחסן אותם ברשימה מקושרת כפולה . זה אומר שכל אלמנט מכיל קישור לאלמנט הקודם ולאלמנט הבא . האלמנט הראשון אינו מקשר לאלמנט הקודם (אחרי הכל, הוא הראשון). הוא נחשב גם לראש הרשימה, ולאובייקט 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 מאחסן את הנתונים שלו במערך של רשימות מקושרות בודדות. אבל הרשו לי לומר מיד שכאשר לתא של מערך הטבלה יש רשימה עם קישור יחיד שמורכב מיותר מאלמנט אחד, זה לא טוב. תופעה זו נקראת התנגשות . אבל דבר ראשון. בוא נראה איך זוג חדש נשמר בשיטת ה-put . ראשית, השיטה מקבלת את ה-hashCode() של המפתח . זה מרמז שכדי ש- HashMap יעבוד כהלכה, המפתחות שבהם אתה משתמש חייבים להיות מחלקות שעוקפות שיטה זו. לאחר מכן נעשה שימוש בקוד ה-hash הזה בשיטת ה-hash() הפנימית כדי לקבוע אינדקס של תא כלשהו בתוך מערך הטבלה. האינדקס המתקבל מאפשר לנו לגשת לתא ספציפי של מערך הטבלה. יש לנו כאן שני מקרים:

1. התא ריק - במקרה זה, ערך הצומת החדש מאוחסן בו.
2. התא אינו ריק - במקרה זה, ערכי המפתחות מושווים. אם הם שווים, אז ערך הצומת החדש מחליף את הישן; אם לא שווה, אז ניגש אל הבא , והמפתח שלו מושווה... וכן הלאה, עד שהערך החדש יחליף ערך ישן כלשהו או שנגיע לסוף הרשימה המקושרת בודדת ואז מאחסנים שם את הערך החדש כ- אלמנט אחרון.

כאשר מחפשים אלמנט לפי מפתח (באמצעות שיטת get(<key>) ), ה- hashCode() של המפתח מחושב, ואז האינדקס שלו בתוך המערך מחושב באמצעות hash() . המספר המתקבל הוא האינדקס של תא במערך הטבלה , שאותו אנו מחפשים על ידי איטרציה על צמתים והשוואה בין המפתח של הצומת הרצוי למפתח של הצומת הנוכחי. באופן אידיאלי, לפעולות מפה יש מורכבות אלגוריתמית של O(1), מכיוון שאנו ניגשים למערך, וכפי שתזכרו, הוא O(1), ללא קשר למספר האלמנטים שהוא מכיל. אבל אנחנו לא עוסקים במקרה האידיאלי. כשהתא לא ריק (2) וכבר מאחסן כמה צמתים, אז המורכבות האלגוריתמית הופכת ל-O(N) (לינארית), כי עכשיו יש צורך לבצע איטרציה על האלמנטים לפני שנמצא את המקום הנכון. אני לא יכול שלא להזכיר שהחל ב-Java 8, אם לצומת בצורה של רשימה עם קישור יחיד יש יותר מ-8 אלמנטים (התנגשויות), אז הוא מומר לעץ בינארי. במקרה הזה, המורכבות האלגוריתמית היא כבר לא O(N), אלא O(log(N)) - וזה עניין אחר לגמרי, לא? HashMap הוא נושא גדול, ואנשים אוהבים לשאול עליו שאלות בראיונות עבודה. אז, אני מציע שתדע את זה כמו את כף היד שלך. באופן אישי, מעולם לא היה לי ראיון שלא כלל שאלות ב- HashMap . זה הכל להיום. המשך יבוא...