Analisis pitakonan lan wangsulan saka wawancara kanggo pangembang Jawa. Bagean 10

Hello! Pira jam sing dibutuhake kanggo dadi master ing sesuatu? Aku kerep krungu kaya: "Kanggo dadi master ing apa wae, sampeyan kudu nglampahi 10.000 jam." Nomer sing medeni, ta? Nanging, aku kepengin weruh yen iki bener? Lan aku terus-terusan nyoba ngerteni pirang-pirang jam aku wis nandur modal kanggo nguwasani seni pemrograman. Lan nalika aku ngliwati 10.000 jam sing ditresnani lan dadi master, apa aku bakal ngrasakake prabédan iki? Utawa apa aku wis nate nyabrang dheweke wiwit biyen tanpa sadhar? Siji cara utawa liyane, kanggo dadi programmer, sampeyan ora perlu nandur modal wektu sing akeh banget. Sing utama yaiku nggunakake kanthi wicaksana. Tujuan utama sampeyan yaiku lulus wawancara. Lan ing wawancara kanggo wong anyar, sing pertama ditakoni yaiku teori, dadi sampeyan kudu kuwat. Bener, nalika nyiapake wawancara, tugas sampeyan yaiku nemokake kabeh kesenjangan ing teori dhasar pangembang Jawa lan nutupi kawruh. Lan dina iki aku bakal nulungi sampeyan babagan perkara iki, amarga aku ana ing kene kanggo terus nganalisa pitakonan sing paling populer. Dadi ayo terus!

89. Kepiye ArrayList beda karo LinkedList?

Iki minangka salah sawijining pitakonan sing paling populer bebarengan karo pitakonan babagan struktur internal HashMap . Ora ana wawancara siji sing rampung tanpa, lan mulane jawaban kasebut kudu "mumbul saka untumu." Saliyane sing jelas - jeneng sing beda-beda - beda-beda ing struktur internal. Sadurunge, kita nliti struktur internal ArrayList lan LinkedList , mula aku ora bakal njlentrehake babagan implementasine. Ayo kula mung ngelingake yen ArrayList diimplementasikake adhedhasar array internal, sing ditambah yen perlu miturut rumus:

<размерТекущегоМассива> * 3 / 2  + 1

Ing wektu sing padha, LinkedList dileksanakake adhedhasar dhaptar internal dobel link, yaiku, saben unsur duwe pranala menyang sadurunge lan sabanjure, ora kalebu nilai sing minangka wiwitan / pungkasan dhaptar. Wong seneng takon pitakonan iki ing format: "Sing luwih apik - ArrayList utawa LinkedList ?", ngarep-arep bisa nyekel sampeyan. Sawise kabeh, yen sampeyan nuding salah sijine minangka jawaban, iku bakal dadi jawaban sing salah. Nanging, sampeyan kudu njlentrehake kahanan tartamtu sing sampeyan gunakake - akses indeks utawa selipan menyang tengah dhaptar. Gumantung ing jawaban, sampeyan bakal bisa nerangake pilihan sampeyan. Aku sadurunge wis diterangake carane ArrayList lan LinkedList bisa ing siji kahanan utawa liyane. Ayo ngringkes iki kanthi nyelehake ing kaca sing padha kanggo mbandhingake: Nambah unsur (nambah)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

Ing ngisor iki: ing LinkedList, kerumitan algoritmik bakal mulai saka O(1) nganti O(n/2) . Tegese, luwih cedhak sisipan ing pungkasan utawa wiwitan dhaptar, luwih cepet. Ing wektu sing padha, kanggo ArrayList kisaran saka O (1) kanggo O (n) : sing luwih cedhak sisipan kanggo mburi dhaftar, sing luwih cepet. Nyetel unsur (set) Operasi iki nulis unsur menyang posisi sing ditemtokake ing dhaptar, nimpa sing sadurunge, yen ana. Ing LinkedList, operasi iki bakal padha karo nambah, amarga Kesulitan paling gedhe ing kene yaiku nemokake unsur kasebut. Nulis ulang unsur bakal ditindakake kanthi nulis ulang sepasang pranala, dadi ing kene uga kompleksitas algoritmik saka O(1) nganti O(n/2) gumantung saka jarak posisi saka mburi utawa wiwitan dhaptar. Ing wektu kasebut, sel sing dibutuhake bakal ditemokake ing ArrayList kanggo operasi indeks iki, lan unsur anyar bakal ditulis. Panelusuran indeks, kaya operasi iki, nduweni kerumitan algoritma O(1) . Njupuk unsur dening indeks (njaluk) Ing LinkedList, njupuk unsur bakal kelakon miturut asas padha nelusuri operasi liyane - gumantung ing kadohan saka mburi utawa wiwitan, i.e. saka O(1) nganti O(n/2) . Ing ArrayList , kaya sing dakkandhakake sadurunge, nemokake unsur ing array kanthi indeks duwe kompleksitas O (1) . Mbusak unsur kanthi indeks (mbusak) Kanggo LinkedList, prinsip operasi uga bisa digunakake ing kene: pisanan unsur ditemokake, banjur pranala ditindih - tetanggan unsur kasebut wiwit saling ngrujuk, ilang referensi kanggo unsur iki, sing salajengipun bakal dibusak dening tukang sampah. Tegese, kerumitan algoritma isih padha - saka O(1) nganti O(n/2) . Kanggo ArrayList , operasi iki luwih mirip karo operasi nambah unsur anyar (nambah). Pisanan, unsur sing dibutuhake ditemokake - O (1) , banjur dibusak, lan kabeh unsur sing ana ing sisih tengen dipindhah siji unit ing sisih kiwa kanggo nutup celah sing diasilake. Operasi mbusak bakal duwe kerumitan algoritma sing padha karo operasi tambah - saka O(1) nganti O(n) . Sing luwih cedhak pambusakan menyang mburi dhaptar, kerumitan algoritma sing kurang. Bener, iki kabeh operasi utama. Ayo kula ngelingake sampeyan: nalika mbandhingake rong dhaptar kasebut, sampeyan kudu njlentrehake apa kahanan tartamtu sing diomongake, banjur sampeyan bisa mangsuli pitakon kanthi jelas.

