Sisukord[Peida][Näita]
- 1. Kuidas defineerida massiivi?
- 2. Dünaamilised massiivid: mis need on? Mis eristab neid põhimassiividest?
- 3. Kuidas massiiv ja sõnastik üksteisest erinevad?
- 4. Loetlege mõned massiivide eelised ja puudused.
- 5. Millele viitab "hõre massiiv"?
- 6. Millal valiksite massiivi asemel lingitud loendi?
- 7. Mis eristab indekseeritud massiivi assotsiatiivsest massiivist?
- 8. Millised eelised on Heapil sorteeritud massiivide ees?
- 9. Kas saame määrata massiivi suuruse negatiivseks?
- 10. Kuidas leida puuduv täisarv 1–100-elemendilises massiivis?
- 11. Kuidas leida massiivist elemendi indeks?
- 12. Kuidas saab massiivist konkreetsest elemendist lahti saada?
- 13. Kuidas saab kontrollida kahe massiivi võrdsust?
- 14. Kui arutleme massiivide üle, mida sa mõtled fraaside “Dimensioon” ja “Alamindeks” all?
- Kodeerimisintervjuu küsimused
- 15. Otsige massiivist paar, millel on määratud summa
- 16. Binaarse massiivi sorteerimine lineaarse ajaga
- 17. Leidke massiivist suurim kahe sisemise korrutis.
- 18. Kuidas nihutada kõik massiivi nullid lõppu
- 19. Kuidas sorteerida massiivi kahe kirjega, mis vahetatakse ühe toiminguga.
- 20. Kuidas ühendada kaks sorteeritud massiivi paigas.
- 21. Kuidas järjestada kaupade massiivi vaheldumisi kõrgetele ja madalatele positsioonidele?
- 22. Kuidas asendada massiivi iga elementi ilma jagamisoperaatorit kasutamata massiivi iga elemendi korrutisega?
- 23. Leidke massiivi kõige veidram element logaritmilise aja järgi
- 24. Kuidas saada ringikujulise massiivi iga elemendi jaoks järgnev suurem element?
- 25. Leida massiivi inversioonide arv?
- 26. Mis on vihmavee püüdmise probleem?
- Järeldus
Kodeerimisintervjuud sisaldavad mitmeid DSA küsimusi. Kui valmistute eelseisvaks tehniliseks intervjuuks FAANG-i või mõne muu Tier-1 tehnoloogiaettevõttega, peaksite olema osav massiividega.
Enamikus kodeerimisintervjuudes on see Stringsi järel teisel kohal. Massiiv on seotud andmeelementide rühmitus, mida hoitakse mälus üksteise vahetus läheduses.
Kuna need on ühendatud kõigi programmeerimiskeeltega, nagu C, C++, Java, Python, Perl ja Ruby, on neid kõikjal. Jätkake lugemist, et näha mõningaid kodeerimisprobleeme ning massiividel põhinevaid intervjuuküsimusi ja vastuseid.
Selles postituses kasutatakse kodeerimisprobleemide lahendamiseks Pythonit, kuna seda on lihtne kasutada, arusaadav ja see peab olema enamikule meist tuttav.
Alustagem.
1. Kuidas defineerida massiivi?
- Seotud andmetüüpide rühm on massiiv.
- Massiivid on alati fikseeritud.
- Sama tüüpi muutujaid salvestavad massiiviobjektid mitmes kohas.
- Sellega ühilduvad nii primitiivsed tüübid kui ka objektiviited.
2. Dünaamilised massiivid: mis need on? Mis eristab neid põhimassiividest?
Automaatne skaleerimine, mida dünaamilised massiivid (Javas nimetatakse ka kasvavateks massiivideks, muudetava suurusega massiivideks, muudetavateks massiivideks või massiiviloenditeks) pakuvad, on märkimisväärne eelis.
Peate alati teadma, kui palju elemente teie massiiv salvestab, kuna massiividel on kindel suurus. Dünaamiline massiiv seevastu kasvab, kui lisate sellele täiendavaid liikmeid, nii et te ei pea selle täpset suurust eelnevalt teadma.
3. Kuidas massiiv ja sõnastik üksteisest erinevad?
See on põhitõdedel põhinev rida intervjuuküsimusi, mida regulaarselt küsitakse. Järgmised on peamised erinevused massiivide ja sõnaraamatute vahel.
- Massiiv on sarnaste üksuste järjestatud loend. Sõnastikus on seevastu võtme-väärtuse paarid.
- Massiivi suurused võivad dünaamiliselt muutuda. Selliseid dünaamilisi ideid sõnaraamatutes ei ole.
- Enne massiivi kasutamist tuleb määrata selle suurus. Sõnastiku suurusi pole vaja kohandada.
- Kui soovite massiivi suurust laiendada, kasutage käsku Redim. Sõnaraamatutes saab elemendi lisada ilma deklaratsioonita.
4. Loetlege mõned massiivide eelised ja puudused.
Plussid:
- Massiivid võivad korraga sortida mitut elementi.
- Muu andmestruktuurid, nagu virnad, järjekorrad, lingitud loendid, puud, graafikud jne, saab rakendada massiivina.
- Indeksit saab kasutada massiivi elemendini jõudmiseks.
Puudused:
- Massiivi suurus tuleb eelnevalt deklareerida. Massiivi deklareerimise hetkel ei pruugi me aga nõutavast suurusest teadlikud olla.
- Massiivi struktuur on staatiline. See tähendab, et massiivi suurus on alati fikseeritud ja mälu eraldamist ei saa suurendada ega vähendada.
5. Millele viitab "hõre massiiv"?
Hõred massiiv on andmemassiivi, millel on palju nullväärtusega kirjeid. Seevastu tihe massiiv sisaldab enamikku nullist erineva väärtusega üksusi. Arve objektideks teisendava hõreda massiivi indeksid võivad sisaldada lünki. Võrreldes HashMapiga on need mälutõhusamad.
6. Millal valiksite massiivi asemel lingitud loendi?
Kui kasutate massiivide asemel lingitud loendeid, võtke arvesse järgmist.
- Juhusliku juurdepääsu saamiseks ei vaja te elemente.
- Kui ajaline prognoositavus on hädavajalik, peate loendist pidevalt lisama ja eemaldama.
- Prioriteetse järjekorra loomiseks peate võib-olla paigutama üksused loendi keskele.
- Teil pole õrna aimugi, kui pikk see nimekiri on. Kui massiivi suurus suureneb, peate mälu uuesti deklareerima ja dubleerima, nagu lihtsate massiivide puhul.
7. Mis eristab indekseeritud massiivi assotsiatiivsest massiivist?
Peamised erinevused assotsiatiivsete ja indekseeritud massiivide vahel on loetletud järgmises tabelis.
- Assotsiatiivse massiivi sortimiseks kasutatakse teksti- või numbrivormingus võtme-väärtuse paari. Indekseeritud massiivi võtmed on kõik numbrilised ja iga võti on ühendatud kindla väärtusega.
- Assotsiatiivses massiivis võib võti olla string. Indekseeritud massiiv täisarvuliste võtmetega, mis algavad 0-st.
- Kahe veeruga tabel jäljendab assotsiatiivse massiivi käitumist. Sarnaselt üheveerulise tabeliga on indekseeritud massiivid.
- Kaardid on assotsiatiivne massiiv. Indeksi massiiv ei ole kaart.
8. Millised eelised on Heapil sorteeritud massiivide ees?
Peamiseks eeliseks on kuhja kasutamise ajasäästlikkus sorteeritud massiivide üle. Kuigi kuhjatoimingud on kiiremad, nõuab massiivi sortimine palju aega. Hunnik suudab avastada väikseima elemendi tunduvalt kiiremini kui massiivi sorteerida.
Antud numbrite kogumit saab sorteeritud massiive kasutades korraldada kahel viisil. Teisest küljest võib antud arvude kogumi puhul olla rohkem kui üks potentsiaalne hunnik.
9. Kas saame määrata massiivi suuruse negatiivseks?
Ei, me ei saa defineerida negatiivset täisarvu massiivi suurusena. Kui deklareerime, siis kompileerimisaja viga ei esine. Käitusajal kohtame aga NegativeArraySizeExceptioni.
10. Kuidas leida puuduv täisarv 1–100-elemendilises massiivis?
Seeriate kogusumma saab arvutada järgmise funktsiooni abil: n (n + 1) / 2
See funktsioon töötab ainult siis, kui massiivil pole duplikaate või puudub rohkem kui üks täisarv. Olenemata sellest, kas massiivis on dubleerivaid elemente, saate massiivi sortida, et näha, kas seal on samaväärseid elemente.
11. Kuidas leida massiivist elemendi indeks?
Elemendi indeksi saab avastada lineaarse või binaarse otsingu abil. Kuni vajaliku elemendi vaste leidmiseni liigub lineaarne otsingufunktsioon üle iga massiivi elemendi. See tagastab indeksi, kui on leidnud sobiva elemendi. Järelikult on lineaarse otsingu ajaline keerukus O. (n). Nii sorteeritud kui ka sortimata massiiv võivad kasutada lineaarset otsingut.
Kasutades binaarotsingut, mis jagab massiivi pidevalt pooleks, kuni intervalli mediaan vastab vajalikule elemendile ja annab indeksi, saate elemendi indeksi, kui massiiv on sorteeritud. Järelikult on binaarse otsingu ajaline keerukus O. (log n).
12. Kuidas saab massiivist konkreetsest elemendist lahti saada?
Kuna elemente ei saa algsest massiivist lihtsalt kustutada, kuna need on kindlaksmääratud suurusega fikseeritud komplektid, soovib intervjueerija, et pakuksite välja teistsuguse lähenemisviisi ja lahendaksite küsimuse tõstatatud probleemi. Parim tegevusviis on elemendi kustutamiseks teha uus massiiv. Võite selle massiivi esimese massiivi elemente dubleerida ja lisada ainult selle elemendi, mida soovite kustutada.
Teine strateegia hõlmab sihtelemendi leidmist massiivist ja seejärel kõigi sihtelemendist paremal olevate üksuste järjekorra muutmist.
13. Kuidas saab kontrollida kahe massiivi võrdsust?
Esmalt peate kontrollima kahe pakutava massiivi pikkust. Mõlema massiivi sobivaid üksusi võrreldakse, kui nende pikkused on võrdsed. Neid kahte massiivi loetakse võrdseks. kui iga komponendi paar igas vastavuses on võrdne. Seda lähenemist ei soovitata kontrollida kahe massiivi võrdsust, kui massiivid on suured, kuna see võtab palju aega. Võite kasutada ka klassis Arrays sisalduvat meetodit equals(), kuid kui küsitleja palub teil võrrelda kahte massiivi ilma sisseehitatud meetodeid kasutamata, on see meetod kasulik.
14. Kui arutleme massiivide üle, mida sa mõtled fraaside “Dimensioon” ja “Alamindeks” all?
Massiivi "Dimensioon" on iga üksiku liikme tuvastamiseks vajalike indeksite või alamindeksite arv. Alamindeksid ja mõõtmed võivad olla ebaselged. Dimensioon on lubatud võtmete vahemiku kirjeldus, alaindeks aga arv. Iga massiivi dimensiooni jaoks on vaja ainult ühte alamindeksit.
Näiteks massiivil arr[10][5] on kaks mõõdet. Ühel suurus 10 ja teisel 5. Selle komponentide käsitlemiseks vajate kahte alamindeksit. Mõlemad on vahemikus 0 kuni 4; üks vahemikus 0 kuni 9, kaasa arvatud.
Kodeerimisintervjuu küsimused
15. Otsige massiivist paar, millel on määratud summa
Näiteks
sisend:
- numbrid = [8, 7, 2, 5, 3, 1]
- sihtmärk = 10
Väljund:
- Leitud paar (8, 2)
- Or
- Leitud paar (7, 3)
sisend:
- numbrid = [5, 2, 6, 8, 1, 9]
- sihtmärk = 12
Väljund:
- Paari ei leitud
16. Binaarse massiivi sorteerimine lineaarse ajaga
Sorteeri binaarmassiivi lineaarses ajas ja kindlas piirkonnas. Väljund peaks kõigepealt kuvama kõik nullid, seejärel kõik ühed.
Näiteks
- Sisend: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Väljund: { 0, 0, 0, 0, 1, 1, 1, 1 }
Lihtne lähenemine oleks arvutada massiivi nullide koguarv, näiteks k, ja seejärel täita massiivi esimesed k indeksit 0-ga ja ülejäänud indeksid 0-ga. massiiv k, täitke massiivi viimased k indeksit 1-ga ja ülejäänud indeksid täitke 1-ga.
Antud lähenemisviisil on O(n) ajaline keerukus ja see ei kasuta täiendavat salvestusruumi, kus n on sisendi suurus.
17. Leidke massiivist suurim kahe sisemise korrutis.
Leidke täisarvu massiivi kahe arvu suurim korrutis.
Mõelge näitena massiivile 10 3 5 6 2. Paar (-10, -3) või (5, 6) on kõrgeim toode.
Mõelda iga elementide kombinatsioonile ja välja mõelda nende toode on rumal lähenemine. Kui praeguse paari korrutis on suurem kui seni saadud maksimumkorrutis, värskendage maksimumkorrutist. Printige lõpptoote komponendid viimasena.
Ülaltoodud lahendus, kus n on sisendi kogus, on ajaliselt keerukusega O(n2) ja ei võta rohkem ruumi.
18. Kuidas nihutada kõik massiivi nullid lõppu
Liigutage kõik täisarvu massiivi nullid lõpuni. Vastus peaks vältima pideva ruumi kasutamist ja säilitama massiivi komponentide suhtelise järjekorra.
Sisend: {1,2,3,0,8,0,4,7}
Väljund on {1,2,3,8,4,7,0,0}
Kui praegune element ei ole null, asetage element massiivi järgmisele saadaolevale positsioonile. Kui massiivi üksused on töödeldud, täitke kõik ülejäänud indeksid 0-ga.
Eelneval lahendusel on O(n) ajaline keerukus, kus n on sisendi suurus.
19. Kuidas sorteerida massiivi kahe kirjega, mis vahetatakse ühe toiminguga.
Sorteerige massiiv lineaarse aja järgi, võttes arvesse kahte vahetatud üksust ja massiivi, mille kõik elemendid on järjestatud kasvavas järjekorras. Teeskle, et massiiv ei sisalda duplikaate.
Sisend:= [1,9,3,4,7,2] või [9,3,7,2,1,4] või [2,4,1,7,3,9]
Väljund: = [1,2,3,4,7,9]
Alustades massiivi teisest elemendist, on eesmärk võrrelda iga elementi selle eelkäijaga. Vaidluse asukoht salvestatakse kahe osuti x ja y abil.
Värskendage x eelmise elemendi indeksiga ja y praeguse elemendi indeksiga, kui esimene on teisest suurem. Värskendage y praeguse elemendi indeksile, kui selgub, et eelmine element on suurem kui praegune element.
Lõpuks vahetage elemendid indeksites x ja y, kui oleme lõpetanud iga külgneva elemendipaari töötlemise.
Tulenevalt asjaolust, et eelnimetatud meetod teostab n suuruse sisendmassiivi ainult ühe skaneerimise, on selle ajaline keerukus O(n). Lahenduse jaoks ei ole vaja täiendavat ruumi.
20. Kuidas ühendada kaks sorteeritud massiivi paigas.
Ühendage massiivide X[] ja Y[] üksused – kaks sorteeritud massiivi suurusega m ja n –, säilitades järjestatud järjestuse, st täites X[] esimese m väikseima elemendiga ja täites Y[] ülejäänud elemendid.
Kui massiivi X[] element on juba õigel positsioonil (st sellel, mis on ülejäänud elementide hulgast väikseim), jätke see tähelepanuta; vastasel juhul asenda see väikseima elemendiga, mis juhtub olema ka Y[] esimene liige. Sorditud järjestuse säilitamiseks pärast vahetamist viige element (nüüd Y[0] juures) õigesse asukohta Y[]-s.
Esimese massiivi suurus on m ja teise massiivi suurus on n ning ajaline keerukus on O(mn).
21. Kuidas järjestada kaupade massiivi vaheldumisi kõrgetele ja madalatele positsioonidele?
Korraldage täisarvude massiiv ümber nii, et iga järgnev liige oleks suurem kui eelmine ja järgnev element. Oletame, et massiiv ei sisalda dubleerivaid elemente.
Massiivi sortimine või lisaruumi kasutamine ei ole tõhusa lähenemisviisi jaoks vajalik. Plaan on alustuseks massiivi teine liige ja tõuseb iga tsükli iteratsiooni korral kahe võrra.
Vahetage komponendid, kui viimane element ületab esimest. Samamoodi vahetage mõlemat üksust, kui järgmine element on suurem kui praegune element. Me saame soovitud massiivi, mis vastab määratud piirangutele tsükli lõpus.
22. Kuidas asendada massiivi iga elementi ilma jagamisoperaatorit kasutamata massiivi iga elemendi korrutisega?
Ilma jagamisoperaatorit kasutamata asendage täisarvude massiivi iga element kõigi teiste elementide korrutisega.
Lineaarses ajas ja konstantses ruumis saame selle probleemi lahendamiseks kasutada rekursiooni. Parempoolse alamrea iga elemendi korrutiste rekursiivne arvutamine ja vasakpoolse alamrea korrutise edastamine funktsiooni parameetritena on mõte.
Ajaline keerukus on O(n).
23. Leidke massiivi kõige veidram element logaritmilise aja järgi
Arvestades täisarvu massiivi, milles kõigil peale ühe liikme on paarisarv esinemissagedust, on probleemiks määrata, mitu korda see üks element ilmub. Leia paaritu esinev element logaritmilises ajas ja konstantses ruumis, kui samad elemendid esinevad massiivi paarikaupa ja ühes reas ei saa kunagi olla rohkem kui kaks antud elemendi eksemplari.
XOR-operatsioon võimaldab meil selle probleemi lineaarse aja jooksul lahendada. Eesmärk on XOR-ida massiivi iga element. Ainult paaritu esinevad elemendid jäävad alles pärast seda, kui paaris esinevad elemendid üksteist tühistavad.
Seda probleemi saab lahendada isegi O(log(n)) ajaga.
24. Kuidas saada ringikujulise massiivi iga elemendi jaoks järgnev suurem element?
Ringikujulise täisarvu massiivi iga elemendi jaoks peaks asuma järgmine suurem element. Esimene suurem täisarv massiivi elemendi x järel on selle elemendi järgnev suurem element.
Paremalt vasakule võime töötada massiivi üksustega. Eesmärk on teha silmust iga elemendi x jaoks, kuni virn on tühi või selle peal on kõrgem element. Määrake järgmine suurem element x ilmuma virna ülaosas, kui see ilmub.
25. Leida massiivi inversioonide arv?
Leidke massiivi inversioonide koguarv. Paari I j) nimetatakse massiivi A inversiooniks, kui I j) ja (A[i] > A[j]). Peame loendama massiivi kõik nende paarid.
Kõigi sellest paremal asuvast väiksemate massiiviliikmete loendamine ja tulemuse lisamine väljundisse on lihtne lähenemine.
Sellel lahendusel on O(n2) keerukus, kus n on sisendi suurus.
26. Mis on vihmavee püüdmise probleem?
Antud ühe ühiku laiuse lattide komplekti võimalikult suure vee leidmist nimetatakse sademete püüdmise probleemiks.
Eesmärk on määrata kõrgeim riba, mille võib asetada igast ribast vasakule ja paremale. Vasakul ja paremal asuvate esiribade miinimum, millest on maha arvatud jooksva riba kõrgus, on vee kogus, mis on salvestatud iga riba peale.
Järeldus
Võrreldes teiste andmestruktuuri teemadega on massiivid lihtsamad. Et vastata massiiviintervjuu küsimustele, peab teil olema massiividest põhimõtteline arusaam.
Massiiviintervjuu küsimustele edukaks vastamiseks peaksite põhjalikult üle vaatama massiivide alused, sealhulgas massiivitoimingud (alates massiivi deklareerimisest/loomisest kuni massiivi üksustele juurdepääsu/muutmiseni), samuti programmeerimiskontseptsioone, nagu tsüklid, rekursioon ja põhioperaatorid. Tunnistage probleemi täielikult.
Kui teil on küsimusi, peaksite otsima selgitusi. Mõelge probleemi jagamisele paremini hallatavateks osadeks. Enne programmeerimise alustamist veenduge, et teil on algoritm meeles; kirjutage see üles või kujutage seda vooskeemina. seejärel alustage koodi kirjutamist.
Jäta vastus