Intervyuda nima so'rashi mumkin: Java-da ma'lumotlar tuzilmalari. 1-qism

Salom! Qanday qarashingizdan qat'i nazar, siz texnik kirish intervyusidan muvaffaqiyatli o'tmasdan dasturchi bo'lolmaysiz. Java bilan bog'liq ko'plab texnologiyalar mavjud va hamma narsani o'rganish mumkin emas. Qoidaga ko'ra, suhbat davomida aniq bir narsa so'raladi, agar ular loyiha uchun muhim bo'lgan biron bir doirada yaxshi tajribaga ega bo'lgan ishlab chiquvchini izlayotgan bo'lsalar. Agar shunday bo'lsa, siz ushbu ramka atrofida to'liq tezlikda ta'qib qilinasiz, bunga shubhangiz yo'q. Ammo endi biz har bir Java dasturchisi bilishi kerak bo'lgan baza haqida gapiramiz. Hammasi boshlanadigan klassik bilim haqida. Bugun men har qanday intervyuning asosiy mavzularidan biri - Java-dagi ma'lumotlar tuzilmalariga to'xtalib o'tmoqchiman . Shunday qilib, buta atrofida urish o'rniga, keling, boshlaylik. Suhbat davomida ushbu mavzu bo'yicha sizga berilishi mumkin bo'lgan savollar ro'yxatini toping.

1. Ma'lumotlar tuzilmalari haqida bir oz gapirib bering

Ma'lumotlar strukturasi - ma'lum bir tarzda tuzilgan ma'lumotlarni o'z ichiga olgan ma'lumotlar ombori. Ushbu tuzilmalar muayyan operatsiyalarni samarali bajarish uchun mo'ljallangan. Ma'lumotlar tuzilmalarining tipik misollari:

• massivlar,
• vayronalar,
• navbatlar,
• tegishli ro'yxatlar,
• grafiklar,
• daraxtlar,
• prefiks daraxtlari,
• hash jadvali.

Ular haqida ko'proq ma'lumotni bu erda va bu erda topishingiz mumkin . Ma'lumotlar dasturning asosiy komponenti bo'lib, tuzilmalar bu ma'lumotlarni aniq, aniq tuzilgan shaklda saqlashga imkon beradi. Ilovangiz nima qilsa ham, bu jihat unda doimo mavjud bo'ladi: agar u veb-do'kon bo'lsa, u holda mahsulotlar haqidagi ma'lumotlar saqlanadi, agar u ijtimoiy tarmoq bo'lsa, foydalanuvchilar va fayllar haqidagi ma'lumotlar va hokazo.

2. Massivlar haqida nimalarni bilasiz?

Massiv - bu bir xil turdagi qiymatlarni saqlash uchun konteyner, ularning soni oldindan ko'rsatilgan. Satr qiymatlari bilan massiv yaratishga misol:

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

Massivni yaratishda uning barcha elementlari uchun xotira ajratiladi: dastlab elementlar uchun qancha katakcha ko‘rsatilgan bo‘lsa, shuncha ko‘p xotira ajratiladi. Agar ma'lum miqdordagi katakchalardan iborat bo'sh massiv yaratilgan bo'lsa, u holda massivning barcha elementlariga standart qiymatlar beriladi. Masalan:

int[] arr = new int[10];

