Pregled sadržaja[Sakriti][Pokazati]
- 1. Kako definirate niz?
- 2. Dinamički nizovi: što su oni? Što ih razlikuje od Basic Arrays?
- 3. Kako se niz i rječnik međusobno razlikuju?
- 4. Nabrojite neke od prednosti i nedostataka nizova.
- 5. Na što se odnosi "Sparse Array"?
- 6. Kada biste odabrali povezani popis umjesto niza?
- 7. Što razlikuje indeksirani niz od asocijativnog niza?
- 8. Koje prednosti ima Heap u odnosu na sortirane nizove?
- 9. Možemo li definirati veličinu niza kao negativnu?
- 10. Kako ćete locirati cijeli broj koji nedostaje u nizu od 1 do 100 elemenata?
- 11. Kako pronaći indeks elementa u nizu?
- 12. Kako se možete riješiti određenog elementa iz niza?
- 13. Kako se može provjeriti jednakost dvaju nizova?
- 14. Kada govorimo o nizovima, što mislite pod izrazima "Dimenzija" i "Subscript"?
- Pitanja za intervju za kodiranje
- 15. Potražite par u nizu koji ima navedeni zbroj
- 16. Sortiranje binarnih nizova s linearnim vremenom
- 17. Pronađite najveći umnožak od dva int u nizu.
- 18. Kako pomaknuti sve nule niza na kraj
- 19. Kako sortirati niz s dva unosa koji se mijenjaju u jednoj operaciji.
- 20. Kako kombinirati dva sortirana niza na mjestu.
- 21. Kako promijeniti redoslijed niza stavki na izmjeničnim visokim i niskim pozicijama?
- 22. Kako zamijeniti svaki element niza bez korištenja operatora dijeljenja s umnoškom svakog elementa u nizu?
- 23. Pronađite najčudniji element u nizu u logaritamskom vremenu
- 24. Kako dobiti sljedeći veći element za svaki element u kružnom nizu?
- 25. Pronaći broj inverzija niza?
- 26. Što je problem zadržavanja kišnice?
- Zaključak
Razgovori o kodiranju sadrže niz DSA pitanja. Trebali biste biti vješti s nizovima ako se spremate za nadolazeći tehnički intervju s FAANG-om ili drugom tehnološkom tvrtkom Tier-1.
U većini intervjua o kodiranju dolazi na drugo mjesto nakon Stringsa. Niz je skupina povezanih podatkovnih elemenata koji se u memoriji drže u neposrednoj blizini jedan drugome.
Kako su povezani sa svim programskim jezicima, kao što su C, C++, Java, Python, Perl i Ruby, posvuda su. Nastavite čitati za neke izazove kodiranja u praksi i pitanja za intervjue i odgovore na temelju nizova.
Python će se koristiti u ovom postu za rješavanje problema kodiranja jer je jednostavan za korištenje, razumijevanje i mora biti poznat većini nas.
Započnimo.
1. Kako definirate niz?
- Skupina povezanih tipova podataka je polje.
- Nizovi su uvijek fiksni.
- Ista vrsta varijable pohranjena je na nekoliko mjesta pomoću objekata niza.
- Primitivni tipovi i reference objekata kompatibilni su s njim.
2. Dinamički nizovi: što su oni? Što ih razlikuje od Basic Arrays?
Automatsko skaliranje koje pružaju dinamički nizovi (koji se u Javi nazivaju i rastući nizovi, nizovi promjenjive veličine, promjenjivi nizovi ili ArrayLists u Javi) značajna je prednost.
Uvijek morate unaprijed znati koliko će elemenata vaš niz pohraniti budući da nizovi imaju fiksnu veličinu. Dinamički niz, s druge strane, raste kako mu dodajete nove članove, tako da ne morate unaprijed znati njegovu točnu veličinu.
3. Kako se niz i rječnik međusobno razlikuju?
Ovo je niz pitanja za intervju koji se redovito postavljaju temeljen na osnovama. Sljedeće su ključne razlike između polja i rječnika:
- Niz je uređen popis sličnih stavki. Rječnik, s druge strane, ima parove ključ-vrijednost.
- Veličine polja mogu se dinamički mijenjati. Takve dinamičke ideje ne postoje u rječnicima.
- Prije korištenja polja potrebno je odrediti njegovu veličinu. Veličine rječnika ne moraju se prilagođavati.
- Koristite naredbu Redim ako želite proširiti veličinu niza. U rječnicima se element može dodati bez deklaracije.
4. Nabrojite neke od prednosti i nedostataka nizova.
Prednosti:
- Nizovi mogu sortirati više elemenata istovremeno.
- drugo strukture podataka, kao stogovi, redovi, povezani popisi, stabla, grafikoni itd., mogu se implementirati u nizu.
- Indeks se može koristiti za postizanje elementa niza.
Nedostaci:
- Veličina niza mora biti deklarirana unaprijed. Međutim, u trenutku deklaracije niza možda nismo svjesni veličine koja nam je potrebna.
- Struktura niza je statična. To implicira da je veličina polja uvijek fiksna i da se alokacija memorije ne može povećati ili smanjiti.
5. Na što se odnosi "Sparse Array"?
Rijetki niz je podatkovni niz koji ima puno unosa s nula vrijednosti. Nasuprot tome, gusti niz sadrži većinu svojih stavki s vrijednostima različitim od nule. Indeksi prorijeđenog niza, koji pretvara brojeve u objekte, mogu sadržavati praznine. U usporedbi s HashMapom, memorijski su učinkovitiji.
6. Kada biste odabrali povezani popis umjesto niza?
Kada koristite povezane popise umjesto nizova, uzmite u obzir sljedeće:
- Ne trebaju vam nikakvi elementi za nasumični pristup.
- Tamo gdje je vremenska predvidljivost bitna, potrebna su vam umetanja i uklanjanja s liste u stalnom vremenu.
- Kako biste stvorili prioritetni red, možda ćete morati staviti stavke u središte popisa.
- Nemate pojma koliko će dugačak biti popis. Ako se veličina niza poveća, morate ponovno deklarirati i duplicirati memoriju, baš kao s jednostavnim nizovima.
7. Što razlikuje indeksirani niz od asocijativnog niza?
Primarne razlike između asocijativnih i indeksiranih nizova navedene su u sljedećoj tablici.
- Par ključ-vrijednost u tekstualnom ili numeričkom formatu koristi se za sortiranje asocijativnog niza. Svi ključevi indeksiranog niza su numerički, a svaki je ključ povezan s posebnom vrijednošću.
- U asocijativnom nizu ključ može biti niz. Indeksirano polje s cjelobrojnim ključevima koji počinju od 0.
- Tablica s dva stupca oponaša ponašanje asocijativnog niza. Slično tablici s jednim stupcem su indeksirani nizovi.
- Karte su tipa asocijativnog niza. Indeksni niz nije karta.
8. Koje prednosti ima Heap u odnosu na sortirane nizove?
Vremenska učinkovitost korištenja hrpe u odnosu na sortirane nizove ključna je prednost. Iako su heap operacije brže, sortiranje niza zahtijeva puno vremena. Hrpa može otkriti najmanji element znatno brže nego što se niz može sortirati.
Zadana kolekcija brojeva može se posložiti na jedan od dva načina pomoću sortiranih nizova. S druge strane, za određenu kolekciju brojeva može postojati više od jedne potencijalne gomile.
9. Možemo li definirati veličinu niza kao negativnu?
Ne, ne možemo definirati negativan cijeli broj kao veličinu niza. Neće biti pogreške tijekom kompilacije ako deklariramo. Tijekom izvođenja, međutim, naići ćemo na NegativeArraySizeException.
10. Kako ćete locirati cijeli broj koji nedostaje u nizu od 1 do 100 elemenata?
Zbroj niza može se izračunati primjenom sljedeće funkcije: n (n + 1) / 2
Funkcija će raditi samo ako polje nema duplikate ili mu nedostaje više od jednog cijelog broja. Bez obzira na to ima li niz duplicirane elemente, možete sortirati niz da vidite ima li elemenata koji su ekvivalentni.
11. Kako pronaći indeks elementa u nizu?
Indeks elementa može se otkriti putem linearnog ili binarnog pretraživanja. Sve dok ne locira podudaranje traženog elementa, linearna funkcija pretraživanja prelazi preko svakog elementa u nizu. Vraća indeks nakon što locira odgovarajući element. Posljedično, vremenska složenost linearnog pretraživanja je O. (n). I sortirano i nesortirano polje može koristiti linearno pretraživanje.
Korištenjem binarnog pretraživanja, koje kontinuirano dijeli niz na pola sve dok medijan intervala ne odgovara traženom elementu i ne pruži indeks, možete dobiti indeks elementa ako je niz sortiran. Posljedično, vremenska složenost binarnog pretraživanja je O. (log n).
12. Kako se možete riješiti određenog elementa iz niza?
Budući da ne možete jednostavno izbrisati elemente iz izvornog niza budući da su oni fiksni skupovi s definiranom veličinom, anketar traži da predložite drugačiji pristup i pozabavite se problemom koji postavlja pitanje. Najbolji postupak je napraviti novi niz kako biste izbrisali element. Možete duplicirati elemente iz prvog niza u ovom nizu i uključiti samo element koji želite izbrisati.
Druga strategija uključuje pronalaženje ciljnog elementa u nizu i zatim obrnuti redoslijed svih stavki koje su s desne strane ciljnog elementa.
13. Kako se može provjeriti jednakost dvaju nizova?
Najprije morate provjeriti duljine dva navedena niza. Podudarne stavke obaju nizova uspoređuju se ako su im duljine jednake. Dva niza će se smatrati jednakima. ako je svaki par komponenata u svakoj korespondenciji jednak. Ovaj se pristup ne preporučuje za provjeru jednakosti dvaju nizova ako su nizovi velikih dimenzija jer će to oduzeti puno vremena. Također možete koristiti metodu equals() koja je uključena u klasu Arrays, međutim, ako anketar od vas zatraži da usporedite dva niza bez korištenja ugrađenih metoda, ovaj će način biti koristan.
14. Kada govorimo o nizovima, što mislite pod izrazima "Dimenzija" i "Subscript"?
“Dimenzija” niza je broj indeksa ili indeksa potrebnih za identifikaciju svakog pojedinačnog člana. Indeksi i dimenzije mogu biti nejasni. Dimenzija je opis raspona dopuštenih ključeva, dok je indeks broj. Za svaku dimenziju niza potreban je samo jedan indeks.
Na primjer, polje arr[10][5] ima dvije dimenzije. Veličine 10 na jednom i 5 na drugom. Za adresiranje njegovih komponenti potrebna su vam dva indeksa. Oba su između 0 i 4; jedan između 0 i 9, uključivo.
Pitanja za intervju za kodiranje
15. Potražite par u nizu koji ima navedeni zbroj
Na primjer,
Ulazni:
- brojevi = [8, 7, 2, 5, 3, 1]
- cilj = 10
Izlaz:
- Pronađen par (8, 2)
- Or
- Pronađen par (7, 3)
Ulazni:
- brojevi = [5, 2, 6, 8, 1, 9]
- cilj = 12
Izlaz:
- Par nije pronađen
16. Sortiranje binarnih nizova s linearnim vremenom
Sortiraj binarni niz u linearnom vremenu i u fiksnom području. Izlaz bi trebao prvo prikazati sve nule, a zatim sve jedinice.
Na primjer,
- Unos: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Izlaz: { 0, 0, 0, 0, 1, 1, 1, 1 }
Jednostavan pristup bio bi izračunati ukupni broj nula u nizu, recimo k, a zatim popuniti prvih k indeksa u nizu s 0, a preostale indekse s 0. Kao alternativu, možemo izračunati koliko je ukupno 1 u niz k, popunite posljednjih k indeksa u nizu s 1, a ostatak indeksa ostavite ispunjen s 1.
Zadani pristup ima O(n) vremensku složenost i ne koristi dodatnu pohranu, gdje je n veličina ulaza.
17. Pronađite najveći umnožak od dva int u nizu.
Pronađite najveći umnožak dvaju brojeva u nizu cijelih brojeva.
Razmislite o nizu 10 3 5 6 2 kao primjeru. Par (-10, -3) ili (5, 6) je najveći proizvod.
Razmišljati o svakoj kombinaciji elemenata i shvatiti njihov proizvod je glup pristup. Ako je umnožak trenutnog para veći od maksimalnog umnoška dobivenog do sada, ažurirajte maksimalni umnožak. Komponente konačnog proizvoda ispišite na kraju.
Gornje rješenje, gdje je n količina ulaza, ima vremensku složenost O(n2) i ne zauzima više prostora.
18. Kako pomaknuti sve nule niza na kraj
Pomaknite sve nule u nizu cijelih brojeva na kraj. Odgovor bi trebao izbjegavati korištenje konstantnog prostora i sačuvati relativni poredak komponenti niza.
Ulaz: {1,2,3,0,8,0,4,7}
Izlaz će biti {1,2,3,8,4,7,0,0}
Stavite element na sljedeće dostupno mjesto u nizu ako trenutni element nije nula. Ispunite sve preostale indekse s 0 nakon što su sve stavke niza obrađene.
Prethodno rješenje ima O(n) vremensku složenost, gdje je n veličina ulaza.
19. Kako sortirati niz s dva unosa koji se mijenjaju u jednoj operaciji.
Sortiraj niz u linearnom vremenu s obzirom na dvije zamijenjene stavke i niz sa svim njegovim elementima poredanim uzlaznim redoslijedom. Pretvarajte se da niz ne sadrži duplikate.
Unos:= [1,9,3,4,7,2] ili [9,3,7,2,1,4] ili [2,4,1,7,3,9]
Izlaz: = [1,2,3,4,7,9]
Počevši od drugog elementa u nizu, cilj je usporediti svaki element s njegovim prethodnikom. Položaj spora pohranjuje se uzimanjem dva pokazivača, x i y.
Ažurirajte x na indeks prethodnog elementa i y na indeks trenutnog elementa ako je prvi veći od drugog. Ažurirajte y na indeks trenutnog elementa ako se pokaže da je prethodni element veći od trenutnog elementa.
Na kraju, zamijenite elemente na indeksima x i y nakon što smo završili s obradom svakog susjednog para elemenata.
Zbog činjenice da spomenuta metoda izvodi samo jedno skeniranje ulaznog niza veličine n, njena vremenska složenost je O(n). Za rješenje nije potrebna dodatna prostorija.
20. Kako kombinirati dva sortirana niza na mjestu.
Spojite stavke nizova X[] i Y[]—dva sortirana niza veličine m i n svaki—zadržavajući sortirani redoslijed, to jest ispunjavanjem X[] s prvih m najmanjih elemenata i ispunjavanjem Y[] s preostali elementi.
Ako je element u nizu X[] već na pravom mjestu (tj. onaj koji je najmanji među preostalim elementima), zanemarite ga; u suprotnom, zamijenite ga najmanjim elementom, koji je također prvi član Y[]. Da biste zadržali sortirani redoslijed nakon zamjene, prenesite element (sada na Y[0]) na njegovu odgovarajuću lokaciju u Y[].
Veličina prvog niza je m, a drugog niza je n, a vremenska složenost je O(mn).
21. Kako promijeniti redoslijed niza stavki na izmjeničnim visokim i niskim pozicijama?
Preuredite niz cijelih brojeva tako da svaki sljedeći član bude veći od prethodnog i sljedećeg elementa. Pretpostavimo da niz ne uključuje duple elemente.
Sortiranje niza ili korištenje dodatnog prostora nije potrebno za učinkovit pristup. Plan je, za početak, drugi član niza i povećanje za dva za svaku iteraciju petlje.
Zamijenite komponente ako zadnji element premašuje prvi. Na sličan način, promijenite obje stavke ako je sljedeći element veći od trenutnog elementa. Dobit ćemo željeni niz koji je u skladu s navedenim ograničenjima na kraju petlje.
22. Kako zamijeniti svaki element niza bez korištenja operatora dijeljenja s umnoškom svakog elementa u nizu?
Bez korištenja operatora dijeljenja, zamijenite svaki element u nizu cijelih brojeva umnoškom svih ostalih elemenata.
U linearnom vremenu i konstantnom prostoru, možemo upotrijebiti rekurziju za rješavanje ovog problema. Pojam je rekurzivno izračunavanje umnožaka svakog elementa u desnom podnizu i prosljeđivanje lijevog umnoška podniza kao parametara funkcije.
Vremenska složenost je O(n).
23. Pronađite najčudniji element u nizu u logaritamskom vremenu
S obzirom na niz cijelih brojeva u kojem svi osim jednog člana imaju paran broj pojavljivanja, problem je odrediti koliko se puta taj element pojavljuje. Pronađite neparni element koji se pojavljuje u logaritamskom vremenu i konstantnom prostoru ako se isti elementi pojavljuju u parovima u nizu i nikada ne mogu biti više od dvije instance danog elementa u nizu.
Operacija XOR omogućuje nam rješavanje ovog problema u linearnom vremenu. Cilj je XOR svaki element u nizu. Samo neparni elementi ostaju nakon što se parni elementi međusobno ponište.
Ovaj se problem čak može riješiti za O(log(n)) vremena.
24. Kako dobiti sljedeći veći element za svaki element u kružnom nizu?
Sljedeći veći element za svaki element u kružnom nizu cijelih brojeva trebao bi se nalaziti. Prvi veći cijeli broj nakon elementa x u nizu sljedeći je veći element tog elementa.
S desna na lijevo, možemo raditi na stavkama niza. Cilj je petlja za svaki element x sve dok stog ne bude prazan ili dok nemamo viši element na vrhu. Postavite sljedeći veći element od x da se pojavi na vrhu hrpe kada se pojavi.
25. Pronaći broj inverzija niza?
Pronađite ukupan broj inverzija niza. Par I j) se odnosi na inverziju niza A ako je I j) i (A[i] > A[j]). Moramo prebrojati svaki par ovih u nizu.
Brojanje svih članova niza koji su manji od njega s njegove desne strane i dodavanje rezultata u izlaz je jednostavan pristup.
Ovo rješenje ima O(n2) složenost, gdje je n veličina ulaza.
26. Što je problem zadržavanja kišnice?
Pronalaženje najveće količine vode koja se može zadržati u određenom nizu šipki širine jedne jedinice poznato je kao problem "zarobljavanja padalina".
Cilj je odrediti najvišu šipku koja se može postaviti lijevo i desno od svake trake. Minimum vodećih stupaca lijevo i desno, umanjen za visinu trenutnog stupca, je količina vode koja je pohranjena na vrhu svakog stupca.
Zaključak
U usporedbi s drugim temama strukture podataka, nizovi su jednostavniji. Kako biste uspjeli odgovoriti na pitanja za intervju s nizovima, morate imati temeljno razumijevanje nizova.
Trebali biste opširno pregledati temelje nizova, uključujući operacije s nizovima (od deklariranja/stvaranja niza do pristupa/modificiranja stavki niza), kao i koncepte programiranja kao što su petlje, rekurzija i osnovni operatori kako biste uspješno odgovorili na pitanja intervjua s nizovima. U potpunosti prepoznajte problem.
Trebali biste zatražiti pojašnjenje ako imate bilo kakvih pitanja. Razmislite o tome da problem podijelite na dijelove kojima se lakše može upravljati. Provjerite imate li algoritam na umu prije nego počnete programirati; zapišite ili vizualizirajte u dijagramu toka. zatim počnite pisati kod.
Ostavi odgovor