Sommario[Nascondere][Spettacolo]
- 1. Come si definisce un array?
- 2. Array dinamici: cosa sono? Cosa li distingue dagli array di base?
- 3. In che modo un array e un dizionario variano l'uno dall'altro?
- 4. Elenca alcuni dei vantaggi e degli svantaggi degli array.
- 5. A cosa si riferisce "Sparse Array"?
- 6. Quando sceglieresti un elenco collegato su un array?
- 7. Cosa distingue un array indicizzato da un array associativo?
- 8. Quali vantaggi ha Heap rispetto agli array ordinati?
- 9. Possiamo definire negativa la dimensione dell'array?
- 10. Come si individua l'intero mancante in un array da 1 a 100 elementi?
- 11. Come trovi l'indice di un elemento in un array?
- 12. Come puoi eliminare un elemento specifico da un array?
- 13. Come si può verificare l'uguaglianza di due array?
- 14. Quando discutiamo di array, cosa intendi con le frasi "Dimensione" e "Pedice"?
- Domande di intervista sulla codifica
- 15. Cerca una coppia in un array che abbia la somma specificata
- 16. Ordinamento di array binari con tempo lineare
- 17. Trova il prodotto a due int più grande in un array.
- 18. Come spostare tutti gli zeri dell'array alla fine
- 19. Come ordinare un array con due voci che vengono commutate in un'unica operazione.
- 20. Come combinare due array ordinati sul posto.
- 21. Come riordinare una serie di articoli alternando posizioni alte e basse?
- 22. Come sostituire ogni elemento di un array senza utilizzare un operatore di divisione con il prodotto di ciascun elemento nell'array?
- 23. Trova l'elemento più strano in un array in tempo logaritmico
- 24. Come ottenere il successivo elemento più grande per ogni elemento in una matrice circolare?
- 25. Trovare il conteggio delle inversioni di un array?
- 26. Qual è il problema di intrappolamento dell'acqua piovana?
- Conclusione
Le interviste di codifica contengono una serie di domande DSA. Dovresti essere esperto con gli array se ti stai preparando per il tuo prossimo colloquio tecnico con FAANG o un'altra azienda tecnologica di livello 1.
Nella maggior parte delle interviste di programmazione, viene al secondo posto dopo Strings. Un array è un raggruppamento di elementi di dati correlati tenuti in stretta vicinanza l'uno all'altro in memoria.
Poiché sono collegati a tutti i linguaggi di programmazione, come C, C++, Java, Python, Perl e Ruby, sono ovunque. Continua a leggere per alcune sfide di codifica pratica e domande e risposte per interviste basate su array.
Python verrà utilizzato in questo post per affrontare i problemi di codifica perché è semplice da usare, comprendere e deve essere familiare alla maggior parte di noi.
Cominciamo.
1. Come si definisce un array?
- Un gruppo di tipi di dati correlati è un array.
- Gli array sono sempre fissi.
- Lo stesso tipo di variabile è memorizzato in più posizioni dagli oggetti array.
- I tipi primitivi e i riferimenti agli oggetti sono entrambi compatibili con esso.
2. Array dinamici: cosa sono? Cosa li distingue dagli array di base?
Il ridimensionamento automatico fornito dagli array dinamici (indicati anche come array espandibili, array ridimensionabili, array modificabili o ArrayList in Java) è un vantaggio significativo.
Devi sempre sapere quanti elementi memorizzerà il tuo array in anticipo poiché gli array hanno una dimensione fissa. Un array dinamico, d'altra parte, cresce man mano che si aggiungono altri membri, quindi non è necessario conoscerne la dimensione esatta in anticipo.
3. In che modo un array e un dizionario variano l'uno dall'altro?
Questa è una serie di domande di intervista basate sui fondamenti che vengono poste regolarmente. Di seguito sono riportate le principali distinzioni tra array e dizionari:
- Un array è un elenco ordinato di elementi simili. Il dizionario, d'altra parte, ha coppie chiave-valore.
- Le dimensioni dell'array possono cambiare in modo dinamico. Tali idee dinamiche non esistono nei dizionari.
- Prima di utilizzare un array, è necessario specificarne la dimensione. Le dimensioni del dizionario non devono essere personalizzate.
- Utilizzare l'istruzione Redim se si desidera espandere la dimensione dell'array. Nei dizionari, un elemento può essere aggiunto senza una dichiarazione.
4. Elenca alcuni dei vantaggi e degli svantaggi degli array.
vantaggi:
- Gli array possono ordinare più elementi contemporaneamente.
- Altro strutture di dati, come stack, code, elenchi collegati, alberi, grafici, ecc., possono essere implementati in un array.
- Un indice può essere utilizzato per raggiungere un elemento di un array.
svantaggi:
- La dimensione di un array deve essere dichiarata in anticipo. Al momento della dichiarazione dell'array, tuttavia, potremmo non essere a conoscenza della dimensione richiesta.
- La struttura dell'array è statica. Implica che la dimensione dell'array è sempre fissa e che l'allocazione di memoria non può essere aumentata o ridotta.
5. A cosa si riferisce "Sparse Array"?
Un array sparso è un array di dati che ha molte voci con zero valori. Al contrario, un array denso contiene la maggior parte dei suoi elementi con valori diversi da zero. Gli indici di una matrice sparsa, che converte i numeri in oggetti, possono includere lacune. Rispetto a una HashMap, sono più efficienti in termini di memoria.
6. Quando sceglieresti un elenco collegato su un array?
Quando si utilizzano elenchi collegati anziché array, considerare:
- Non hai bisogno di alcun elemento per avere accesso casuale.
- Laddove la prevedibilità temporale è essenziale, sono necessari inserimenti e rimozioni dall'elenco a tempo costante.
- Per creare una coda prioritaria, potrebbe essere necessario posizionare gli elementi al centro dell'elenco.
- Non hai idea di quanto sarà lunga la lista. Se la dimensione dell'array aumenta, è necessario dichiarare nuovamente e duplicare la memoria, proprio come con gli array semplici.
7. Cosa distingue un array indicizzato da un array associativo?
Le principali distinzioni tra array associativi e indicizzati sono elencate nella tabella seguente.
- Una coppia chiave-valore in formato testo o numerico viene utilizzata per ordinare una matrice associativa. Le chiavi dell'array indicizzato sono tutte numeriche e ogni chiave è collegata a un valore distinto.
- In un array associativo, la chiave potrebbe essere una stringa. Matrice indicizzata con chiavi intere che iniziano da 0.
- Una tabella a due colonne imita il comportamento di una matrice associativa. Simili a una tabella a colonna singola sono gli array indicizzati.
- Le mappe sono un tipo di array associativo. Un array di indici non è una mappa.
8. Quali vantaggi ha Heap rispetto agli array ordinati?
L'efficienza in termini di tempo nell'utilizzo di Heap su array ordinati è il vantaggio principale. Sebbene le operazioni di heap siano più veloci, l'ordinamento di un array richiede molto tempo. Un heap può scoprire l'elemento più piccolo molto più rapidamente di quanto possa essere ordinato un array.
Una data raccolta di numeri può essere organizzata in due modi utilizzando Matrici ordinate. D'altra parte, per una data raccolta di numeri, potrebbe esserci più di un potenziale heap.
9. Possiamo definire negativa la dimensione dell'array?
No, non possiamo definire un numero intero negativo come la dimensione di un array. Non ci sarà un errore in fase di compilazione se dichiariamo. In fase di esecuzione, tuttavia, incontreremo un'eccezione NegativeArraySizeException.
10. Come si individua l'intero mancante in un array da 1 a 100 elementi?
Il totale delle serie può essere calcolato applicando la seguente funzione: n (n + 1) / 2
Solo se l'array non ha duplicati o ha più di un intero mancante, questa funzione funzionerà. Se un array ha elementi duplicati, puoi ordinare l'array per vedere se ci sono elementi equivalenti.
11. Come trovi l'indice di un elemento in un array?
L'indice di un elemento può essere scoperto tramite una ricerca lineare o binaria. Finché non individua la corrispondenza dell'elemento richiesto, una funzione di ricerca lineare scorre su ogni singolo elemento di un array. Restituisce l'indice una volta individuato l'elemento corrispondente. Di conseguenza, la complessità temporale della ricerca lineare è O. (n). Sia un array ordinato che uno non ordinato possono utilizzare la ricerca lineare.
Utilizzando una ricerca binaria, che divide continuamente l'array a metà finché la mediana dell'intervallo non corrisponde all'elemento richiesto e fornisce l'indice, è possibile ottenere l'indice dell'elemento se l'array è ordinato. Di conseguenza, la complessità temporale della ricerca binaria è O. (log n).
12. Come puoi eliminare un elemento specifico da un array?
Dal momento che non puoi semplicemente eliminare elementi dall'array originale poiché sono insiemi fissi con una dimensione definita, l'intervistatore cerca che tu suggerisca un approccio diverso e affronti il problema sollevato dalla domanda. La migliore linea d'azione è creare un nuovo array per eliminare un elemento. Puoi duplicare gli elementi del primo array in questo array e includere solo l'elemento che desideri eliminare.
Un'altra strategia consiste nel trovare l'elemento target nell'array e quindi invertire l'ordine di tutti gli elementi che si trovano a destra dell'elemento target.
13. Come si può verificare l'uguaglianza di due array?
È necessario prima verificare le lunghezze dei due array forniti. Gli elementi corrispondenti di entrambi gli array vengono confrontati quando le loro lunghezze sono uguali. I due array saranno considerati uguali. se ogni coppia di componenti in ogni corrispondenza è uguale. Questo approccio non è consigliato per verificare l'uguaglianza di due array se gli array sono di grandi dimensioni poiché richiederà molto tempo. Puoi anche usare il metodo equals() incluso nella classe Arrays, tuttavia, se l'intervistatore ti chiede di confrontare due array senza utilizzare metodi integrati, questo metodo sarà utile.
14. Quando discutiamo di array, cosa intendi con le frasi "Dimensione" e "Pedice"?
La "dimensione" di un array è il numero di indici, o pedici, necessari per identificare ogni singolo membro. Gli indici e le dimensioni potrebbero non essere chiari. Una dimensione è una descrizione dell'intervallo di chiavi consentite, mentre un pedice è un numero. È richiesto un solo pedice per ciascuna dimensione dell'array.
Ad esempio, l'array arr[10][5] ha due dimensioni. Taglie 10 su uno e 5 sull'altro. Per indirizzare i suoi componenti, sono necessari due pedici. Entrambi sono compresi tra 0 e 4; uno compreso tra 0 e 9, inclusi.
Domande di intervista sulla codifica
15. Cerca una coppia in un array che abbia la somma specificata
Per esempio,
Ingresso:
- numeri = [8, 7, 2, 5, 3, 1]
- obiettivo = 10
Produzione:
- Coppia trovata (8, 2)
- Or
- Coppia trovata (7, 3)
Ingresso:
- numeri = [5, 2, 6, 8, 1, 9]
- obiettivo = 12
Produzione:
- Coppia non trovata
16. Ordinamento di array binari con tempo lineare
Ordina un array binario in tempo lineare e in un'area fissa. L'output dovrebbe visualizzare prima tutti gli zeri, poi tutti quelli.
Per esempio,
- Input: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Uscita: { 0, 0, 0, 0, 1, 1, 1, 1 }
Un approccio semplice sarebbe calcolare il numero totale di 0 dell'array, diciamo k, e quindi riempire i primi k indici dell'array con 0 e gli indici rimanenti con 1. In alternativa, potremmo calcolare quanti 1 sono totali nel array k, riempi gli ultimi k indici nell'array con 1 e lascia il resto degli indici riempito con 0.
L'approccio fornito ha una complessità temporale O(n) e non utilizza memoria aggiuntiva, dove n è la dimensione dell'input.
17. Trova il prodotto a due int più grande in un array.
Trova il prodotto più grande di due numeri in una matrice intera.
Pensa all'array 10 3 5 6 2 come esempio. La coppia (-10, -3) o (5, 6) è il prodotto più alto.
Pensare a ogni combinazione di elementi e capire il loro prodotto è un approccio sciocco. Se il prodotto della coppia corrente è maggiore del prodotto massimo ottenuto finora, aggiornare il prodotto massimo. Stampa i componenti del prodotto finale per ultimi.
La soluzione di cui sopra, dove n è la quantità dell'input, ha una complessità temporale di O(n2) e non occupa più spazio.
18. Come spostare tutti gli zeri dell'array alla fine
Sposta tutti gli zeri in una matrice intera alla fine. La risposta dovrebbe evitare di utilizzare uno spazio costante e preservare l'ordine relativo dei componenti dell'array.
Inserimento: {1,2,3,0,8,0,4,7}
L'output sarà {1,2,3,8,4,7,0,0}
Metti l'elemento nella seguente posizione disponibile nell'array se l'elemento corrente non è zero. Riempi tutti gli indici rimanenti con 0 una volta che tutti gli elementi dell'array sono stati elaborati.
La soluzione precedente ha una complessità temporale O(n), dove n è la dimensione dell'input.
19. Come ordinare un array con due voci che vengono commutate in un'unica operazione.
Ordina un array nel tempo lineare dati due elementi scambiati e un array con tutti i suoi elementi disposti in ordine crescente. Fai finta che l'array non contenga duplicati.
Input:= [1,9,3,4,7,2] o [9,3,7,2,1,4] o [2,4,1,7,3,9]
Uscita: = [1,2,3,4,7,9]
A partire dal secondo elemento dell'array, l'obiettivo è confrontare ogni elemento con il suo predecessore. La posizione della controversia viene memorizzata prendendo due puntatori, x e y.
Aggiorna x all'indice dell'elemento precedente e y all'indice dell'elemento corrente se il primo è maggiore del secondo. Aggiorna y all'indice dell'elemento corrente se risulta che l'elemento precedente è maggiore dell'elemento corrente.
Infine, scambia gli elementi agli indici xey una volta terminata l'elaborazione di ciascuna coppia di elementi adiacenti.
A causa del fatto che il suddetto metodo esegue solo una singola scansione dell'array di input di dimensione n, la sua complessità temporale è O(n). Non è necessario spazio aggiuntivo per la soluzione.
20. Come combinare due array ordinati sul posto.
Unisci gli elementi degli array X[] e Y[], due array ordinati di dimensioni m e n ciascuno, mantenendo l'ordine ordinato, ovvero riempiendo X[] con i primi m elementi più piccoli e riempiendo Y[] con il elementi rimanenti.
Se un elemento nell'array X[] è già nella posizione corretta (cioè quello che è il più piccolo tra gli elementi rimanenti), ignoralo; in caso contrario, sostituirlo con l'elemento più piccolo, che è anche il primo membro di Y[]. Per mantenere l'ordine dopo lo scambio, trasferire l'elemento (ora in Y[0]) nella sua posizione corretta in Y[].
La dimensione del primo array è m e la dimensione del secondo array è n e la complessità temporale è O(mn).
21. Come riordinare una serie di articoli alternando posizioni alte e basse?
Riorganizzare una matrice intera in modo che ogni membro successivo sia più grande degli elementi precedenti e successivi. Si supponga che l'array non includa elementi duplicati.
L'ordinamento dell'array o l'utilizzo di spazio aggiuntivo non sono necessari per un approccio efficace. Il piano è, per cominciare, il secondo membro dell'array e aumenta di due per ogni iterazione del ciclo.
Scambia i componenti se l'ultimo elemento supera il primo. Allo stesso modo, cambia entrambi gli elementi se l'elemento successivo è più grande dell'elemento corrente. Otterremo l'array desiderato che rispetta le restrizioni specificate alla conclusione del ciclo.
22. Come sostituire ogni elemento di un array senza utilizzare un operatore di divisione con il prodotto di ciascun elemento nell'array?
Senza utilizzare l'operatore di divisione, sostituire ogni elemento in una matrice intera con il prodotto di tutti gli altri elementi.
Nel tempo lineare e nello spazio costante, possiamo utilizzare la ricorsione per affrontare questo problema. Il calcolo ricorsivo dei prodotti di ciascun elemento nel sottoarray di destra e il passaggio del prodotto del sottoarray di sinistra come parametri di funzione è la nozione.
La complessità temporale è O(n).
23. Trova l'elemento più strano in un array in tempo logaritmico
Dato un array intero in cui tutti i membri tranne uno hanno un numero pari di occorrenze, il problema è determinare quante volte questo elemento appare. Trova l'elemento dispari che si verifica nel tempo logaritmico e nello spazio costante se gli stessi elementi si trovano a coppie nell'array e non possono mai esserci più di due istanze di un dato elemento in una riga.
L'operazione XOR ci consente di risolvere questo problema in tempo lineare. L'obiettivo è XOR ogni elemento nell'array. Solo gli elementi dispari che si verificano rimangono dopo che gli elementi pari si annullano a vicenda.
Questo problema può essere risolto anche in tempo O(log(n)).
24. Come ottenere il successivo elemento più grande per ogni elemento in una matrice circolare?
Dovrebbe essere posizionato il successivo elemento più grande per ogni elemento in una matrice di interi circolari. Il primo numero intero più grande dopo un elemento x nell'array è il successivo elemento maggiore di quell'elemento.
Da destra a sinistra, possiamo operare sugli elementi dell'array. L'obiettivo è eseguire un ciclo per ogni elemento x fino a quando lo stack non è vuoto o non abbiamo un elemento più alto sopra di esso. Imposta il successivo elemento più grande di x in modo che appaia in cima alla pila quando lo fa.
25. Trovare il conteggio delle inversioni di un array?
Trova il numero totale di inversioni di una matrice. Una coppia I j) è indicata come un'inversione di un array A se I j) e (A[i] > A[j]). Dobbiamo contare ogni coppia di questi nell'array.
Il conteggio di tutti i membri dell'array inferiori a quello alla sua destra e l'aggiunta del risultato all'output è un approccio semplice.
Questa soluzione ha una complessità O(n2), dove n è la dimensione dell'input.
26. Qual è il problema di intrappolamento dell'acqua piovana?
Trovare la maggior parte dell'acqua che può essere intrappolata in un dato set di barre con una larghezza di un'unità ciascuna è noto come il problema della "pioggia intrappolata".
L'obiettivo è determinare la barra più alta che può essere posizionata a sinistra ea destra di ciascuna barra. Il minimo delle barre principali a sinistra ea destra, meno l'altezza della barra attuale, è la quantità d'acqua che viene immagazzinata sopra ciascuna barra.
Conclusione
Rispetto ad altri argomenti relativi alla struttura dei dati, gli array sono più semplici. Per rispondere alle domande dell'intervista con gli array, è necessario avere una conoscenza fondamentale degli array.
Dovresti esaminare in modo approfondito le basi degli array, comprese le operazioni sugli array (dalla dichiarazione/creazione di un array all'accesso/modifica degli elementi dell'array), nonché concetti di programmazione come loop, ricorsione e operatori di base per rispondere con successo alle domande del colloquio di array. Riconosci completamente il problema.
Dovresti chiedere chiarimenti in caso di domande. Pensa a dividere il problema in parti più gestibili. Assicurati di avere in mente l'algoritmo prima di iniziare a programmare; annotarlo o visualizzarlo in un diagramma di flusso. quindi inizia a scrivere il codice.
Lascia un Commento