Shunday qilib, mantiqiy turdagi elementlarga ega massiv uchun boshlang'ich ( standart ) qiymatlar noto'g'ri bo'ladi , raqamli qiymatlari bo'lgan massivlar uchun - 0, char tipidagi elementlar bilan - \u0000 . Sinf tipidagi massiv (ob'ektlar) uchun - null (bo'sh satrlar emas - "" lekin null ). Ya'ni, yuqoridagi misolda arr massivining barcha qiymatlari to'g'ridan-to'g'ri aniqlanmaguncha 0 bo'ladi. To'plamlardan farqli o'laroq, massivlar dinamik emas. Muayyan o'lchamdagi massiv e'lon qilingandan so'ng, o'lchamning o'zini o'zgartirib bo'lmaydi. Massivga yangi element qo‘shish uchun siz yangi kattaroq massiv yaratishingiz va unga eskisidan barcha elementlarni nusxalashingiz kerak (ArrayList shunday ishlaydi). Hamma ham bilmaydigan va sizni juda yaxshi qo'lga olish mumkin bo'lgan bir nuqta bor. Java-da o'zgaruvchilarning ikki turi mavjud - oddiy tiplar va to'liq huquqli ob'ektlarga havolalar . Bulardan qaysi biri massivdir? Masalan, bu erda:

int[] arr = new int[10];

Hamma narsa oddiy ko'rinadi - bu 10 ta int element . Xo'sh, bu oddiy tur deb ayta olamizmi? Qanday bo'lmasin. Java-da massivlar ob'ektlar bo'lib, dinamik ravishda yaratilgan va Object tipidagi o'zgaruvchilarga tayinlanishi mumkin. Object sinfining barcha usullarini massivda chaqirish mumkin. Shunday qilib, biz hatto yozishimiz mumkin:

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

Konsolga chiqishda siz quyidagi kabi narsalarni olishingiz mumkin: Java-dagi massivlarning xususiyatlari haqida Java massivi haqidagi ushbu maqolada o'qing . O'z bilimlaringizni mustahkamlash uchun siz ushbu to'plamdan bir nechta muammolarni hal qilishingiz mumkin .

3. To‘plamlar ierarxiyasini tushuntiring

To'plamlar ma'lumotlar bilan ishlashda moslashuvchanlikni talab qiladigan holatlarda qo'llaniladi. To'plamlar element qo'shishi, elementni olib tashlashi va boshqa ko'plab operatsiyalarni bajarishi mumkin. Java-da juda ko'p turli xil ilovalar mavjud va biz hozirgi vaziyat uchun to'g'ri to'plamni tanlashimiz kerak. Odatda, Collection interfeysi haqida gapirganda , sizdan uning ba'zi ilovalarini va uning Map bilan aloqasini sanab o'tish so'raladi . Xo'sh, keling, bilib olaylik. Shunday qilib, To'plam va Xarita ma'lumotlar tuzilmalari uchun ikki xil ierarxiyadir. To'plam ierarxiyasi qanday ko'rinishga ega : To'plam interfeysi asosiy usullar ro'yxatiga ega bo'lgan asosiy havola bo'lib, ulardan uchta asosiy turdagi ma'lumotlar tuzilmalari paydo bo'ladi - O'rnatish , Ro'yxat , Navbat . Set<T> - har bir ob'ekt noyob bo'lgan ob'ektlar to'plamini ifodalovchi interfeys. List<T> - ro'yxat deb ataladigan ob'ektlarning tartiblangan ketma-ketligini ifodalovchi interfeys. Queue<T> - navbat sifatida tashkil etilgan tuzilmalar uchun javob beradigan interfeys (elementlarni ketma-ket saqlash). Avval aytib o'tganimizdek, Map alohida ierarxiyadir: Map<K, V> - bu lug'atni ifodalovchi interfeys bo'lib, unda elementlar kalit-qiymat juftlari sifatida joylashgan. Bundan tashqari, barcha tugmalar (K) Map ob'ektida noyobdir . Ushbu turdagi to'plam, agar biz kalitni - ob'ektning noyob identifikatorini bilsak, elementni topishni osonlashtiradi.

4. Set haqida nimalarni bilasiz?

Yuqorida aytib o'tilganidek, ushbu to'plam juda ko'p noyob elementlarni o'z ichiga oladi. Boshqacha qilib aytganda, bir xil ob'ekt Java to'plamida bir necha marta paydo bo'lishi mumkin emas. Shuni ham ta'kidlashni istardimki, biz raqam bo'yicha to'plamdan (indeks) elementni chiqara olmaymiz - faqat qo'pol kuch bilan. Muhimi shundaki, turli xil Set ilovalari ma'lumotlarni tizimlashtirishning turli usullariga ega. Muayyan amaliyotlarni batafsil ko'rib chiqamiz. Shunday qilib, Set ning asosiy ilovalari : HashSet - bu xesh-jadvalga asoslangan to'plam bo'lib, u o'z navbatida qidiruvga yordam beradi. Qidiruv va qo‘shish vaqtida ish faoliyatini yaxshilaydigan xesh funksiyasidan foydalanadi. Elementlar sonidan qat'iy nazar, umuman olganda, kiritish va qidirish (ba'zan o'chirish) doimiy vaqtga yaqin - O (1) da amalga oshiriladi. Xesh funksiyasini biroz keyinroq batafsil ko‘rib chiqamiz. Shuni ham ta'kidlashni istardimki, HashSetda barcha sehrlar sodir bo'ladigan HashMap mavjud . Bu erda Java'da HashSet haqida batafsil maqola . LinkedHashSet - bu sinf yangi usullarni qo'shmasdan HashSet-ni kengaytiradi. LinkedList singari , bu sinf ham to'plam elementlarining bog'langan ro'yxatini ular kiritilgan tartibda saqlaydi. Bu sizga berilgan to'siq amalga oshirishda zarur tartibni tashkil qilish imkonini beradi . TreeSet klassi elementlarni saqlash strukturasini tashkil qilish uchun qizil-qora daraxtga asoslangan to'plamni yaratadi. Boshqacha qilib aytganda, berilgan to'plamda biz elementlarni o'sish tartibida tartiblashimiz mumkin. Agar biz "quti"dagi ba'zi standart ob'ektlardan foydalansak, masalan, Integer , unda butun sonlar to'plamini o'sish tartibida joylashtirish uchun hech narsa qilishimiz shart emas:

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

System.out.println(set);

Va konsolda biz natijani olamiz: Ya'ni, bu to'plamda raqamlar tartiblangan shaklda saqlanadi. Agar TreeSet da String elementlaridan foydalansak , ular tartiblanadi, lekin alifbo tartibida. Xo'sh, agar bizda standart (odatiy) sinf bo'lsa-chi? Ushbu sinf ob'ektlari TreeSet ni qanday tuzatadi ? Agar biz ushbu to'plamga ixtiyoriy ob'ektni belgilashga harakat qilsak :

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);