90. Kepiye ArrayList beda karo HashSet?

Yen ArrayList lan LinkedList bisa dibandhingake babagan operasi - sing luwih apik - mula ora gampang kanggo mbandhingake ArrayList karo HashSet , amarga iki koleksi sing beda. Sampeyan bisa mbandhingake siji sajian manis karo liyane, nanging bakal bisa digunakake karo sajian daging - beda banget. Nanging, aku bakal nyoba menehi sawetara beda ing antarane:

• ArrayList ngleksanakake antarmuka List , nalika HashSet ngleksanakake antarmuka Set ;

• Ing ArrayList, akses bisa kanthi indeks unsur: operasi get duwe kerumitan algoritma O (1) , lan ing HashSet unsur sing dibutuhake mung bisa dipikolehi kanthi brute force, lan iki saka O (1) nganti O (n) ;

• ArrayList ngidini unsur duplikat. Ing HashSet, kabeh unsur unik: nambahake unsur menyang HashSet sing analoge wis ana ing koleksi ora bakal bisa digunakake (duplikat dicenthang nggunakake kode hash, mula jenenge koleksi iki);

• ArrayList diimplementasikake nggunakake array internal, lan HashSet diimplementasikake nggunakake HashMap internal ;

• ArrayList njaga urutan sisipan unsur, dene HashSet minangka set sing ora diurutake lan ora njaga urutan unsur;

• ArrayList ngidini sawetara nilai kosong (null), mung siji nilai null bisa dilebokake menyang HashSet (sawise kabeh, keunikan saka unsur).

91. Apa sebabe ana macem-macem implementasi array dinamis ing Jawa?

Inggih, iki luwih saka pitakonan filosofis. Ya, kenapa dheweke nggawe macem-macem teknologi anyar? Kanggo comfort. Bener, padha karo akeh implementasi array dinamis. Ora ana sing bisa diarani paling apik utawa becik. Saben duwe kauntungan ing sawetara kahanan tartamtu. Lan tugas kita yaiku ngerti bedane, kekuwatan / kelemahane: supaya bisa nggunakake sing paling cocog ing kahanan sing bener.

92. Yagene ana macem-macem implementasine panyimpenan nilai kunci ing Jawa?

Ing kene kahanane padha karo implementasi array dinamis. Ora ana sing paling apik: saben duwe kekuwatan lan kelemahane. Lan kita, mesthi, kudu ngoptimalake kekuwatan kita. Conto: paket concurrent, sing ngemot akeh teknologi multi-threaded, duwe koleksi Concurrent dhewe . ConcurrentHashMap padha duwe kauntungan ing safety saka karya multi-Utas karo data dibandhingake karo HashMap biasa , nanging ing lingkungan non-multithreaded ilang kacepetan. Inggih, implementasine, sing ora paling kuat ing kahanan apa wae, mboko sithik mandheg digunakake. Conto: Hashtable , sing asline dimaksudake dadi HashMap sing aman kanggo thread , nanging ConcurrentHashMap ngluwihi kinerja ing lingkungan multi-threaded, lan pungkasane Hashtable dilalekake lan ora digunakake maneh.

93. Carane ngurutake kumpulan unsur?

