מה הם עשויים לשאול בראיון: מבני נתונים בג'אווה. חלק 1

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

1. ספר לנו קצת על מבני נתונים

מבנה נתונים הוא מאגר נתונים המכיל מידע מובנה בצורה מסוימת. מבנים אלה מיועדים לביצוע יעיל של פעולות מסוימות. דוגמאות אופייניות למבני נתונים הן:

• מערכים,
• ערימות,
• תורים,
• רשימות קשורות,
• גרפים,
• עצים,
• עצי קידומת,
• טבלת גיבוב.

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

2. מה אתה יודע על מערכים?

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

String[] strArray = {"Java","is","the","best","language"};

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

int[] arr = new int[10];

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

int[] arr = new int[10];

נראה שהכל פשוט - אלו הם 10 אלמנטים int . אז, אנחנו יכולים לומר שזה סוג פשוט? לא משנה איך זה. ב-Java, מערכים הם אובייקטים, נוצרים באופן דינמי וניתן לשייך אותם למשתנים מסוג Object. ניתן לקרוא לכל השיטות של המחלקה Object במערך. אז אנחנו יכולים אפילו לכתוב:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

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

3. הסבר את ההיררכיה של האוספים

אוספים משמשים במצבים שבהם אתה צריך גמישות בעבודה עם נתונים. אוספים יכולים להוסיף אלמנט, להסיר אלמנט ולבצע פעולות רבות אחרות. יש הרבה יישומים שונים בג'אווה, ואנחנו רק צריכים לבחור את האוסף המתאים למצב הנוכחי. בדרך כלל, כאשר אתה מזכיר את ממשק האוסף , אתה מתבקש לרשום כמה מהיישומים שלו ואת הקשר שלו עם מפה . ובכן, בוא נגלה. אז, אוסף ומפה הן שתי היררכיות שונות עבור מבני נתונים. איך נראית היררכיית האוסף : ממשק האוסף הוא הקישור העליון המפתח עם רשימה של שיטות בסיסיות, שמהן נובעים שלושה סוגים בסיסיים של מבני נתונים - סט , רשימה , תור . Set<T> הוא ממשק המייצג אוסף של אובייקטים שבהם כל אובייקט הוא ייחודי. List<T> הוא ממשק המייצג רצף מסודר של אובייקטים הנקרא רשימה. Queue<T> הוא ממשק האחראי על מבנים שמאורגנים כתור (אחסון רציף של אלמנטים). כפי שהוזכר קודם לכן, מפה היא היררכיה נפרדת: מפה<K,V> היא ממשק המייצג מילון שבו אלמנטים כלולים כצמדי מפתח-ערך. יתר על כן, כל המפתחות (K) הם ייחודיים בתוך אובייקט המפה . סוג זה של אוסף מקל על מציאת אלמנט אם אנו יודעים את המפתח - המזהה הייחודי של האובייקט.

4. מה אתה יודע על סט?

כפי שנאמר קודם לכן, אוסף זה כולל אלמנטים ייחודיים רבים. במילים אחרות, אותו אובייקט לא יכול להופיע יותר מפעם אחת ב-Java Set . אני גם רוצה לציין שאנחנו לא יכולים לחלץ אלמנט מ- Set by number (אינדקס) - רק בכוח גס. הדבר החשוב הוא שליישומי סט שונים יש דרכים שונות לבניית נתונים. נשקול עוד יישומים ספציפיים. אז, ההטמעות העיקריות של Set : HashSet היא סט שמבוסס על טבלת hash, אשר בתורה עוזרת בחיפוש. משתמש בפונקציית Hash המשפרת את הביצועים במהלך חיפושים והוספות. ללא קשר למספר האלמנטים, באופן כללי, הכנסה וחיפוש (לעיתים מחיקה) מתבצעים בזמן קרוב לקבוע - O(1). נסתכל על פונקציית ה-hash בפירוט רב יותר מעט מאוחר יותר. אני גם רוצה לציין שה- HashSet מכיל HashMap , וזה המקום שבו כל הקסם מתרחש. הנה מאמר מפורט על HashSet ב-Java . LinkedHashSet - מחלקה זו מרחיבה את HashSet מבלי להוסיף שיטות חדשות. בדומה ל- LinkedList , מחלקה זו שומרת על רשימה מקושרת של הרכיבים של קבוצה בסדר שבו הם הוכנסו. זה מאפשר לך לארגן את הסדר הדרוש ביישום סט נתון . המחלקה TreeSet יוצרת קבוצה שמבוססת על עץ אדום-שחור כדי לארגן את מבנה רכיבי האחסון. במילים אחרות, בקבוצה נתונה נוכל למיין את האלמנטים בסדר עולה. אם אנו משתמשים בכמה אובייקטים סטנדרטיים מה"קופסה", למשל, מספר שלם , אז אנחנו לא צריכים לעשות שום דבר כדי לסדר את קבוצת המספרים השלמים בסדר עולה:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

ובקונסולה נקבל את הפלט: כלומר, בקבוצה הזו המספרים מאוחסנים בצורה ממוינת. אם נשתמש ברכיבי String ב- TreeSet , הם ימוינו, אבל לפי אלפביתי. ובכן, מה אם יש לנו שיעור סטנדרטי (מותאם אישית)? כיצד אובייקטים של מחלקה זו יבנו את TreeSet ? אם ננסה להקצות אובייקט שרירותי לסט הזה :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

נקבל ClassCastException כי ה-TreeSet לא יודע למיין אובייקטים מסוג זה. במקרה זה, אנו זקוקים לאובייקט המותאם אישית שלנו כדי ליישם את ממשק Comparable ואת שיטת compareTo שלו :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

כפי ששמת לב, שיטת compareTo מחזירה int :

• 1 אם האובייקט הנוכחי (זה) נחשב גדול;
• -1 אם האובייקט הנוכחי נחשב קטן יותר מזה שהגיע כטיעון;
• 0 אם האובייקטים שווים (אנחנו לא משתמשים בזה במקרה הזה).

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

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

במקרה זה, כדי להשתמש בו, עלינו להגדיר אובייקט מהמחלקה הזו לבנאי TreeSet :

TreeSet set = new TreeSet<>(new CatComparator());

לאחר מכן, כל האובייקטים של המחלקה Cat הכלולים ב- TreeSet ימוינו באמצעות המחלקה Cat Comparator . אתה יכול ללמוד עוד על Comparator ו- Comarable ב-Java ממאמר זה .

5. ספר לנו על Queue

Queue הוא ממשק שאחראי על מבנים שמאורגנים כתור - מבנה נתונים המאחסן אלמנטים ברצף. לדוגמה, מתוך תור של אנשים, הראשון שייכנס יהיה זה שהגיע מוקדם יותר מאחרים, והאחרון יהיה זה שהגיע מאוחר יותר מכולם. שיטה זו נקראת FIFO , כלומר, First in First Out . שיטות תור ייחודיות מתמקדות בעבודה עם האלמנט הראשון או האחרון, למשל:

• הוסף והצע - מכניס אלמנט בסוף התור ,
• הסר - מאחזר ומסיר את הכותרת של התור הזה,
• הצצה - מאחזר אך לא מסיר את כותרת התור.

חלק 2