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

היי! כמה שעות לוקח להיות מאסטר במשהו? לא פעם שמעתי משהו כמו: "כדי להיות מאסטר בכל דבר, אתה צריך להשקיע בזה 10,000 שעות." זה מספר מאיים, לא? ובכל זאת, אני תוהה אם זה נכון. ואני כל הזמן מנסה להבין כמה שעות כבר השקעתי בשליטה באמנות התכנות. וכשאעבור את הקו המיוחד הזה של 10,000 שעות ואהיה מאסטר, האם ארגיש את ההבדל? או שכבר חציתי את הגבול הזה מזמן בלי ששמתי לב? כך או כך, אתה לא צריך להשקיע כמות עצומה כל כך של זמן כדי להפוך למתכנת. הדבר החשוב הוא לנצל את הזמן שלך בחוכמה. המטרה העיקרית שלך היא להגיע לראיון. ובראיונות, מפתחי תוכנה לעתיד נשאלים תחילה על תיאוריה, אז זה צריך להיות כוח. למעשה, בזמן שאתה מתכונן לראיון, התפקיד שלך הוא לגלות את כל הפערים בידע של תיאוריית ג'אווה בסיסית ולאחר מכן למלא אותם. היום אני כאן כדי לעזור לכם לעשות בדיוק את זה, מכיוון שהיום נמשיך בסקירה של שאלות הראיונות הפופולריות ביותר. ובכן, בואו נמשיך!

89. במה שונה ArrayList מ-LinkedList?

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

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

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

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

   שיטת ה-add מוסיפה אלמנט לתא הריק האחרון במערך ( O(1) ).

2. הוספת פריט לפי אינדקס פירושה בדרך כלל הכנסתו איפשהו באמצע הרשימה. ב- LinkedList , השיטה תחפש תחילה את המיקום הרצוי על ידי איטרציה על האלמנטים מהזנב והראש ( O(n/2) ) ולאחר מכן תכניס את הערך על ידי החלפת הפניות של האלמנטים משני הצדדים של המקום שבו אלמנט חדש מוכנס ( O(1) ). המורכבות האלגוריתמית הכוללת של פעולה זו תהיה O(n/2) .

   באותו מצב (הוספה לפי אינדקס), ArrayList מוצא את המיקום הרצוי ( O(1) ) ואז מעביר את כל האלמנטים הממוקמים ימינה (כולל האלמנט שכבר מאוחסן באינדקס שצוין) ימינה באחד (ש עשוי לדרוש יצירת מערך פנימי חדש והעתקת אלמנטים אליו) ( O(n/2) ). המורכבות הכוללת היא O(n/2) .

3. הוספת אלמנט להתחלה של LinkedList דומה להוספת אלמנט לסוף: האלמנט החדש הופך לראש החדש ( O(1) ). אבל עבור ArrayList, הפעולה הזו דורשת הזזת כל האלמנטים ימינה ( O(n) ).