Wangsulan: Bab ingkang pisanan kanggo ngomong iku kelas unsur koleksi kudu ngleksanakake antarmuka Comparable lan cara compareTo sawijining . Utawa sampeyan butuh kelas sing ngetrapake Comaprator kanthi metode komparator . Sampeyan bisa maca liyane babagan ing kirim iki . Loro-lorone cara nemtokake cara obyek saka jinis tartamtu kudu dibandhingake. Nalika ngurutake, iki penting banget, amarga sampeyan kudu ngerti prinsip sing bisa dibandhingake karo unsur kasebut. Cara utama kanggo nindakake iki yaiku ngleksanakake Comparable , dileksanakake langsung ing kelas sing pengin diurutake. Ing wektu sing padha, panggunaan Comparator kurang umum. Ayo dadi ngomong sampeyan nggunakake kelas saka sawetara perpustakaan sing ora duwe implementasine Comparable , nanging sampeyan kudu ngurutake piye wae. Tanpa bisa ngganti kode saka kelas iki (kajaba ndawakake iku), sampeyan bisa nulis implementasine saka Comparator , kang nuduhake ing asas apa sampeyan pengin mbandhingaké obyek saka kelas iki. Lan conto liyane. Contone, sampeyan butuh prinsip sing beda kanggo ngurutake obyek saka jinis sing padha, supaya sampeyan nulis sawetara Comparator sing digunakake ing kahanan sing beda. Minangka aturan, akeh kelas metu saka kothak wis ngleksanakake antarmuka Comparable - padha String . Bener, nalika nggunakake, sampeyan ora kudu kuwatir babagan cara mbandhingake. Sampeyan mung njupuk lan nggunakake. Cara pisanan lan paling jelas yaiku nggunakake koleksi jinis TreeSet utawa TreeMap , sing nyimpen unsur ing urutan sing wis diurutake miturut komparator kelas unsur. Elinga yen TreeMap ngurutake kunci, nanging dudu nilai. Yen sampeyan nggunakake implementasi Comparator tinimbang Comparable , sampeyan kudu ngirim obyek kasebut menyang konstruktor koleksi nalika digawe:

TreeSet treeSet = new TreeSet(customComparator);

Nanging kepiye yen sampeyan duwe jinis koleksi sing beda? Carane ngurutake? Ing kasus iki, cara liya saka kelas sarana Koleksi cocok - cara sort() . Iku statis, dadi sampeyan mung perlu jeneng kelas lan cara kanggo ngirim dhaptar sing dibutuhake. Tuladhane:

Collections.sort(someList);

Yen sampeyan ora nggunakake Comparable , nanging implementasine saka Comparator , sampeyan kudu pass minangka parameter kapindho:

Collections.sort(someList, customComparator);

Akibaté, urutan internal saka unsur dhaftar liwati bakal diganti: bakal diurutake miturut komparator unsur. Aku Wigati sing dhaftar ditransfer saka unsur kudu mutable, i.e. bisa diowahi, yen cara kasebut ora bisa digunakake lan UnsupportedOperationException bakal dibuwang . Minangka cara katelu , sampeyan bisa nggunakake operasi Stream sort , sing ngurutake unsur koleksi yen implementasine Comparable digunakake :

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

yen komparator :

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

Sampeyan bisa maca liyane babagan Stream ing artikel iki . Cara kaping papat yaiku kanthi manual ngleksanakake sorting, kayata bubble sort utawa merge sort .

ClassObject. Podo karo lan HashCode

94. Andharan ringkes babagan objek kelas ing basa Jawa

Ing bagean kapindho analisis, kita wis ngomong babagan metode kelas Obyek , lan aku bakal ngelingake yen kelas Obyek minangka leluhur kabeh kelas ing Jawa. Wis 11 cara, sing, miturut, diwarisake dening kabeh kelas. Informasi babagan kabeh 11 cara bisa ditemokake ing bagean kapindho diskusi.

95. Apa Equals lan HashCode digunakake ing Jawa?

hashCode () minangka cara saka kelas Obyek sing diwarisake dening kabeh kelas. Tugase yaiku ngasilake sawetara nomer sing nggambarake obyek tartamtu. Conto nggunakake metode iki yaiku nggunakake HashMap ing obyek utama kanggo nemtokake kode hash lokal, sing bakal nemtokake sel array internal (ember) ing ngendi pasangan kasebut bakal disimpen. Kita ngomong kanthi rinci babagan karya HashMap ing bagean 9 analisis , mula kita ora bakal mikir babagan iki. Uga, minangka aturan, cara iki digunakake ing witjaksono () cara minangka salah siji saka alat utama kanggo nemtokake identitas obyek. witjaksono () iku sawijining cara saka kelas Obyek sing proyek kanggo mbandhingaké obyek lan nemtokake apa padha utawa ora. Cara iki digunakake ing endi wae ing ngendi kita kudu mbandhingake obyek, amarga perbandingan biasa nggunakake == ora cocok kanggo obyek, amarga mbandhingake mung pranala menyang wong-wong mau.

96. Marang kita bab kontrak antarane Equals lan HashCode ing Jawa?

Wangsulan: Bab ingkang pisanan aku bakal ngomong iku kanggo witjaksono () lan hashCode () cara kanggo bisa bener , padha kudu ditindhes bener. Sawise iki, dheweke kudu ngetutake aturan kasebut:

• obyek podho rupo kanggo kang comparison liwat witjaksono bali bener kudu duwe kode hash podho rupo;
• obyek karo kode hash padha bisa uga ora tansah padha.

Ing titik iki kita bakal ngaso nganti bagean sabanjure analisis!