Biz ClassCastException olamiz , chunki TreeSet bu turdagi ob'ektlarni qanday saralashni bilmaydi. Bunday holda, solishtirma interfeysi va uning compareTo usulini amalga oshirish uchun bizga maxsus ob'ekt kerak bo'ladi :

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 + '\'' +
               '}';
   }
}

Siz sezganingizdek, compareTo usuli int ni qaytaradi :

• 1 agar joriy (bu) ob'ekt katta deb hisoblansa;
• -1 agar joriy ob'ekt argument sifatida kelgan ob'ektdan kichikroq deb hisoblansa;
• 0, agar ob'ektlar teng bo'lsa (biz bu holatda foydalanmaymiz).

Bunday holda, bizning TreeSet to'g'ri ishlaydi va natijani ko'rsatadi: Yana bir usul - taqqoslash interfeysi va uning solishtirish usulini amalga oshiradigan alohida saralash sinfini yaratish :

public class CatComparator implements Comparator {

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

Bunday holda, undan foydalanish uchun biz ushbu sinf ob'ektini TreeSet konstruktoriga o'rnatishimiz kerak :

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

Shundan so'ng, TreeSet- ga kiritilgan Cat sinfining barcha ob'ektlari Cat Comparator klassi yordamida tartiblanadi . Ushbu maqoladan Java-dagi Comparator va Comparator haqida ko'proq bilib olishingiz mumkin .

5. Navbat haqida bizga xabar bering

Navbat - navbat sifatida tashkil etilgan tuzilmalar uchun javob beradigan interfeys - elementlarni ketma-ket saqlaydigan ma'lumotlar strukturasi. Masalan, navbatda turgan odamlardan birinchi bo'lib boshqalardan erta kelgan, oxirgisi esa hammadan kech kelgan kishi bo'ladi. Bu usul deyiladi FIFO , ya'ni Birinchi kiruvchi birinchi chiqadi . Noyob navbat usullari birinchi yoki oxirgi element bilan ishlashga qaratilgan, masalan:

• qo'shish va taklif qilish - navbatning oxiriga element qo'shadi,
• olib tashlash - bu navbatning sarlavhasini oladi va o'chiradi,
• peek - navbat sarlavhasini oladi, lekin olib tashlamaydi.

2-QISM