השורה התחתונה היא שעבור LinkedList המורכבות האלגוריתמית תנוע בין O(1) ל- O(n/2) . התבוננות נוספת היא שככל שההכנסה קרובה יותר לסוף או לתחילת הרשימה, כך היא מהירה יותר. עבור ArrayList , המורכבות האלגוריתמית נעה בין O(1) ל- O(n) , וככל שההכנסה קרובה יותר לסוף הרשימה, כך היא מהירה יותר. הגדרת אלמנט (סט) פעולה זו כותבת אלמנט למיקום המצוין ברשימה, ומחליפה כל רכיב קיים. ב- LinkedList , פעולה זו דומה להוספה, מכיוון שהאתגר הגדול ביותר כאן הוא למצוא את מיקומו של האלמנט. האלמנט הקיים מוחלף על ידי עדכון זוג הפניות, כך ששוב יש לנו מורכבות אלגוריתמית המשתנה מ- O(1) ל- O(n/2) , בהתאם למרחק המיקום הרצוי מסוף או תחילת הרשימה. אבל עבור ArrayList , פעולה זו מוצאת את התא הרצוי לפי אינדקס וכותבת שם את האלמנט החדש. כמו פעולת הסט, לחיפוש לפי אינדקס יש מורכבות אלגוריתמית של O(1) . קבלת אלמנט לפי אינדקס (get) קבלת אלמנט מ- LinkedList פועלת לפי אותו עקרון חיפוש שמשמש בפעולות אחרות. המורכבות תלויה במרחק מהסוף או מההתחלה, כלומר משתנה מ- O(1) ל- O(n/2) . כפי שצוין קודם לכן, עבור ArrayList , למציאת אלמנט לפי אינדקס במערך הפנימי יש מורכבות של O(1) . הסרת אלמנט לפי אינדקס (הסר) עבור LinkedList , אותו עיקרון חל שוב. תחילה מאתרים את האלמנט, ולאחר מכן נכתבים מחדש ההפניות, שכניו של האלמנט שנמחק מתייחסים כעת זה לזה, ומבטלים את ההפניות לאלמנט שנמחק, אשר ינוקה לאחר מכן על ידי אספן האשפה. במילים אחרות, המורכבות האלגוריתמית עדיין זהה - היא משתנה מ- O(1) ל- O(n/2) . עבור ArrayList , פעולה זו דומה יותר להוספת אלמנט חדש (add). ראשית, השיטה מוצאת את האלמנט הרצוי ( O(1) ), מסירה אותו, ולאחר מכן כל האלמנטים הממוקמים מימין מוזזים צעד אחד שמאלה על מנת לסגור את הפער שנוצר בהסרה. להסרת אלמנט יש אותה מורכבות אלגוריתמית כמו פעולת ההוספה - מ- O(1) עד O(n). ככל שהאלמנט שהוסר קרוב יותר לסוף הרשימה, כך המורכבות האלגוריתמית של פעולה זו נמוכה יותר. ועכשיו כיסינו את כל הפעולות העיקריות. הרשו לי להזכיר לכם שכאשר משווים בין שני סוגי הרשימות הללו, עליכם להבהיר את המצב הספציפי שבו הם נמצאים בשימוש. רק אז תוכלו לענות באופן חד משמעי על שאלת המראיין.

90. במה שונה ArrayList מ-HashSet?

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

• ArrayList מיישמת את ממשק List בעוד HashSet מיישמת את ממשק הסט .

• ArrayList מאפשר לך לגשת לאלמנט לפי אינדקס: לפעולת get יש מורכבות אלגוריתמית O(1) , אבל HashSet מאפשרת לך לגשת לאלמנט רצוי רק על ידי איטרציה, מה שמניב מורכבות אלגוריתמית הנעה בין O(1) ל- O(n) .

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

• ArrayList מיושם באמצעות מערך פנימי, אך HashSet מיושם באמצעות HashMap פנימי .

• ArrayList שומר על סדר ההכנסה של האלמנטים, אבל HashSet הוא קבוצה לא מסודרת ואינו שומר על סדר האלמנטים.

• ArrayList מאפשר כל מספר של ערכי null, אבל אתה יכול להוסיף רק ערך null אחד ל- HashSet (אחרי הכל, האלמנטים חייבים להיות ייחודיים).

91. מדוע ל-Java יש כל כך הרבה מימושים שונים של מערך דינמי?

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

92. מדוע ל-Java יש כל כך הרבה מימושים שונים של אחסון ערך מפתח?

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

93. איך אני ממיין אוסף של אלמנטים?

הדבר הראשון שיש לומר הוא שהמחלקה המייצגת רכיבי אוסף חייבת ליישם את ממשק Comparable , המורכב משיטת compareTo . או שאתה צריך מחלקה המיישמת את ממשק Comparator , כולל שיטת ההשוואה שלו . שתי השיטות מציינות כיצד להשוות אובייקטים מסוג נתון. זה קריטי בעת מיון, מכיוון שאלגוריתם המיון צריך להבין באיזה עיקרון להשתמש כדי להשוות אלמנטים. זה נעשה בעיקר על ידי יישום Comparable ישירות במחלקה שברצונך למיין. השימוש ב-Comparator הוא פחות נפוץ. נניח שאתה משתמש במחלקה מספריה כלשהי והיא לא מיישמת Comparable , אבל אתה צריך למיין אוסף של האובייקטים שלה. מכיוון שאינך יכול לשנות את הקוד של המחלקה הזו (למעט על ידי הארכתו), אתה יכול לכתוב יישום של Comparator שמציין כיצד להשוות בין אובייקטים של המחלקה. ועוד דוגמה אחת. אם אתה צריך למיין אובייקטים מאותו סוג בדרכים שונות, אז אתה יכול לכתוב יישומי Comparator מרובים לשימוש במצבים שונים. ככלל, מחלקות רבות מחוץ לקופסה, למשל String , כבר מיישמות את הממשק Comparable . זה אומר שאתה לא צריך לדאוג איך להשוות שיעורים אלה. אתה יכול פשוט להמשיך ולהשתמש בהם. הדרך הראשונה והברורה ביותר היא להשתמש במחלקה TreeSet או TreeMap . מחלקות אלו מאחסנות אלמנטים בסדר ממוין בהתבסס על המשווה המיושם על ידי רכיבי המחלקה. אל תשכח ש- TreeMap ממיין מפתחות, לא ערכים. אם אתה משתמש ב-Comparator במקום Comparable , אז אתה צריך להעביר אובייקט Comparator לבנאי האוסף בעת יצירתו:

