Turinys[Slėpti][Rodyti]
- 1. Kaip apibrėžiate masyvą?
- 2. Dinaminiai masyvai: kas tai yra? Kuo jie skiriasi nuo pagrindinių masyvų?
- 3. Kaip masyvas ir žodynas skiriasi vienas nuo kito?
- 4. Išvardykite kai kuriuos masyvų privalumus ir trūkumus.
- 5. Ką reiškia „retas masyvas“?
- 6. Kada pasirinktumėte susietą sąrašą, o ne masyvą?
- 7. Kuo indeksuotas masyvas skiriasi nuo asociatyvaus masyvo?
- 8. Kokie yra Heap pranašumai prieš surūšiuotus masyvus?
- 9. Ar galime nustatyti, kad masyvo dydis būtų neigiamas?
- 10. Kaip rasti trūkstamą sveikąjį skaičių masyve nuo 1 iki 100?
- 11. Kaip rasti masyvo elemento indeksą?
- 12. Kaip galite atsikratyti konkretaus elemento iš masyvo?
- 13. Kaip galima patikrinti dviejų masyvų lygybę?
- 14. Kai kalbame apie masyvus, ką turite omenyje sakydami frazes „Dimensija“ ir „Apatinis indeksas“?
- Kodavimo interviu klausimai
- 15. Raskite porą masyve, turinčią nurodytą sumą
- 16. Dvejetainis masyvo rūšiavimas tiesiniu laiku
- 17. Raskite didžiausią dviejų indų sandaugą masyve.
- 18. Kaip perkelti visus masyvo nulius į pabaigą
- 19. Kaip surūšiuoti masyvą su dviem įrašais, kurie perjungiami viena operacija.
- 20. Kaip sujungti du surūšiuotus masyvus vietoje.
- 21. Kaip pertvarkyti prekių masyvą pakaitomis aukštoje ir žemoje pozicijoje?
- 22. Kaip pakeisti kiekvieną masyvo elementą nenaudojant dalybos operatoriaus kiekvieno masyvo elemento sandauga?
- 23. Raskite keisčiausią masyvo elementą logaritminiu laiku
- 24. Kaip gauti paskesnį didesnį elementą kiekvienam apskritimo masyvo elementui?
- 25. Rasti masyvo inversijų skaičių?
- 26. Kokia yra lietaus vandens gaudymo problema?
- Išvada
Kodavimo interviu yra DSA klausimų serija. Jei ruošiatės būsimam techniniam pokalbiui su FAANG ar kitu 1 lygio technologijų verslu, turėtumėte būti įgudę valdyti masyvus.
Daugumoje kodavimo interviu jis užima antrąją vietą po „Strings“. Masyvas yra susijusių duomenų elementų, laikomų atmintyje arti vienas kito, grupė.
Kadangi jie yra prijungti prie visų programavimo kalbų, tokių kaip C, C++, Java, Python, Perl ir Ruby, jie yra visur. Skaitykite toliau, kad sužinotumėte apie kai kuriuos praktikos kodavimo iššūkius ir interviu klausimus bei atsakymus, pagrįstus masyvais.
Šiame įraše „Python“ bus naudojamas kodavimo problemoms spręsti, nes juo paprasta naudotis, jis suprantamas ir daugeliui iš mūsų turi būti pažįstamas.
Pradėkime.
1. Kaip apibrėžiate masyvą?
- Susijusių duomenų tipų grupė yra masyvas.
- Masyvai visada yra fiksuoti.
- To paties tipo kintamąjį keliose vietose saugo masyvo objektai.
- Primityvūs tipai ir objektų nuorodos yra suderinami su juo.
2. Dinaminiai masyvai: kas tai yra? Kuo jie skiriasi nuo pagrindinių masyvų?
Didelis pranašumas yra automatinis mastelio keitimas, kurį suteikia dinaminiai masyvai (taip pat vadinami augančiais masyvais, keičiamo dydžio masyvais, keičiamais masyvais arba ArrayLists).
Visada turite iš anksto žinoti, kiek elementų bus saugoma jūsų masyve, nes masyvai yra fiksuoto dydžio. Kita vertus, dinaminis masyvas auga, kai į jį įtraukiate papildomų narių, todėl jums nereikia iš anksto žinoti tikslaus jo dydžio.
3. Kaip masyvas ir žodynas skiriasi vienas nuo kito?
Tai yra pagrindiniais dalykais pagrįsta interviu klausimų, kurie reguliariai užduodami, rinkinys. Toliau pateikiami pagrindiniai skirtumai tarp masyvų ir žodynų:
- Masyvas yra sutvarkytas panašių elementų sąrašas. Kita vertus, žodynas turi raktų ir reikšmių poras.
- Masyvo dydžiai gali keistis dinamiškai. Tokių dinamiškų idėjų žodynuose nėra.
- Prieš naudojant masyvą, reikia nurodyti jo dydį. Žodyno dydžių tinkinti nereikia.
- Jei norite išplėsti masyvo dydį, naudokite „Redim“ teiginį. Žodynuose elementas gali būti įtrauktas be deklaracijos.
4. Išvardykite kai kuriuos masyvų privalumus ir trūkumus.
Privalumai:
- Masyvai gali rūšiuoti kelis elementus vienu metu.
- kitas duomenų struktūros, pavyzdžiui, kaip krūvas, eiles, susietus sąrašus, medžius, grafikus ir kt., galima įdiegti masyve.
- Indeksas gali būti naudojamas norint pasiekti masyvo elementą.
Trūkumai:
- Masyvo dydis turi būti deklaruotas iš anksto. Tačiau masyvo deklaravimo metu galime nežinoti, kokio dydžio mums reikia.
- Masyvo struktūra yra statinė. Tai reiškia, kad masyvo dydis visada yra fiksuotas ir kad atminties paskirstymas negali būti padidintas ar sumažintas.
5. Ką reiškia „retas masyvas“?
Retas masyvas yra duomenų masyvas, kuriame yra daug įrašų su nulinėmis reikšmėmis. Priešingai, tankiame masyve yra daugumos elementų, kurių reikšmės skiriasi nuo nulio. Reto masyvo, kuris paverčia skaičius į objektus, indeksuose gali būti spragų. Palyginti su HashMap, jie yra efektyvesni atmintyje.
6. Kada pasirinktumėte susietą sąrašą, o ne masyvą?
Naudodami susietus sąrašus, o ne masyvus, apsvarstykite:
- Norint turėti atsitiktinę prieigą, nereikia jokių elementų.
- Jei laikinasis nuspėjamumas yra labai svarbus, jums reikia nuolatinio įterpimo ir pašalinimo iš sąrašo.
- Norint sukurti prioritetinę eilę, gali reikėti įdėti elementus sąrašo centre.
- Jūs neįsivaizduojate, kokio ilgio bus sąrašas. Jei masyvo dydis padidėja, turite iš naujo deklaruoti ir kopijuoti atmintį, kaip ir naudojant paprastus masyvus.
7. Kuo indeksuotas masyvas skiriasi nuo asociatyvaus masyvo?
Pagrindiniai skirtumai tarp asociatyvių ir indeksuotų masyvų yra išvardyti šioje lentelėje.
- Rakto-reikšmių pora tekstiniu arba skaitmeniniu formatu naudojama asociatyviniam masyvui rūšiuoti. Visi indeksuoto masyvo raktai yra skaitiniai ir kiekvienas raktas yra susietas su atskira reikšme.
- Asociaciniame masyve raktas gali būti eilutė. Indeksuotas masyvas su sveikųjų skaičių raktais, prasidedančiais nuo 0.
- Dviejų stulpelių lentelė imituoja asociatyvaus masyvo elgesį. Panašūs į vieno stulpelio lentelę, yra indeksuoti masyvai.
- Žemėlapiai yra asociatyvus masyvo tipas. Rodyklės masyvas nėra žemėlapis.
8. Kokie yra Heap pranašumai prieš surūšiuotus masyvus?
Pagrindinis pranašumas yra laiko efektyvumas naudojant „Heap over Sorted Arrays“. Nors krūvos operacijos yra greitesnės, masyvo rūšiavimas reikalauja daug laiko. Krūva gali atrasti mažiausią elementą daug greičiau, nei galima surūšiuoti masyvą.
Nurodytas skaičių rinkinys gali būti išdėstytas vienu iš dviejų būdų, naudojant surūšiuotus masyvus. Kita vertus, tam tikroje skaičių rinkinyje gali būti daugiau nei viena potenciali krūva.
9. Ar galime nustatyti, kad masyvo dydis būtų neigiamas?
Ne, negalime apibrėžti neigiamo sveikojo skaičiaus kaip masyvo dydžio. Jei paskelbsime, kompiliavimo laiko klaidos nebus. Tačiau vykdymo metu susidursime su NegativeArraySizeException.
10. Kaip rasti trūkstamą sveikąjį skaičių masyve nuo 1 iki 100?
Bendra serijų suma gali būti apskaičiuota taikant šią funkciją: n (n + 1) / 2
Ši funkcija veiks tik tuo atveju, jei masyve nėra dublikatų arba trūksta daugiau nei vieno sveikojo skaičiaus. Nesvarbu, ar masyve yra pasikartojančių elementų, galite rūšiuoti masyvą, kad pamatytumėte, ar yra lygiaverčių elementų.
11. Kaip rasti masyvo elemento indeksą?
Elemento indeksą galima rasti naudojant tiesinę arba dvejetainę paiešką. Kol aptiks reikiamo elemento atitiktį, linijinė paieškos funkcija perkelia kiekvieną masyvo elementą. Jis grąžina indeksą, kai nustato atitinkamą elementą. Vadinasi, tiesinės paieškos sudėtingumas laike yra O. (n). Tiek surūšiuotame, tiek nerūšiuotame masyve galima naudoti tiesinę paiešką.
Naudodami dvejetainę paiešką, kuri nuolat dalija masyvą per pusę, kol intervalo mediana atitinka reikiamą elementą ir pateikia indeksą, galite gauti elemento indeksą, jei masyvas surūšiuotas. Vadinasi, dvejetainės paieškos sudėtingumas laike yra O. (log n).
12. Kaip galite atsikratyti konkretaus elemento iš masyvo?
Kadangi negalite tiesiog ištrinti elementų iš pradinio masyvo, nes jie yra nustatyto dydžio fiksuoti rinkiniai, pašnekovas nori, kad galėtumėte pasiūlyti kitokį požiūrį ir išspręsti iškilusią problemą. Geriausias būdas yra sukurti naują masyvą, kad būtų pašalintas elementas. Šiame masyve galite kopijuoti elementus iš pirmojo masyvo ir įtraukti tik tą elementą, kurį norite ištrinti.
Kita strategija apima tikslinio elemento radimą masyve ir visų elementų, esančių dešinėje tikslinio elemento, eilės keitimą.
13. Kaip galima patikrinti dviejų masyvų lygybę?
Pirmiausia turite patikrinti dviejų pateiktų masyvų ilgius. Abiejų masyvų atitikimo elementai lyginami, kai jų ilgiai yra vienodi. Abu masyvai bus laikomi lygiais. jei kiekvienoje korespondencijoje kiekviena komponentų pora yra lygi. Taikant šį metodą nerekomenduojama tikrinti dviejų masyvų lygybės, jei masyvai yra dideli, nes tai užtruks daug laiko. Taip pat galite naudoti masyvų klasėje įeinantį metodą equals(), tačiau jei pašnekovas paprašys jūsų palyginti du masyvus nenaudojant integruotų metodų, šis būdas bus naudingas.
14. Kai kalbame apie masyvus, ką turite omenyje sakydami frazes „Dimensija“ ir „Apatinis indeksas“?
Masyvo „matmenys“ yra indeksų arba indeksų, reikalingų kiekvienam atskiram nariui identifikuoti, skaičius. Indeksai ir matmenys gali būti neaiškūs. Dimensija yra leidžiamų raktų diapazono aprašymas, o indeksas yra skaičius. Kiekvienam masyvo aspektui reikalingas tik vienas indeksas.
Pavyzdžiui, masyvas arr[10][5] turi du matmenis. Vienoje 10, kitoje 5 dydis. Norėdami išspręsti jo komponentus, jums reikia dviejų indeksų. Abu yra nuo 0 iki 4; vienas nuo 0 iki 9 imtinai.
Kodavimo interviu klausimai
15. Raskite porą masyve, turinčią nurodytą sumą
Pavyzdžiui,
Įvestis:
- skaičiai = [8, 7, 2, 5, 3, 1]
- taikinys = 10
Rezultatas:
- Rasta pora (8, 2)
- Or
- Rasta pora (7, 3)
Įvestis:
- skaičiai = [5, 2, 6, 8, 1, 9]
- taikinys = 12
Rezultatas:
- Pora nerasta
16. Dvejetainis masyvo rūšiavimas tiesiniu laiku
Rūšiuokite dvejetainį masyvą tiesiniu laiku ir fiksuotoje srityje. Išvestyje pirmiausia turi būti rodomi visi nuliai, tada visi vienetai.
Pavyzdžiui,
- Įvestis: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Išvestis: {0, 0, 0, 0, 1, 1, 1, 1}
Paprasčiausias būdas būtų apskaičiuoti bendrą masyvo 0 skaičių, tarkime, k, o tada pirmuosius k masyvo indeksus užpildyti 0, o likusius indeksus - 1. Kaip alternatyvą galime apskaičiuoti, kiek 1 yra iš viso masyve k, paskutinius k masyvo indeksus užpildykite 1, o likusius indeksus palikite užpildytus 0.
Pateiktas metodas turi O(n) laiko sudėtingumą ir nenaudoja papildomos saugyklos, kur n yra įvesties dydis.
17. Raskite didžiausią dviejų indų sandaugą masyve.
Raskite didžiausią dviejų skaičių sandaugą sveikųjų skaičių masyve.
Pagalvokite apie masyvą 10 3 5 6 2 kaip pavyzdį. (-10, -3) arba (5, 6) pora yra didžiausias produktas.
Galvoti apie kiekvieną elementų derinį ir išsiaiškinti jų produktą yra kvailas požiūris. Jei dabartinės poros sandauga yra didesnė už didžiausią iki šiol gautą produktą, atnaujinkite maksimalų produktą. Galutinio produkto komponentus spausdinkite paskutiniai.
Pirmiau pateikto sprendimo, kur n yra įvesties kiekis, laiko sudėtingumas yra O(n2) ir jis neužima daugiau vietos.
18. Kaip perkelti visus masyvo nulius į pabaigą
Perkelkite visus sveikųjų skaičių masyvo nulius iki galo. Atsakymas turėtų vengti naudoti nuolatinę erdvę ir išlaikyti santykinę masyvo komponentų tvarką.
Įvestis: {1,2,3,0,8,0,4,7}
Išvestis bus {1,2,3,8,4,7,0,0}
Įdėkite elementą į šią galimą masyvo vietą, jei dabartinis elementas nėra nulis. Užpildykite visus likusius indeksus 0, kai visi masyvo elementai bus apdoroti.
Ankstesnis sprendimas turi O(n) laiko sudėtingumą, kur n yra įvesties dydis.
19. Kaip surūšiuoti masyvą su dviem įrašais, kurie perjungiami viena operacija.
Rūšiuoti masyvą tiesiniu laiku, atsižvelgiant į du sukeistus elementus ir masyvą su visais jo elementais, išdėstytais didėjančia tvarka. Apsimeskite, kad masyve nėra dublikatų.
Įvestis:= [1,9,3,4,7,2] arba [9,3,7,2,1,4] arba [2,4,1,7,3,9]
Išvestis: = [1,2,3,4,7,9]
Pradedant nuo antrojo masyvo elemento, tikslas yra palyginti kiekvieną elementą su jo pirmtaku. Ginčo padėtis išsaugoma imant du rodykles x ir y.
Atnaujinkite x į ankstesnio elemento indeksą ir y į dabartinio elemento indeksą, jei pirmasis yra didesnis už pastarąjį. Atnaujinkite y į dabartinio elemento indeksą, jei paaiškėja, kad ankstesnis elementas yra didesnis už dabartinį elementą.
Galiausiai perjunkite elementus prie indeksų x ir y, kai baigsime apdoroti kiekvieną gretimų elementų porą.
Dėl to, kad aukščiau minėtas metodas atlieka tik vieną n dydžio įvesties masyvo nuskaitymą, jo sudėtingumas laike yra O(n). Sprendimui nereikia papildomos patalpos.
20. Kaip sujungti du surūšiuotus masyvus vietoje.
Sujunkite masyvų X[] ir Y[] elementus – po du surūšiuotus m ir n dydžio masyvus – išsaugodami rūšiavimo tvarką, ty užpildydami X[] pirmaisiais m mažiausiais elementais, o Y[] užpildydami likusius elementus.
Jei elementas masyve X[] jau yra tinkamoje padėtyje (ty toje, kuri yra mažiausia tarp likusių elementų), nepaisykite jo; kitu atveju pakeiskite jį mažiausiu elementu, kuris taip pat yra pirmasis Y[] narys. Norėdami išsaugoti rūšiavimo tvarką po sukeitimo, perkelkite elementą (dabar Y[0]) į tinkamą vietą Y[].
Pirmojo masyvo dydis yra m, o antrojo masyvo dydis yra n, o laiko sudėtingumas yra O(mn).
21. Kaip pertvarkyti prekių masyvą pakaitomis aukštoje ir žemoje pozicijoje?
Pertvarkykite sveikųjų skaičių masyvą taip, kad kiekvienas paskesnis narys būtų didesnis už ankstesnį ir paskesnį elementą. Tarkime, kad masyve nėra jokių pasikartojančių elementų.
Rūšiuoti masyvą arba naudoti papildomą erdvę nebūtina, kad būtų veiksmingas. Pradžioje planas yra antrasis masyvo narys ir padidės dviem kiekvienai ciklo iteracijai.
Sukeiskite komponentus, jei paskutinis elementas viršija pirmąjį. Panašiai perjunkite abu elementus, jei šis elementas yra didesnis nei dabartinis. Mes gausime norimą masyvą, atitinkantį nurodytus apribojimus ciklo pabaigoje.
22. Kaip pakeisti kiekvieną masyvo elementą nenaudojant dalybos operatoriaus kiekvieno masyvo elemento sandauga?
Nenaudodami padalijimo operatoriaus, kiekvieną sveikųjų skaičių masyvo elementą pakeiskite visų kitų elementų sandauga.
Linijiniame laike ir pastovioje erdvėje šiai problemai išspręsti galime panaudoti rekursiją. Sąvoka yra rekursyvus kiekvieno dešiniojo pogrupio elemento sandaugų skaičiavimas ir kairiojo pogrupio sandaugų perdavimas kaip funkcijos parametrai.
Laiko sudėtingumas yra O(n).
23. Raskite keisčiausią masyvo elementą logaritminiu laiku
Atsižvelgiant į sveikųjų skaičių masyvą, kuriame visi nariai, išskyrus vieną, turi lyginį atvejų skaičių, problema yra nustatyti, kiek kartų šis elementas pasirodo. Raskite nelyginį elementą logaritminiame laike ir pastovioje erdvėje, jei tie patys elementai masyve yra poromis ir niekada negali būti daugiau nei du tam tikro elemento atvejai iš eilės.
XOR operacija leidžia išspręsti šią problemą tiesiniu laiku. Tikslas yra XOR atlikti kiekvieną masyvo elementą. Po to, kai lyginiai elementai panaikina vienas kitą, lieka tik nelyginiai elementai.
Šią problemą netgi galima išspręsti per O(log(n)) laiką.
24. Kaip gauti paskesnį didesnį elementą kiekvienam apskritimo masyvo elementui?
Kitas didesnis kiekvieno elemento elementas apskrito sveikųjų skaičių masyve turėtų būti. Pirmasis didesnis sveikas skaičius po elemento x masyve yra tolesnis didesnis to elemento elementas.
Iš dešinės į kairę galime dirbti su masyvo elementais. Tikslas yra kiekvieno elemento x kilpa tol, kol arba krūvelė bus tuščia, arba ant jos bus aukštesnis elementas. Nustatykite kitą didesnį x elementą, kad jis būtų rodomas krūvos viršuje.
25. Rasti masyvo inversijų skaičių?
Raskite bendrą masyvo inversijų skaičių. Pora I j) vadinama masyvo A inversija, jei I j) ir (A[i] > A[j]). Turime suskaičiuoti kiekvieną jų porą masyve.
Suskaičiuoti visus masyvo narius, kurių yra mažiau nei jis dešinėje, ir pridėti rezultatą prie išvesties yra paprastas būdas.
Šis sprendimas turi O(n2) sudėtingumą, kur n yra įvesties dydis.
26. Kokia yra lietaus vandens gaudymo problema?
Daugiausiai vandens, kurį galima įstrigti tam tikrame strypų, kurių kiekvieno plotis yra po vieną vienetą, rinkinys yra žinomas kaip „lietaus sulaikymo“ problema.
Tikslas yra nustatyti aukščiausią juostą, kuri gali būti kiekvienos juostos kairėje ir dešinėje. Minimalus pirmaujančių juostų kairėje ir dešinėje pusėje, atėmus dabartinės juostos aukštį, yra vandens kiekis, kuris laikomas kiekvienos juostos viršuje.
Išvada
Palyginti su kitomis duomenų struktūros temomis, masyvai yra paprastesni. Norėdami atsakyti į masyvo interviu klausimus, turite iš esmės suprasti masyvus.
Turėtumėte išsamiai peržiūrėti masyvų pagrindus, įskaitant masyvo operacijas (nuo masyvo deklaravimo / kūrimo iki masyvo elementų prieigos / modifikavimo), taip pat programavimo koncepcijas, tokias kaip kilpos, rekursija ir pagrindiniai operatoriai, kad galėtumėte sėkmingai atsakyti į masyvo interviu klausimus. Visiškai pripažinkite problemą.
Jei turite klausimų, turėtumėte paprašyti paaiškinimo. Pagalvokite apie problemos padalijimą į lengviau valdomas dalis. Prieš pradėdami programuoti, įsitikinkite, kad turite omenyje algoritmą; užsirašykite arba vizualizuokite struktūrinėje schemoje. tada pradėkite rašyti kodą.
Palikti atsakymą