Kazalo[Skrij][Pokaži]
- 1. Kako definirate matriko?
- 2. Dinamični nizi: kaj so? Kaj jih loči od osnovnih nizov?
- 3. Kako se matrika in slovar razlikujeta drug od drugega?
- 4. Naštejte nekaj prednosti in slabosti nizov.
- 5. Na kaj se nanaša "Sparse Array"?
- 6. Kdaj bi izbrali povezan seznam namesto niza?
- 7. Po čem se indeksirano polje razlikuje od asociativnega polja?
- 8. Kakšne prednosti ima Heap pred razvrščenimi nizi?
- 9. Ali lahko določimo, da je velikost niza negativna?
- 10. Kako poiščete manjkajoče celo število v nizu od 1 do 100 elementov?
- 11. Kako najdete indeks elementa v matriki?
- 12. Kako se lahko znebite določenega elementa iz matrike?
- 13. Kako lahko preverimo enakost dveh nizov?
- 14. Ko govorimo o nizih, kaj mislite z izrazoma »Dimenzija« in »Podpis«?
- Vprašanja za razgovor o kodiranju
- 15. Poiščite par v nizu, ki ima navedeno vsoto
- 16. Razvrščanje binarnih nizov z linearnim časom
- 17. Poiščite največji produkt z dvema celima v nizu.
- 18. Kako premakniti vse ničle matrike na konec
- 19. Kako razvrstiti matriko z dvema vnosoma, ki se zamenjata v eni operaciji.
- 20. Kako združiti dve razvrščeni matriki na mestu.
- 21. Kako preurediti niz predmetov na izmenično visoke in nizke položaje?
- 22. Kako nadomestiti vsak element matrike brez uporabe operatorja deljenja s produktom vsakega elementa v matriki?
- 23. Poiščite najbolj čuden element v nizu v logaritemskem času
- 24. Kako pridobiti naslednji večji element za vsak element v krožni matriki?
- 25. Najti število inverzij polja?
- 26. Kaj je problem zadrževanja deževnice?
- zaključek
Intervjuji o kodiranju vsebujejo vrsto vprašanj DSA. Če se pripravljate na prihajajoči tehnični razgovor s podjetjem FAANG ali drugim tehnološkim podjetjem prve stopnje, bi morali biti vešči uporabe nizov.
V večini intervjujev o kodiranju je na drugem mestu za nizi. Matrika je skupina povezanih podatkovnih elementov, ki se v pomnilniku hranijo v neposredni bližini drug drugega.
Ker so povezani z vsemi programskimi jeziki, kot so C, C++, Java, Python, Perl in Ruby, so povsod. Nadaljujte z branjem za nekaj izzivov pri kodiranju v praksi ter vprašanj in odgovorov na intervjuju na podlagi nizov.
Python bo v tej objavi uporabljen za reševanje težav s kodiranjem, ker je preprost za uporabo, razumljiv in mora biti znan večini od nas.
Začnimo.
1. Kako definirate matriko?
- Skupina povezanih tipov podatkov je matrika.
- Nizi so vedno fiksni.
- Ista vrsta spremenljivke je shranjena na več mestih v matričnih objektih.
- Primitivni tipi in reference objektov so združljivi z njim.
2. Dinamični nizi: kaj so? Kaj jih loči od osnovnih nizov?
Samodejno skaliranje, ki ga ponujajo dinamična polja (imenovana tudi rastoča polja, polja s spreminjanjem velikosti, spremenljiva polja ali ArrayLists v Javi), je pomembna prednost.
Vedno morate vedeti, koliko elementov bo vaša matrika shranila vnaprej, saj imajo matrike fiksno velikost. Po drugi strani pa dinamično polje raste, ko mu dodajate dodatne člane, zato vam ni treba vnaprej vedeti njegove natančne velikosti.
3. Kako se matrika in slovar razlikujeta drug od drugega?
To je niz vprašanj za intervjuje, ki temeljijo na osnovah in se redno postavljajo. Sledijo ključne razlike med nizi in slovarji:
- Niz je urejen seznam podobnih elementov. Po drugi strani pa ima slovar pare ključ-vrednost.
- Velikosti nizov se lahko dinamično spreminjajo. Takšne dinamične zamisli v slovarjih ne obstajajo.
- Pred uporabo matrike je treba določiti njeno velikost. Velikosti slovarja ni treba prilagajati.
- Uporabite stavek Redim, če želite razširiti velikost polja. V slovarjih je element mogoče dodati brez deklaracije.
4. Naštejte nekaj prednosti in slabosti nizov.
prednosti:
- Nizi lahko razvrstijo več elementov hkrati.
- Ostalo podatkovne strukture, kot so skladi, čakalne vrste, povezani seznami, drevesa, grafi itd., se lahko izvajajo v matriki.
- Za dosego elementa matrike je mogoče uporabiti indeks.
slabosti:
- Velikost matrike je treba deklarirati vnaprej. V trenutku deklaracije matrike pa se morda ne zavedamo velikosti, ki jo potrebujemo.
- Struktura polja je statična. To pomeni, da je velikost polja vedno fiksna in da dodelitve pomnilnika ni mogoče povečati ali zmanjšati.
5. Na kaj se nanaša "Sparse Array"?
Redka matrika je podatkovna matrika, ki ima veliko vnosov z vrednostmi nič. Nasprotno pa gosta matrika vsebuje večino elementov z vrednostmi, ki niso nič. Indeksi redke matrike, ki pretvarja števila v objekte, lahko vključujejo vrzeli. V primerjavi s HashMap so bolj pomnilniško učinkoviti.
6. Kdaj bi izbrali povezan seznam namesto niza?
Pri uporabi povezanih seznamov namesto nizov upoštevajte:
- Za naključni dostop ne potrebujete nobenih elementov.
- Kjer je bistvena časovna predvidljivost, potrebujete vstavljanje in odstranjevanje s seznama v stalnem času.
- Če želite ustvariti prednostno čakalno vrsto, boste morda morali elemente postaviti na sredino seznama.
- Ne veš, kako dolg bo seznam. Če se velikost polja poveča, morate ponovno deklarirati in podvojiti pomnilnik, tako kot pri preprostih nizih.
7. Po čem se indeksirano polje razlikuje od asociativnega polja?
Primarne razlike med asociativnimi in indeksiranimi nizi so navedene v naslednji tabeli.
- Par ključ-vrednost v besedilni ali številski obliki se uporablja za razvrščanje asociativnega polja. Vsi ključi indeksirane matrike so številski in vsak ključ je povezan z ločeno vrednostjo.
- V asociativnem nizu je lahko ključ niz. Indeksirana matrika s celimi ključi, ki se začnejo pri 0.
- Tabela z dvema stolpcema posnema vedenje asociativnega polja. Podobno kot tabela z enim stolpcem so indeksirana polja.
- Zemljevidi so vrsta asociativnega niza. Indeksni niz ni zemljevid.
8. Kakšne prednosti ima Heap pred razvrščenimi nizi?
Časovna učinkovitost uporabe kopice nad razvrščenimi nizi je ključna prednost. Čeprav so operacije kopice hitrejše, razvrščanje matrike zahteva veliko časa. Kup lahko odkrije najmanjši element bistveno hitreje, kot je mogoče razvrstiti niz.
Dano zbirko števil je mogoče urediti na enega od dveh načinov z uporabo razvrščenih nizov. Po drugi strani pa lahko za določeno zbirko števil obstaja več kot en potencialni kup.
9. Ali lahko določimo, da je velikost niza negativna?
Ne, negativnega celega števila ne moremo definirati kot velikost matrike. Če deklariramo, ne bo prišlo do napake med prevajanjem. Med izvajanjem pa bomo naleteli na izjemo NegativeArraySizeException.
10. Kako poiščete manjkajoče celo število v nizu od 1 do 100 elementov?
Vsoto niza je mogoče izračunati z uporabo naslednje funkcije: n (n + 1) / 2
Ta funkcija deluje samo, če matrika nima dvojnikov ali manjka več kot eno celo število. Ne glede na to, ali ima matrika podvojene elemente, lahko matriko razvrstite, da vidite, ali obstajajo enakovredni elementi.
11. Kako najdete indeks elementa v matriki?
Indeks elementa je mogoče odkriti z linearnim ali binarnim iskanjem. Dokler ne najde ujemanja zahtevanega elementa, funkcija linearnega iskanja preleti vsak element v matriki. Ko najde ujemajoči se element, vrne indeks. Posledično je časovna kompleksnost linearnega iskanja O. (n). Tako razvrščeni kot nerazvrščeni nizi lahko uporabljajo linearno iskanje.
Z uporabo binarnega iskanja, ki nenehno deli matriko na pol, dokler se mediana intervala ne ujema z zahtevanim elementom in zagotovi indeks, lahko dobite indeks elementa, če je matrika razvrščena. Posledično je časovna kompleksnost binarnega iskanja O. (log n).
12. Kako se lahko znebite določenega elementa iz matrike?
Ker ne morete preprosto izbrisati elementov iz prvotne matrike, saj gre za fiksne nize z določeno velikostjo, anketar išče, da predlagate drugačen pristop in se spopadete s problemom, ki ga postavlja vprašanje. Najboljši način ukrepanja je ustvariti novo matriko, da izbrišete element. Lahko podvojite elemente iz prve matrike v to matriko in vključite samo element, ki ga želite izbrisati.
Druga strategija vključuje iskanje ciljnega elementa v matriki in nato obračanje vrstnega reda vseh elementov, ki so desno od ciljnega elementa.
13. Kako lahko preverimo enakost dveh nizov?
Najprej morate preveriti dolžini obeh podanih nizov. Ujemajoči se elementi obeh nizov se primerjajo, ko sta njuni dolžini enaki. Dva niza bosta obravnavana kot enaka. če je vsak par komponent v vsaki korespondenci enak. Ta pristop ni priporočljiv za preverjanje enakosti dveh matrik, če sta matriki veliki, saj bo trajalo veliko časa. Uporabite lahko tudi metodo equals(), ki je vključena v razred Arrays, vendar bo ta način uporaben, če vas anketar prosi, da primerjate dve matriki brez uporabe vgrajenih metod.
14. Ko govorimo o nizih, kaj mislite z izrazoma »Dimenzija« in »Podpis«?
»Dimenzija« matrike je število indeksov ali indeksov, potrebnih za identifikacijo vsakega posameznega člana. Indeksi in dimenzije so lahko nejasni. Dimenzija je opis obsega dovoljenih ključev, medtem ko je indeks število. Za vsako dimenzijo polja je potreben samo en indeks.
Na primer, niz arr[10][5] ima dve dimenziji. Velikosti 10 na enem in 5 na drugem. Če želite obravnavati njegove komponente, potrebujete dva indeksa. Oba sta med 0 in 4; enega med 0 in vključno 9.
Vprašanja za razgovor o kodiranju
15. Poiščite par v nizu, ki ima navedeno vsoto
Na primer,
vhod:
- števila = [8, 7, 2, 5, 3, 1]
- cilj = 10
izhod:
- Najden par (8, 2)
- Or
- Najden par (7, 3)
vhod:
- števila = [5, 2, 6, 8, 1, 9]
- cilj = 12
izhod:
- Par ni bil najden
16. Razvrščanje binarnih nizov z linearnim časom
Razvrsti binarno polje v linearnem času in v fiksnem območju. Izhod bi moral najprej prikazati vse ničle, nato vse enote.
Na primer,
- Vnos: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Izhod: { 0, 0, 0, 0, 1, 1, 1, 1 }
Enostaven pristop bi bil izračunati skupno število 0 v matriki, recimo k, in nato zapolniti prvih k indeksov v matriki z 0 in preostale indekse z 1. Namesto tega lahko izračunamo, koliko 1 je skupno v matriko k, zadnjih k indeksov v matriki izpolnite z 1, preostale indekse pa pustite zapolnjene z 0.
Dani pristop ima O(n) časovno kompleksnost in ne uporablja dodatnega pomnilnika, kjer je n velikost vnosa.
17. Poiščite največji produkt z dvema celima v nizu.
Poiščite največji zmnožek dveh števil v nizu celih števil.
Razmislite o nizu 10 3 5 6 2 kot primeru. Par (-10, -3) ali (5, 6) je najvišji produkt.
Razmišljati o vsaki kombinaciji elementov in ugotoviti njihov izdelek je neumen pristop. Če je zmnožek trenutnega para večji od do sedaj doseženega največjega zmnožka, posodobite največji zmnožek. Sestavne dele končnega izdelka natisnite nazadnje.
Zgornja rešitev, kjer je n količina vnosa, ima časovno kompleksnost O(n2) in ne zavzame več prostora.
18. Kako premakniti vse ničle matrike na konec
Premaknite vse ničle v nizu celih števil na konec. Odgovor se mora izogibati uporabi konstantnega prostora in ohraniti relativni vrstni red komponent polja.
Vhod: {1,2,3,0,8,0,4,7}
Izhod bo {1,2,3,8,4,7,0,0}
Postavite element na naslednje razpoložljivo mesto v matriki, če trenutni element ni nič. Izpolnite vse preostale indekse z 0, ko so vsi elementi matrike obdelani.
Prejšnja rešitev ima O(n) časovno kompleksnost, kjer je n velikost vnosa.
19. Kako razvrstiti matriko z dvema vnosoma, ki se zamenjata v eni operaciji.
Razvrsti matriko v linearnem času glede na dva zamenjana elementa in matriko z vsemi elementi, razporejenimi v naraščajočem vrstnem redu. Pretvarjajte se, da matrika ne vsebuje dvojnikov.
Vnos:= [1,9,3,4,7,2] ali [9,3,7,2,1,4] ali [2,4,1,7,3,9]
Izhod: = [1,2,3,4,7,9]
Začenši z drugim elementom v nizu, je cilj primerjati vsak element z njegovim predhodnikom. Položaj spora se shrani tako, da se vzameta dva kazalca, x in y.
Posodobite x na indeks prejšnjega elementa in y na indeks trenutnega elementa, če je prvi večji od drugega. Posodobite y na indeks trenutnega elementa, če se izkaže, da je prejšnji element večji od trenutnega elementa.
Nazadnje zamenjajte elemente pri indeksih x in y, ko končamo obdelavo vsakega sosednjega para elementov.
Ker omenjena metoda izvede le enkratno skeniranje vhodne matrike velikosti n, je njena časovna zahtevnost O(n). Za rešitev ni potreben dodaten prostor.
20. Kako združiti dve razvrščeni matriki na mestu.
Združite elemente nizov X[] in Y[] – dva razvrščena niza velikosti m in n – tako, da obdržite razvrščeni vrstni red, to je tako, da X[] napolnite s prvimi m najmanjšimi elementi in Y[] napolnite z preostali elementi.
Če je element v matriki X[] že na pravem mestu (tj. tisti, ki je najmanjši med preostalimi elementi), ga zanemarite; sicer ga zamenjajte z najmanjšim elementom, ki je tudi prvi član Y[]. Če želite obdržati razvrščeni vrstni red po zamenjavi, prenesite element (zdaj na Y[0]) na njegovo ustrezno lokacijo v Y[].
Velikost prve matrike je m in velikost druge matrike je n, časovna kompleksnost pa je O(mn).
21. Kako preurediti niz predmetov na izmenično visoke in nizke položaje?
Preuredite niz celih števil tako, da bo vsak naslednji član večji od predhodnega in naslednjih elementov. Predpostavimo, da matrika ne vključuje nobenih podvojenih elementov.
Za učinkovit pristop ni potrebno razvrščanje matrike ali uporaba dodatnega prostora. Načrt je, da začnemo z drugim članom niza in se povečamo za dva za vsako ponovitev zanke.
Zamenjajte komponente, če zadnji element presega prvega. Na podoben način zamenjajte oba elementa, če je naslednji element večji od trenutnega elementa. Ob zaključku zanke bomo pridobili želeno matriko, ki je skladna z navedenimi omejitvami.
22. Kako nadomestiti vsak element matrike brez uporabe operatorja deljenja s produktom vsakega elementa v matriki?
Brez uporabe operatorja deljenja zamenjajte vsak element v nizu celih števil s produktom vseh drugih elementov.
V linearnem času in konstantnem prostoru lahko za reševanje te težave uporabimo rekurzijo. Pojem je rekurzivno izračunavanje zmnožkov vsakega elementa v desnem podnizu in posredovanje levega podmatričnega produkta kot parametrov funkcije.
Časovna kompleksnost je O(n).
23. Poiščite najbolj čuden element v nizu v logaritemskem času
Glede na niz celih števil, v katerem imajo vsi člani razen enega sodo število pojavitev, je težava ugotoviti, kolikokrat se ta element pojavi. Poiščite liho pojavljanje elementa v logaritemskem času in konstantnem prostoru, če se isti elementi pojavljajo v parih v matriki in nikoli ne moreta biti več kot dva primerka danega elementa v vrsti.
Operacija XOR nam omogoča, da rešimo to težavo v linearnem času. Cilj je XOR vsak element v matriki. Samo neparni elementi ostanejo potem, ko se sodi elementi med seboj izničijo.
To težavo je mogoče rešiti celo v času O(log(n)).
24. Kako pridobiti naslednji večji element za vsak element v krožni matriki?
Najti je treba naslednji večji element za vsak element v krožnem nizu celih števil. Prvo večje celo število za elementom x v matriki je naslednji večji element tega elementa.
Od desne proti levi lahko delujemo z elementi polja. Cilj je zanka za vsak element x, dokler ni sklad prazen ali pa imamo na vrhu višjega elementa. Nastavite naslednji večji element x, da se prikaže na vrhu sklada, ko se pojavi.
25. Najti število inverzij polja?
Poiščite skupno število inverzij matrike. Par I j) je inverzija niza A, če I j) in (A[i] > A[j]). Prešteti moramo vsak par teh v nizu.
Preštevanje vseh članov matrike, ki so manjši od nje na njeni desni strani, in dodajanje rezultata izhodu je preprost pristop.
Ta rešitev ima kompleksnost O(n2), kjer je n velikost vnosa.
26. Kaj je problem zadrževanja deževnice?
Iskanje največje količine vode, ki se lahko ujame v danem nizu palic s širino ene enote, je znano kot vprašanje "ujetje padavin".
Cilj je določiti najvišjo palico, ki se lahko postavi levo in desno od vsake palice. Najmanjša količina vodilnih stolpcev na levi in desni, zmanjšana za višino trenutnega stolpca, je količina vode, ki je shranjena na vrhu vsakega stolpca.
zaključek
V primerjavi z drugimi temami podatkovne strukture so nizi preprostejši. Če želite uspešno odgovoriti na vprašanja za intervju z nizi, morate imeti temeljno razumevanje nizov.
Morali bi obsežno pregledati temelje matrik, vključno z operacijami matrike (od deklaracije/ustvarjanja matrike do dostopa do/spreminjanja elementov matrike), kot tudi koncepte programiranja, kot so zanke, rekurzija in osnovni operaterji, da bi uspešno odgovorili na vprašanja intervjuja o matriki. Popolnoma prepoznajte težavo.
Če imate kakršna koli vprašanja, prosite za pojasnilo. Razmislite o razdelitvi vprašanja na bolj obvladljive dele. Prepričajte se, da imate v mislih algoritem, preden začnete programirati; zapišite ali vizualizirajte v diagram poteka. nato začnite pisati kodo.
Pustite Odgovori