TreeSet treeSet = new TreeSet(customComparator);

אבל מה אם יש לך סוג אחר של אוסף? איך מסדרים את זה? במקרה זה, הדרך השנייה של מחלקת השירות Collections - השיטה sort() - מתאימה. השיטה היא סטטית, אז כל מה שאתה צריך זה להוסיף את שם המחלקה ולאחר מכן לעבור ברשימה למיון. לדוגמה:

Collections.sort(someList);

אם אתה משתמש ביישום של Comparator ולא Comparable , עליך להעביר אותו כארגומנט השני:

Collections.sort(someList, customComparator);

פעולה זו תשנה את הסדר הפנימי של האלמנטים ברשימה שעברה: הרשימה תמוין באמצעות המשווה. שים לב שהרשימה שעברה חייבת להיות ניתנת לשינוי, אחרת השיטה תיכשל ותשליך UnsupportedOperationException . אפשרות שלישית היא להשתמש בשיטת המיון של המחלקה Stream , אשר ממיינת את האלמנטים של האוסף. אם אנו משתמשים ב-Comarable :

someList = someList.stream().sorted().collect(Collectors.toList());

אם אנחנו משתמשים ב-Comparator :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

הדרך הרביעית היא ליישם ידנית אלגוריתם מיון, לדוגמה, מיון בועות או מיון מיזוג .

מחלקת אובייקט. equals() ו-hashCode()

94. תן תיאור קצר של המחלקה Object ב-Java.

בחלק השני של הסקירה, כבר דנו בשיטות של המחלקה Object . כאן אזכיר לכם שהמחלקה Object היא אב קדמון של כל מחלקה בג'אווה. יש לו 11 שיטות, אשר בתורן עוברות בירושה לכל המחלקות.

95. לשם מה משתמשים equals() ו-hashCode() ב-Java?

hashCode() היא שיטה של ​​מחלקת Object שעוברת בירושה לכל המחלקות. תפקידו ליצור מספר המייצג אובייקט ספציפי. דוגמה לשיטה זו בפעולה ניתן למצוא ב- HashMap , שם היא נקראת על אובייקטי מפתח כדי לקבל את ה-hashcode המקומי, אשר יקבע באיזה דלי (תא של המערך הפנימי) יאוחסן צמד המפתח-ערך. כמו כן, שיטה זו משמשת בדרך כלל בשיטת equals() כאחת הדרכים העיקריות שלה לזהות אובייקטים. equals() היא שיטה של ​​מחלקת Object שתפקידה להשוות אובייקטים ולקבוע אם הם שווים. שיטה זו משמשת בכל מקום בו אנו צריכים להשוות אובייקטים, כי אופרטור ההשוואה הסטנדרטי == אינו מתאים לאובייקטים, מכיוון שהוא משווה רק הפניות לאובייקטים.

96. ספר לנו על החוזה בין equals() ל-hashCode() ב-Java?

ראשית, הרשו לי לומר שכדי שהשיטות equals() ו- hashCode() יעבדו כהלכה, יש לעקוף אותן כראוי. היישום החדש שלהם חייב לעמוד בכללים הבאים:

• אובייקטים זהים שעבורם שווה מחזירים true חייבים להיות בעלי אותם קודי hash.
• אובייקטים עם אותם קודי Hash אינם בהכרח שווים.

כעת נראה כמו מקום טוב לעצור בו עד לחלק הבא של הסקירה!