Cuprins[Ascunde][Spectacol]
- 1. Cum definiți un Array?
- 2. Matrice dinamice: ce sunt acestea? Ce le diferențiază de Basic Arrays?
- 3. Cum diferă o matrice și un dicționar unul de celălalt?
- 4. Enumerați câteva dintre beneficiile și dezavantajele matricelor.
- 5. La ce se referă „Sparse Array”?
- 6. Când ați alege o listă legată în locul unei matrice?
- 7. Ce deosebește un tablou indexat de un tablou asociativ?
- 8. Ce avantaje are Heap față de matricele sortate?
- 9. Putem defini dimensiunea matricei ca fiind negativă?
- 10. Cum localizați întregul lipsă într-o matrice de la 1 la 100 de elemente?
- 11. Cum găsiți indexul unui element dintr-o matrice?
- 12. Cum poți scăpa de un anumit element dintr-o matrice?
- 13. Cum poate fi verificată egalitatea a două matrice?
- 14. Când discutăm despre matrice, ce înțelegeți prin expresiile „Dimensiune” și „Indice”?
- Codarea întrebărilor interviului
- 15. Căutați o pereche într-o matrice care are suma specificată
- 16. Sortare matrice binară cu timp liniar
- 17. Găsiți cel mai mare produs two-int dintr-o matrice.
- 18. Cum să mutați toate zerourile matricei până la sfârșit
- 19. Cum se sortează o matrice cu două intrări care sunt comutate într-o singură operație.
- 20. Cum să combinați două matrice sortate în loc.
- 21. Cum se reordonează o serie de articole în poziții alternante înalte și joase?
- 22. Cum să înlocuiți fiecare element dintr-o matrice fără a utiliza un operator de divizare cu produsul fiecărui element din matrice?
- 23. Găsiți cel mai ciudat element dintr-o matrice în timp logaritmic
- 24. Cum să obțineți elementul mai mare ulterior pentru fiecare element dintr-o matrice circulară?
- 25. Găsiți numărul de inversiuni al unui tablou?
- 26. Care este problema captării apei de ploaie?
- Concluzie
Interviurile de codificare conțin o serie de întrebări DSA. Ar trebui să fii priceput cu matrice dacă te pregătești pentru viitorul tău interviu tehnologic cu FAANG sau cu o altă afacere de nivel 1.
În cele mai multe interviuri de codificare, acesta se află pe locul doi, după Strings. O matrice este o grupare de elemente de date înrudite păstrate în imediata apropiere unele de altele în memorie.
Deoarece sunt conectate la toate limbajele de programare, cum ar fi C, C++, Java, Python, Perl și Ruby, sunt peste tot. Continuați să citiți pentru câteva provocări practice de codificare și întrebări și răspunsuri la interviu bazate pe matrice.
Python va fi folosit în această postare pentru a aborda problemele de codificare, deoarece este simplu de utilizat, de înțeles și trebuie să fie familiar pentru majoritatea dintre noi.
Sa incepem.
1. Cum definiți un Array?
- Un grup de tipuri de date înrudite este o matrice.
- Matricele sunt întotdeauna fixe.
- Același tip de variabilă este stocată în mai multe locuri de obiectele matrice.
- Tipurile primitive și referințele la obiect sunt ambele compatibile cu acesta.
2. Matrice dinamice: ce sunt acestea? Ce le diferențiază de Basic Arrays?
Scalarea automată pe care o oferă matricele dinamice (numite și matrice care poate crește, matrice redimensionabile, matrice modificabile sau ArrayLists în Java) este un avantaj semnificativ.
Trebuie să știți întotdeauna câte elemente va stoca matricea dvs. în avans, deoarece matricele au o dimensiune fixă. O matrice dinamică, pe de altă parte, crește pe măsură ce îi adăugați membri suplimentari, astfel încât nu trebuie să cunoașteți dimensiunea exactă în prealabil.
3. Cum diferă o matrice și un dicționar unul de celălalt?
Aceasta este o gamă de întrebări de interviu bazată pe elemente fundamentale care sunt puse în mod regulat. Următoarele sunt distincțiile cheie dintre matrice și dicționare:
- O matrice este o listă ordonată de articole similare. Dicționarul, pe de altă parte, are perechi cheie-valoare.
- Dimensiunile matricei se pot schimba dinamic. Astfel de idei dinamice nu există în dicționare.
- Înainte de a utiliza o matrice, dimensiunea acesteia trebuie specificată. Dimensiunile dicționarului nu trebuie personalizate.
- Utilizați instrucțiunea Redim dacă doriți să extindeți dimensiunea matricei. În dicționare, un element poate fi adăugat fără declarație.
4. Enumerați câteva dintre beneficiile și dezavantajele matricelor.
avantaje:
- Matricele pot sorta un număr de elemente simultan.
- Altele structuri de date, cum ar fi stive, cozi, liste legate, arbori, grafice etc., pot fi implementate într-o matrice.
- Un index poate fi folosit pentru a ajunge la un element al unui tablou.
Dezavantaje:
- Dimensiunea unei matrice trebuie declarată în prealabil. În momentul declarării matricei, s-ar putea, totuși, să nu fim conștienți de dimensiunea de care avem nevoie.
- Structura matricei este statică. Aceasta implică faptul că dimensiunea matricei este întotdeauna fixă și că alocarea memoriei nu poate fi mărită sau redusă.
5. La ce se referă „Sparse Array”?
O matrice rară este o matrice de date care are o mulțime de intrări cu valori zero. În schimb, o matrice densă conține majoritatea elementelor sale cu valori diferite de zero. Indicii unei matrice rare, care convertește numerele în obiecte, pot include goluri. În comparație cu un HashMap, acestea sunt mai eficiente din punct de vedere al memoriei.
6. Când ați alege o listă legată în locul unei matrice?
Când utilizați liste legate în loc de matrice, luați în considerare:
- Nu aveți nevoie de niciun element pentru a avea acces aleatoriu.
- Acolo unde predictibilitatea temporală este esențială, aveți nevoie de inserări și eliminări în timp constant din listă.
- Pentru a crea o coadă cu prioritate, poate fi necesar să plasați elemente în centrul listei.
- Nu ai idee cât de lungă va fi lista. Dacă dimensiunea matricei crește, trebuie să re-declarați și să duplicați memoria, la fel ca în cazul matricelor simple.
7. Ce deosebește un tablou indexat de un tablou asociativ?
Distincțiile primare dintre tablourile asociative și cele indexate sunt enumerate în tabelul următor.
- O pereche cheie-valoare în format text sau numeric este utilizată pentru a sorta o matrice asociativă. Cheile matricei indexate sunt toate numerice și fiecare cheie este conectată la o valoare distinctă.
- Într-o matrice asociativă, cheia poate fi un șir. Matrice indexată cu chei întregi începând de la 0.
- Un tabel cu două coloane imită comportamentul unui tablou asociativ. Similar unui tabel cu o singură coloană sunt matricele indexate.
- Hărțile sunt un tip de matrice asociativă. O matrice de index nu este o hartă.
8. Ce avantaje are Heap față de matricele sortate?
Eficiența în timp a utilizării Heap over Sorted Arrays este avantajul cheie. În timp ce operațiunile heap sunt mai rapide, sortarea unei matrice necesită mult timp. O grămadă poate descoperi cel mai mic element mult mai repede decât poate fi sortată o matrice.
O anumită colecție de numere poate fi aranjată în unul din două moduri folosind Sorted Arrays. Pe de altă parte, pentru o anumită colecție de numere, poate exista mai mult de un potențial heap.
9. Putem defini dimensiunea matricei ca fiind negativă?
Nu, nu putem defini un număr întreg negativ ca fiind dimensiunea unui tablou. Nu va exista o eroare de compilare dacă declarăm. În timpul execuției, vom întâlni totuși o excepție NegativeArraySizeException.
10. Cum localizați întregul lipsă într-o matrice de la 1 la 100 de elemente?
Totalul seriei poate fi calculat prin aplicarea următoarei funcții: n (n + 1) / 2
Această funcție va funcționa numai dacă matricea nu are duplicate sau lipsește mai mult de un număr întreg. Indiferent dacă o matrice are elemente duplicate, puteți sorta matricea pentru a vedea dacă există elemente echivalente.
11. Cum găsiți indexul unui element dintr-o matrice?
Indicele unui element poate fi descoperit printr-o căutare liniară sau binară. Până când localizează potrivirea elementului necesar, o funcție de căutare liniară trece în buclă peste fiecare element dintr-o matrice. Returnează indexul odată ce localizează elementul potrivit. În consecință, complexitatea temporală a căutării liniare este O. (n). Atât o matrice sortată, cât și una nesortată pot folosi căutarea liniară.
Folosind o căutare binară, care împarte continuu matricea la jumătate până când mediana intervalului se potrivește cu elementul necesar și oferă indexul, puteți obține indexul elementului dacă matricea este sortată. În consecință, complexitatea temporală a căutării binare este O. (log n).
12. Cum poți scăpa de un anumit element dintr-o matrice?
Deoarece nu puteți șterge pur și simplu elemente din matricea originală, deoarece sunt seturi fixe cu o dimensiune definită, intervievatorul caută să sugerați o abordare diferită și să rezolvați problema pe care o ridică întrebarea. Cel mai bun curs de acțiune este să faci o nouă matrice pentru a șterge un element. Puteți duplica elementele din prima matrice din această matrice și includeți numai elementul pe care doriți să îl ștergeți.
O altă strategie implică găsirea elementului țintă în matrice și apoi inversarea ordinii tuturor elementelor care se află în dreapta elementului țintă.
13. Cum poate fi verificată egalitatea a două matrice?
Mai întâi trebuie să verificați lungimile celor două matrice furnizate. Elementele care se potrivesc ale ambelor matrice sunt comparate atunci când lungimile lor sunt egale. Cele două matrice vor fi considerate egale. dacă fiecare pereche de componente din fiecare corespondență este egală. Această abordare nu este recomandată pentru a verifica egalitatea a două matrice dacă matricele sunt mari ca dimensiuni, deoarece va dura mult timp. De asemenea, puteți utiliza metoda equals() inclusă în clasa Arrays, cu toate acestea, dacă intervievatorul vă cere să comparați două matrice fără a utiliza metode încorporate, acest mod va fi util.
14. Când discutăm despre matrice, ce înțelegeți prin expresiile „Dimensiune” și „Indice”?
„Dimensiunea” unui tablou este numărul de indici, sau indice, necesari pentru a identifica fiecare membru individual. Indicele și dimensiunile pot fi neclare. O dimensiune este o descriere a gamei de chei permise, în timp ce un indice este un număr. Este necesar doar un indice pentru fiecare dimensiune a matricei.
De exemplu, matricea arr[10][5] are două dimensiuni. Marimi 10 pe una si 5 pe cealalta. Pentru a aborda componentele sale, aveți nevoie de două indice. Ambele sunt între 0 și 4; unul intre 0 si 9, inclusiv.
Codarea întrebărilor interviului
15. Căutați o pereche într-o matrice care are suma specificată
De exemplu,
Intrare:
- numere = [8, 7, 2, 5, 3, 1]
- țintă = 10
ieșire:
- Pereche găsită (8, 2)
- Or
- Pereche găsită (7, 3)
Intrare:
- numere = [5, 2, 6, 8, 1, 9]
- țintă = 12
ieșire:
- Perechea nu a fost găsită
16. Sortare matrice binară cu timp liniar
Sortați o matrice binară în timp liniar și într-o zonă fixă. Ieșirea ar trebui să afișeze mai întâi toate zerourile, apoi toate cele.
De exemplu,
- Intrare: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Ieșire: { 0, 0, 0, 0, 1, 1, 1, 1 }
O abordare simplă ar fi să se calculeze numărul total de 0 al matricei, să zicem k, și apoi să se completeze primii k indici din matrice cu 0 și pe cei rămași indici cu 1. Ca alternativă, am putea calcula câți 1 sunt în total în matricea k, completați ultimii k indici din matrice cu 1 și lăsați restul indicilor umpluți cu 0.
Abordarea dată are o complexitate de timp O(n) și nu utilizează stocare suplimentară, unde n este dimensiunea intrării.
17. Găsiți cel mai mare produs two-int dintr-o matrice.
Găsiți cel mai mare produs din două numere dintr-un tablou întreg.
Gândiți-vă la matricea 10 3 5 6 2 ca exemplu. Perechea (-10, -3) sau (5, 6) este produsul cel mai mare.
Să te gândești la fiecare combinație de elemente și să-ți dai seama de produsul lor este o abordare prostească. Dacă produsul perechii curente este mai mare decât produsul maxim obținut până acum, actualizați produsul maxim. Imprimați ultima dată componentele produsului final.
Soluția de mai sus, unde n este cantitatea de intrare, are o complexitate de timp de O(n2) și nu mai ocupă spațiu.
18. Cum să mutați toate zerourile matricei până la sfârșit
Mutați toate zerourile dintr-o matrice întregă până la sfârșit. Răspunsul ar trebui să evite utilizarea spațiului constant și să păstreze ordinea relativă a componentelor matricei.
Intrare: {1,2,3,0,8,0,4,7}
Ieșirea va fi {1,2,3,8,4,7,0,0}
Puneți elementul în următoarea poziție disponibilă în matrice dacă elementul curent nu este zero. Completați toți indicii rămași cu 0 odată ce elementele matricei au fost toate procesate.
Soluția anterioară are o complexitate de timp O(n), unde n este dimensiunea intrării.
19. Cum se sortează o matrice cu două intrări care sunt comutate într-o singură operație.
Sortați o matrice în timp liniar având în vedere două elemente schimbate și o matrice cu toate elementele sale aranjate în ordine crescătoare. Pretindeți-vă că matricea nu conține duplicate.
Intrare:= [1,9,3,4,7,2] sau [9,3,7,2,1,4] sau [2,4,1,7,3,9]
Ieșire: = [1,2,3,4,7,9]
Începând cu al doilea element din matrice, obiectivul este de a compara fiecare element cu predecesorul său. Poziția disputei este stocată prin luarea a doi indicatori, x și y.
Actualizați x la indexul elementului anterior și y la indexul elementului curent dacă primul este mai mare decât cel din urmă. Actualizați y la indexul elementului curent dacă se dovedește că elementul anterior este mai mare decât elementul curent.
În cele din urmă, comutați elementele de la indicii x și y odată ce am terminat de procesat fiecare pereche de elemente adiacente.
Datorită faptului că metoda menționată mai sus efectuează doar o singură scanare a matricei de intrare de dimensiune n, complexitatea sa de timp este O(n). Nu este nevoie de încăpere suplimentară pentru soluție.
20. Cum să combinați două matrice sortate în loc.
Îmbinați elementele matricelor X[] și Y[]—două matrice sortate de mărimea m și n fiecare—prin păstrarea ordinii sortate, adică umplând X[] cu primele m elemente cele mai mici și umplând Y[] cu elementele rămase.
Dacă un element din tabloul X[] este deja în poziția corectă (adică, cel care este cel mai mic dintre elementele rămase), ignorați-l; în caz contrar, înlocuiți-l cu cel mai mic element, care se întâmplă să fie și primul membru al lui Y[]. Pentru a păstra ordinea sortată după schimbare, transferați elementul (acum la Y[0]) în locația sa corectă în Y[].
Mărimea primului tablou este m, iar dimensiunea celui de-al doilea tablou este n, iar complexitatea timpului este O(mn).
21. Cum se reordonează o serie de articole în poziții alternante înalte și joase?
Rearanjați un tablou întreg astfel încât fiecare membru ulterior să fie mai mare decât elementele precedente și următoare. Să presupunem că matricea nu include niciun element duplicat.
Sortarea matricei sau utilizarea spațiului suplimentar nu este necesară pentru o abordare eficientă. Planul este, pentru început, al doilea membru al matricei și crește cu două pentru fiecare iterație a buclei.
Schimbați componentele dacă ultimul element îl depășește pe primul. În mod similar, comutați ambele articole dacă următorul element este mai mare decât elementul curent. Vom obține matricea dorită care respectă restricțiile specificate la încheierea buclei.
22. Cum să înlocuiți fiecare element dintr-o matrice fără a utiliza un operator de divizare cu produsul fiecărui element din matrice?
Fără a utiliza operatorul de divizare, înlocuiți fiecare element dintr-o matrice întregă cu produsul tuturor celorlalte elemente.
În timp liniar și spațiu constant, putem folosi recursiunea pentru a aborda această problemă. Calculul recursiv a produselor fiecărui element din subbarra din dreapta și trecerea produsului subbarra din stânga ca parametri de funcție este noțiunea.
Complexitatea timpului este O(n).
23. Găsiți cel mai ciudat element dintr-o matrice în timp logaritmic
Având în vedere un tablou întreg în care toți membrii, cu excepția unuia, au un număr par de apariții, problema este de a determina de câte ori apare acest element. Găsiți elementul impar în timp logaritmic și spațiu constant dacă aceleași elemente apar în perechi în matrice și nu pot exista niciodată mai mult de două instanțe ale unui element dat într-un rând.
Operația XOR ne permite să rezolvăm această problemă în timp liniar. Scopul este de a XOR fiecare element din matrice. Doar elementele care apar impare rămân după ce elementele pare se anulează reciproc.
Această problemă poate fi chiar rezolvată în timp O(log(n)).
24. Cum să obțineți elementul mai mare ulterior pentru fiecare element dintr-o matrice circulară?
Următorul element mai mare pentru fiecare element dintr-o matrice de întregi circulare ar trebui să fie localizat. Primul număr întreg mai mare după un element x din matrice este elementul mai mare ulterior al acelui element.
De la dreapta la stânga, putem opera pe elemente matrice. Scopul este de a bucla pentru fiecare element x până când fie stiva este goală, fie avem un element mai înalt deasupra acestuia. Setați următorul element mai mare de x să apară în partea de sus a stivei atunci când apare.
25. Găsiți numărul de inversiuni al unui tablou?
Găsiți numărul total de inversiuni ale unui tablou. O pereche I j) se referă la o inversare a unui tablou A dacă I j) și (A[i] > A[j]). Trebuie să numărăm fiecare pereche din acestea din matrice.
Numărarea tuturor membrilor matricei care sunt mai puține decât în dreapta sa și adăugarea rezultatului la ieșire este o abordare simplă.
Această soluție are o complexitate O(n2), unde n este dimensiunea intrării.
26. Care este problema captării apei de ploaie?
Găsirea celei mai multe ape care poate fi prinsă într-un anumit set de bare cu o lățime de o unitate fiecare este cunoscută sub numele de problema „capcană a precipitațiilor”.
Scopul este de a determina cea mai înaltă bară care poate fi plasată în stânga și în dreapta fiecărei bare. Minimul barelor de conducere la stânga și la dreapta, mai puțin înălțimea barei curente, este cantitatea de apă care este stocată deasupra fiecărei bare.
Concluzie
În comparație cu alte subiecte privind structura datelor, matricele sunt mai simple. Pentru a răspunde la întrebările de interviu cu matrice, trebuie să aveți o înțelegere fundamentală a matricelor.
Ar trebui să revizuiți pe larg bazele matricelor, inclusiv operațiunile cu matrice (de la declararea/crearea unei matrice până la accesarea/modificarea elementelor matricei), precum și concepte de programare precum bucle, recursivitate și operatori de bază pentru a răspunde cu succes la întrebările interviului matrice. Recunoașteți problema complet.
Ar trebui să solicitați clarificări dacă aveți întrebări. Gândiți-vă să împărțiți problema în părți mai ușor de gestionat. Asigurați-vă că aveți algoritmul în minte înainte de a începe programarea; notează-l sau vizualizează-l într-o diagramă. apoi începeți să scrieți codul.
Lasă un comentariu