Sisällysluettelo[Piilottaa][Näytä]
- 1. Miten määrität taulukon?
- 2. Dynaamiset taulukot: mitä ne ovat? Mikä erottaa ne perustaulukoista?
- 3. Miten taulukko ja sanakirja eroavat toisistaan?
- 4. Listaa joitakin taulukoiden etuja ja haittoja.
- 5. Mihin "Sparse Array" viittaa?
- 6. Milloin valitsisit linkitetyn luettelon taulukon sijaan?
- 7. Mikä erottaa indeksoidun taulukon assosiatiivisesta taulukosta?
- 8. Mitä etuja Heapilla on lajiteltuihin matriisiin verrattuna?
- 9. Voimmeko määrittää taulukon koon negatiiviseksi?
- 10. Kuinka paikannat puuttuvan kokonaisluvun 1-100 alkioisesta taulukosta?
- 11. Kuinka löydät taulukon elementin indeksin?
- 12. Kuinka voit poistaa tietyn elementin taulukosta?
- 13. Kuinka kahden taulukon yhtäläisyys voidaan varmistaa?
- 14. Kun keskustelemme taulukoista, mitä tarkoitat ilmauksilla "ulottuvuus" ja "alaindeksi"?
- Koodaushaastattelukysymykset
- 15. Etsi pari taulukosta, jolla on määritetty summa
- 16. Binääritaulukkolajittelu lineaarisella ajalla
- 17. Etsi taulukon suurin kahden innen tulo.
- 18. Kuinka siirtää kaikki taulukon nollat loppuun
- 19. Kuinka lajitella matriisi, jossa on kaksi merkintää, jotka vaihdetaan yhdellä toiminnolla.
- 20. Kuinka yhdistää kaksi lajiteltua taulukkoa paikoilleen.
- 21. Kuinka järjestää uudelleen joukko tuotteita vuorotellen korkeisiin ja alhaisiin paikkoihin?
- 22. Miten taulukon jokainen elementti korvataan taulukon jokaisen elementin tulolla ilman jakooperaattoria?
- 23. Etsi taulukon pariton elementti logaritmisessa ajassa
- 24. Kuinka saada seuraava isompi elementti jokaiselle pyöreän taulukon elementille?
- 25. Löytääkö taulukon inversiomäärä?
- 26. Mikä on sadeveden kiinnijäämisongelma?
- Yhteenveto
Koodaushaastattelut sisältävät joukon DSA-kysymyksiä. Sinun tulee olla taitava taulukoiden kanssa, jos valmistaudut tulevaan tekniseen haastatteluun FAANG:n tai muun tason 1 teknologiayrityksen kanssa.
Useimmissa koodaushaastatteluissa se on toisella sijalla Stringsin jälkeen. Taulukko on joukko toisiinsa liittyviä tietoelementtejä, joita pidetään lähellä toisiaan muistissa.
Koska ne ovat yhteydessä kaikkiin ohjelmointikieliin, kuten C, C++, Java, Python, Perl ja Ruby, niitä on kaikkialla. Jatka lukemista saadaksesi käytännön koodauksen haasteita ja haastattelukysymyksiä ja vastauksia taulukoiden perusteella.
Pythonia käytetään tässä viestissä koodausongelmien ratkaisemiseen, koska se on helppokäyttöinen, ymmärrettävä ja sen on oltava tuttu useimmille meistä.
Aloitetaanpa.
1. Miten määrität taulukon?
- Joukko toisiinsa liittyviä tietotyyppejä on taulukko.
- Taulukot ovat aina kiinteitä.
- Samanlainen muuttuja on tallennettu useisiin paikkoihin taulukkoobjektien avulla.
- Primitiivityypit ja objektiviittaukset ovat molemmat yhteensopivia sen kanssa.
2. Dynaamiset taulukot: mitä ne ovat? Mikä erottaa ne perustaulukoista?
Automaattinen skaalaus, jonka dynaamiset taulukot (jota kutsutaan myös Javassa kasvatettaviksi taulukoiksi, muutettavat taulukot, muutettavat taulukot tai ArrayLists) tarjoavat, on merkittävä etu.
Sinun on aina tiedettävä etukäteen, kuinka monta elementtiä taulukkosi tallentaa, koska taulukoilla on kiinteä koko. Dynaaminen matriisi puolestaan kasvaa, kun lisäät siihen jäseniä, joten sinun ei tarvitse tietää sen tarkkaa kokoa etukäteen.
3. Miten taulukko ja sanakirja eroavat toisistaan?
Tämä on perustietoihin perustuva joukko haastattelukysymyksiä, joita kysytään säännöllisesti. Seuraavat ovat tärkeimmät erot taulukoiden ja sanakirjojen välillä:
- Taulukko on järjestetty luettelo samankaltaisista kohteista. Sanakirjassa taas on avainarvopareja.
- Taulukkokoot voivat muuttua dynaamisesti. Tällaisia dynaamisia ideoita ei ole sanakirjoissa.
- Ennen taulukon käyttöä sen koko on määritettävä. Sanakirjan kokoja ei tarvitse mukauttaa.
- Käytä Redim-käskyä, jos haluat laajentaa taulukon kokoa. Sanakirjoissa elementti voidaan lisätä ilman ilmoitusta.
4. Listaa joitakin taulukoiden etuja ja haittoja.
edut:
- Taulukot voivat lajitella useita elementtejä samanaikaisesti.
- Muut Tietorakenteet, kuten pinot, jonot, linkitetyt luettelot, puut, kaaviot jne., voidaan toteuttaa taulukossa.
- Indeksiä voidaan käyttää taulukon elementin saavuttamiseen.
Haitat:
- Matriisin koko on ilmoitettava etukäteen. Taulukon määrityshetkellä emme kuitenkaan ehkä ole tietoisia tarvitsemamme koosta.
- Taulukon rakenne on staattinen. Se tarkoittaa, että taulukon koko on aina kiinteä ja että muistin varausta ei voida lisätä tai vähentää.
5. Mihin "Sparse Array" viittaa?
Harva taulukko on tietojoukko, jossa on paljon merkintöjä nolla-arvoilla. Sitä vastoin tiheä taulukko sisältää suurimman osan kohteistaan nollasta poikkeavilla arvoilla. Numerot objekteiksi muuntavan harvan taulukon indeksit voivat sisältää aukkoja. HashMapiin verrattuna ne ovat muistitehokkaampia.
6. Milloin valitsisit linkitetyn luettelon taulukon sijaan?
Kun käytät linkitettyjä luetteloita taulukoiden sijaan, ota huomioon:
- Et tarvitse mitään elementtejä satunnaiskäyttöön.
- Kun ajallinen ennustettavuus on välttämätöntä, tarvitset jatkuvasti lisäyksiä ja poistoja luettelosta.
- Jotta voit luoda prioriteettijonon, sinun on ehkä asetettava kohteita luettelon keskelle.
- Sinulla ei ole aavistustakaan kuinka pitkä lista on. Jos taulukon koko kasvaa, sinun täytyy ilmoittaa uudelleen ja kopioida muisti, kuten yksinkertaisissa taulukoissa.
7. Mikä erottaa indeksoidun taulukon assosiatiivisesta taulukosta?
Ensisijaiset erot assosiatiivisten ja indeksoitujen taulukoiden välillä on lueteltu seuraavassa taulukossa.
- Assosiatiivisen taulukon lajittelemiseen käytetään teksti- tai numeromuodossa olevaa avain-arvo-paria. Indeksoidun taulukon avaimet ovat kaikki numeerisia, ja jokainen avain on yhdistetty erilliseen arvoon.
- Assosiatiivisessa taulukossa avain voi olla merkkijono. Indeksoitu taulukko, jossa kokonaislukuavaimet alkavat 0:sta.
- Kaksisarakkeinen taulukko jäljittelee assosiatiivisen taulukon käyttäytymistä. Kuten yksisarakkeisessa taulukossa, ovat indeksoidut taulukot.
- Kartat ovat assosiatiivinen taulukkotyyppi. Hakemistotaulukko ei ole kartta.
8. Mitä etuja Heapilla on lajiteltuihin matriisiin verrattuna?
Keon yli lajiteltujen taulukoiden käytön aikatehokkuus on tärkein etu. Vaikka kasatoiminnot ovat nopeampia, taulukon lajittelu vaatii paljon aikaa. Kasa löytää pienimmän elementin huomattavasti nopeammin kuin taulukko voidaan lajitella.
Tietty numerokokoelma voidaan järjestää kahdella tavalla käyttämällä lajiteltuja taulukoita. Toisaalta tietyllä numerojoukolla voi olla useampi kuin yksi potentiaalinen kasa.
9. Voimmeko määrittää taulukon koon negatiiviseksi?
Ei, emme voi määrittää negatiivista kokonaislukua taulukon kokoiseksi. Käännösaikavirhettä ei tapahdu, jos ilmoitamme. Ajon aikana kohtaamme kuitenkin NegativeArraySizeExceptionin.
10. Kuinka paikannat puuttuvan kokonaisluvun 1-100 alkioisesta taulukosta?
Sarjan kokonaissumma voidaan laskea käyttämällä seuraavaa funktiota: n (n + 1) / 2
Tämä toiminto toimii vain, jos taulukossa ei ole kaksoiskappaleita tai siitä puuttuu useampi kuin yksi kokonaisluku. Riippumatta siitä, onko taulukossa päällekkäisiä elementtejä, voit lajitella taulukon nähdäksesi, onko olemassa vastaavia elementtejä.
11. Kuinka löydät taulukon elementin indeksin?
Elementin indeksi voidaan löytää lineaarisella tai binäärihaulla. Kunnes se paikantaa vaaditun elementin osuman, lineaarinen hakutoiminto kiertää jokaisen taulukon elementin. Se palauttaa indeksin, kun se löytää vastaavan elementin. Tästä johtuen lineaarihaun ajallinen kompleksisuus on O. (n). Sekä lajiteltu että lajittelematon taulukko voivat käyttää lineaarihakua.
Käyttämällä binäärihakua, joka jakaa taulukon jatkuvasti kahtia, kunnes välin mediaani vastaa vaadittua elementtiä ja antaa indeksin, voit saada elementin indeksin, jos taulukko on lajiteltu. Näin ollen binäärihaun ajallinen kompleksisuus on O. (log n).
12. Kuinka voit poistaa tietyn elementin taulukosta?
Koska et voi yksinkertaisesti poistaa elementtejä alkuperäisestä taulukosta, koska ne ovat tietyn kokoisia kiinteitä joukkoja, haastattelija pyytää sinua ehdottamaan erilaista lähestymistapaa ja käsittelemään kysymyksen herättämää ongelmaa. Paras tapa toimia on tehdä uusi taulukko elementin poistamiseksi. Voit kopioida tämän taulukon ensimmäisen taulukon elementit ja sisällyttää vain sen elementin, jonka haluat poistaa.
Toinen strategia sisältää kohdeelementin etsimisen taulukosta ja sen jälkeen käänteisen kaikkien kohdeelementin oikealla puolella olevien kohteiden järjestyksen.
13. Kuinka kahden taulukon yhtäläisyys voidaan varmistaa?
Sinun on ensin tarkistettava kahden tarjotun taulukon pituudet. Molempien taulukoiden vastaavia kohteita verrataan, kun niiden pituudet ovat yhtä suuret. Näitä kahta taulukkoa pidetään samanarvoisina. jos jokainen komponenttipari jokaisessa vastaavuudessa on yhtä suuri. Tätä lähestymistapaa ei suositella tarkistamaan kahden taulukon yhtäläisyyttä, jos taulukot ovat kooltaan suuria, koska se vie paljon aikaa. Voit käyttää myös Arrays-luokkaan sisältyvää equals()-menetelmää, mutta jos haastattelija pyytää sinua vertailemaan kahta taulukkoa käyttämättä sisäänrakennettuja menetelmiä, tämä tapa on hyödyllinen.
14. Kun keskustelemme taulukoista, mitä tarkoitat ilmauksilla "ulottuvuus" ja "alaindeksi"?
Taulukon "ulottuvuus" on kunkin yksittäisen jäsenen tunnistamiseen tarvittavien indeksien tai alaindeksien lukumäärä. Alaindeksit ja mitat voivat olla epäselviä. Dimensio on kuvaus sallittujen avainten valikoimasta, kun taas alaindeksi on numero. Jokaiselle taulukon ulottuvuudelle vaaditaan vain yksi alaindeksi.
Esimerkiksi taulukolla arr[10][5] on kaksi ulottuvuutta. Toisessa koot 10 ja toisessa 5. Sen osien käsittelemiseksi tarvitset kaksi alaindeksiä. Molemmat ovat välillä 0 ja 4; yksi välillä 0 ja 9, mukaan lukien.
Koodaushaastattelukysymykset
15. Etsi pari taulukosta, jolla on määritetty summa
Esimerkiksi
input:
- luvut = [8, 7, 2, 5, 3, 1]
- kohde = 10
lähtö:
- Pari löydetty (8, 2)
- Or
- Pari löydetty (7, 3)
input:
- luvut = [5, 2, 6, 8, 1, 9]
- kohde = 12
lähtö:
- Paria ei löydy
16. Binääritaulukkolajittelu lineaarisella ajalla
Lajittele binääritaulukko lineaarisessa ajassa ja kiinteällä alueella. Tulosteen tulee näyttää ensin kaikki nollat ja sitten kaikki ykköset.
Esimerkiksi
- Syöte: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Tulos: { 0, 0, 0, 0, 1, 1, 1, 1 }
Yksinkertainen tapa olisi laskea taulukon nollien kokonaismäärä, sanotaan k, ja täyttää sitten taulukon ensimmäiset k indeksit 0:lla ja loput indeksit 0:llä. Vaihtoehtona voisimme laskea, kuinka monta ykköstä on yhteensä taulukko k, täytä taulukon viimeiset k indeksit luvulla 1 ja jätä loput indeksit täytettyä 1:lla.
Annetulla lähestymistavalla on O(n)-ajan monimutkaisuus, eikä se käytä ylimääräistä tallennustilaa, missä n on syötteen koko.
17. Etsi taulukon suurin kahden innen tulo.
Etsi kahden luvun suurin tulo kokonaislukutaulukosta.
Ajattele taulukkoa 10 3 5 6 2 esimerkkinä. Pari (-10, -3) tai (5, 6) on korkein tuote.
Jokaisen elementtiyhdistelmän miettiminen ja niiden tuotteen selvittäminen on typerää lähestymistapaa. Jos nykyisen parin tulo on suurempi kuin tähän mennessä saatu maksimitulo, päivitä maksimitulo. Tulosta lopullisen tuotteen komponentit viimeiseksi.
Yllä olevan ratkaisun, jossa n on syötteen määrä, aikamonimutkaisuus on O(n2), eikä se vie enempää tilaa.
18. Kuinka siirtää kaikki taulukon nollat loppuun
Siirrä kaikki kokonaislukutaulukon nollat loppuun. Vastauksessa tulee välttää jatkuvan tilan käyttöä ja säilyttää taulukon komponenttien suhteellinen järjestys.
Syöttö: {1,2,3,0,8,0,4,7}
Tulos on {1,2,3,8,4,7,0,0}
Aseta elementti seuraavaan käytettävissä olevaan kohtaan taulukossa, jos nykyinen elementti ei ole nolla. Täytä kaikki jäljellä olevat indeksit 0:lla, kun taulukon kohteet on käsitelty.
Edellisellä ratkaisulla on O(n) aikakompleksisuus, jossa n on syötteen koko.
19. Kuinka lajitella matriisi, jossa on kaksi merkintää, jotka vaihdetaan yhdellä toiminnolla.
Lajittele taulukko lineaarisessa ajassa, kun on annettu kaksi vaihdettua kohdetta ja taulukko, jonka kaikki elementit on järjestetty nousevaan järjestykseen. Teeskentele, että taulukko ei sisällä kaksoiskappaleita.
Syöte:= [1,9,3,4,7,2] tai [9,3,7,2,1,4] tai [2,4,1,7,3,9]
Tulos: = [1,2,3,4,7,9]
Alkaen taulukon toisesta elementistä, tavoitteena on verrata jokaista elementtiä edeltäjäänsä. Kiistan sijainti tallennetaan ottamalla kaksi osoitinta, x ja y.
Päivitä x edellisen elementin indeksiin ja y nykyisen elementin indeksiin, jos edellinen on suurempi kuin jälkimmäinen. Päivitä y nykyisen elementin indeksiin, jos käy ilmi, että edellinen elementti on suurempi kuin nykyinen elementti.
Vaihtele lopuksi elementtejä indekseissä x ja y, kun olemme saaneet valmiiksi jokaisen viereisen elementtiparin käsittelyn.
Johtuen siitä, että edellä mainittu menetelmä suorittaa vain yhden skannauksen koon n syötetaulukosta, sen aikamonimutkaisuus on O(n). Ratkaisulle ei tarvita lisätilaa.
20. Kuinka yhdistää kaksi lajiteltua taulukkoa paikoilleen.
Yhdistä taulukoiden X[] ja Y[] alkiot – kaksi lajiteltua taulukkoa, joiden koko on m ja n – säilyttämällä lajiteltu järjestys, eli täyttämällä X[] ensimmäisellä m pienimmällä elementillä ja täyttämällä Y[] jäljellä olevat elementit.
Jos taulukon X[] elementti on jo oikeassa paikassa (eli siinä, joka on pienin jäljellä olevista elementeistä), jätä se huomiotta; muussa tapauksessa korvaa se pienimmällä elementillä, joka myös sattuu olemaan Y[]:n ensimmäinen jäsen. Jos haluat säilyttää järjestyksen vaihdon jälkeen, siirrä elementti (nyt kohdassa Y[0]) oikeaan paikkaan Y[]:ssä.
Ensimmäisen taulukon koko on m ja toisen taulukon koko on n ja aikamonimutkaisuus on O(mn).
21. Kuinka järjestää uudelleen joukko tuotteita vuorotellen korkeisiin ja alhaisiin paikkoihin?
Järjestä kokonaislukutaulukko uudelleen siten, että jokainen seuraava jäsen on suurempi kuin edellinen ja seuraava elementti. Oletetaan, että taulukko ei sisällä päällekkäisiä elementtejä.
Matriisin lajittelu tai lisätilan hyödyntäminen ei ole tehokkaan lähestymistavan kannalta välttämätöntä. Suunnitelma on aluksi taulukon toinen jäsen ja nousee kahdella jokaiselle silmukan iteraatiolle.
Vaihda komponentit, jos viimeinen elementti ylittää ensimmäisen. Vaihda samalla tavalla molempia kohteita, jos seuraava elementti on suurempi kuin nykyinen elementti. Saamme halutun taulukon, joka noudattaa määritettyjä rajoituksia silmukan lopussa.
22. Miten taulukon jokainen elementti korvataan taulukon jokaisen elementin tulolla ilman jakooperaattoria?
Ilman jako-operaattoria korvaa jokainen kokonaislukutaulukon elementti kaikkien muiden elementtien tulolla.
Lineaarisessa ajassa ja vakioavaruudessa voimme hyödyntää rekursiota tämän ongelman ratkaisemiseksi. Oikean alitaulukon kunkin elementin tulojen rekursiivinen laskeminen ja vasemman alitaulukon tulon välittäminen funktioparametreina on ajatus.
Aikamonimutkaisuus on O(n).
23. Etsi taulukon pariton elementti logaritmisessa ajassa
Kun otetaan huomioon kokonaislukutaulukko, jossa kaikilla paitsi yhdellä jäsenellä on parillinen määrä esiintymiä, ongelmana on määrittää, kuinka monta kertaa tämä yksi elementti esiintyy. Etsi pariton elementti logaritmisessa ajassa ja vakioavaruudessa, jos samat elementit esiintyvät pareittain taulukossa ja tietyn elementin esiintymiä ei voi koskaan olla enempää kuin kaksi rivissä.
XOR-operaation avulla voimme ratkaista tämän ongelman lineaarisessa ajassa. Tavoitteena on XOR XOR jokainen taulukon elementti. Vain parittomat elementit jäävät jäljelle sen jälkeen, kun parilliset elementit kumoavat toisensa.
Tämä ongelma voidaan ratkaista jopa O(log(n))-ajassa.
24. Kuinka saada seuraava isompi elementti jokaiselle pyöreän taulukon elementille?
Pyöreän kokonaislukutaulukon jokaisen elementin seuraava isompi elementti tulee sijoittaa. Ensimmäinen suurempi kokonaisluku taulukon elementin x jälkeen on tämän elementin seuraava suurempi alkio.
Oikealta vasemmalle voimme käsitellä taulukkokohteita. Tavoitteena on kiertää jokaista elementtiä x, kunnes pino on tyhjä tai sen päällä on korkeampi elementti. Aseta seuraava suurempi x:n elementti näkymään pinon päällä, kun se näkyy.
25. Löytääkö taulukon inversiomäärä?
Selvitä taulukon inversioiden kokonaismäärä. Paria I j) kutsutaan taulukon A inversioksi, jos I j) ja (A[i] > A[j]). Meidän on laskettava jokainen näiden pari taulukossa.
Kaikkien sitä pienempien taulukon jäsenten laskeminen sen oikealla puolella ja tuloksen lisääminen ulostuloon on yksinkertainen lähestymistapa.
Tämän ratkaisun monimutkaisuus on O(n2), jossa n on syötteen koko.
26. Mikä on sadeveden kiinnijäämisongelma?
Suurimman mahdollisen veden löytäminen tiettyyn yhden yksikön levyiseen tankosarjaan tunnetaan "sademäärän vangitsemisongelmana".
Tavoitteena on määrittää korkein palkki, joka voidaan sijoittaa kunkin palkin vasemmalle ja oikealle puolelle. Vasemmalla ja oikealla olevien johtavien palkkien vähimmäisarvo vähennettynä nykyisen palkin korkeudella on kunkin palkin päälle varastoitunut vesimäärä.
Yhteenveto
Muihin tietorakenneaiheisiin verrattuna taulukot ovat yksinkertaisempia. Jotta voit vastata haastattelukysymyksiin, sinulla on oltava perustavanlaatuinen käsitys taulukoista.
Sinun tulee tarkastella perusteellisesti taulukoiden perusteita, mukaan lukien taulukkooperaatiot (taulukon ilmoittamisesta/luomisesta taulukon kohteiden avaamiseen/muokkaukseen), sekä ohjelmointikonsepteja, kuten silmukat, rekursio ja perusoperaattorit, jotta voit vastata taulukon haastattelukysymyksiin. Tunnista ongelma kokonaan.
Sinun tulee pyytää selvennystä, jos sinulla on kysyttävää. Harkitse ongelman jakamista paremmin hallittavissa oleviin osiin. Varmista, että sinulla on algoritmi mielessä ennen kuin aloitat ohjelmoinnin; kirjoita se muistiin tai visualisoi se vuokaaviona. aloita sitten koodin kirjoittaminen.
Jätä vastaus