Le 30 migliori domande e risposte per interviste su strutture dati e algoritmi [per principianti ed esperti]

Le Strutture Dati e gli Algoritmi sono tra le materie più importanti nel mondo dell'Informatica e dell'Ingegneria. Se ti presenti per un colloquio di ingegneria del software, puoi essere certo di dover affrontare una serie di domande appositamente dedicate alle strutture dei dati e agli algoritmi: ecco quanto sono cruciali!

Gli algoritmi sono alla base di tutto ciò che accade nell'informatica e nella scienza dei dati. Dal Machine Learning all'IA alla Blockchain: tutte le tecnologie funzionano su algoritmi. E gli algoritmi hanno bisogno di strutture dati per funzionare. Pertanto, la conoscenza combinata di strutture dati e algoritmi può aiutarti a distinguerti dalla massa durante il colloquio.

Tuttavia, la sfida è che il DSA è un dominio esteso. Qui, l'apprendimento non si ferma mai e c'è sempre qualche nuovo sviluppo che devi capire. Sebbene il continuo aggiornamento delle competenze sia obbligatorio quando si tratta di strutture di dati e algoritmi, oggi esamineremo alcuni fondamenti DSA che ti aiuteranno a superare i colloqui tecnici.

Top Strutture di dati e algoritmi Intervista Domande e risposte

1. Cosa capisci di "Strutture di dati"?

Le strutture dati possono essere definite come tecniche utilizzate per definire, archiviare e accedere ai dati in modo sistematico. Costituiscono il componente più importante di qualsiasi algoritmo. A seconda del tipo di strutture dati, memorizzano diversi tipi di dati e sono accessibili in modi diversi. Affinché un algoritmo restituisca un risultato, deve operare e manipolare un insieme di strutture di dati in modo organizzato ed efficiente per arrivare al risultato finale.

2. Come puoi distinguere tra una struttura di file e una struttura di dati?

In Strutture di file, i dati vengono archiviati su dischi in base a criteri di archiviazione file standard e non sono compatibili con applicazioni esterne di terze parti. In Data Structures, invece, i dati sono archiviati sia sul disco che sulla RAM in criteri di archiviazione personalizzati, altamente compatibili con app esterne.

3. Quali sono i tipi generali di strutture dati?

Le strutture dati possono essere sostanzialmente suddivise in due categorie:

• Lineare: in questo, tutti gli elementi vengono memorizzati in sequenza e il recupero avviene in modo lineare. La disposizione non è gerarchica e ogni elemento ha un successore e un predecessore. Esempio: matrici, elenchi collegati, stack, code, ecc.
• Non lineare: qui la memorizzazione non avviene in una sequenza lineare, ovvero tutti gli elementi non hanno necessariamente un solo successore e predecessore. Al contrario, gli elementi nelle strutture dati non lineari sono collegati a due o più elementi in modo non lineare. Esempio: alberi, grafici, heap.

4. Quali sono alcune aree chiave di utilizzo delle strutture dati?

Le strutture dati sono praticamente richieste in tutti i campi dell'informatica che ti vengono in mente, in particolare algoritmi e ottimizzazione degli algoritmi. Ecco alcune altre aree in cui le strutture dati sono ampiamente utilizzate:

• Progettazione del sistema operativo
• Analisi numerica
• Apprendimento automatico e intelligenza artificiale
• Progettazione e sviluppo di compilatori
• Gestione del database
• Analisi lessicale
• Programmazione grafica
• Algoritmi di ricerca e ordinamento e altro ancora.

5. Spiega la struttura dei dati dello stack e menziona le sue aree di utilizzo.

Stack è semplicemente un elenco ordinato che consente l'inserimento e l'eliminazione solo da una delle estremità, nota come "parte superiore". È una struttura dati ricorsiva che ha un puntatore ai suoi elementi "top" che ci consente di conoscere l'elemento più in alto dello Stack. In base alla strategia di recupero degli elementi, Stack è anche noto come Last-In-First-Out, poiché l'ultimo elemento inserito nello stack sarà in cima e sarà il primo ad essere estratto. Ecco alcuni usi della struttura dei dati dello stack:

• Tornare indietro
• Gestione della memoria
• Funzione di ritorno e chiamata
• Valutazione dell'espressione

6. Quali sono le operazioni che possono essere eseguite su uno stack?

Stack Data Structure supporta le tre operazioni seguenti:

• push() — per inserire un elemento nella prima posizione dello Stack.
• pop() — per far uscire un elemento dalla cima dello Stack.
• peek() — per controllare semplicemente l'elemento presente in cima allo Stack senza portarlo fuori dallo Stack.

7. Cosa capisci delle espressioni Postfix?

Postfix Expression è un'espressione in cui gli operatori seguono gli operandi. Questo è estremamente vantaggioso in termini di calcolo poiché non richiede alcun raggruppamento di sottoespressioni tra parentesi o addirittura considera la precedenza dell'operatore. L'espressione a+b è semplicemente rappresentata come ab+ in suffisso.

8. Come vengono archiviati nella memoria gli elementi dell'array 2D?

Gli elementi di un array 2D possono essere archiviati nella memoria in uno dei due modi seguenti:

• Row-Major: in questo metodo, prima tutte le righe dell'array vengono archiviate in modo contiguo nella memoria. Per prima cosa viene memorizzata completamente la 1a riga, quindi la 2a riga e così via fino all'ultima.
• Column-Major: in questo, tutte le colonne dell'array vengono continuamente archiviate nella memoria. Innanzitutto, la prima colonna viene archiviata completamente, quindi la seconda colonna e così via.

9. Definire la struttura dei dati dell'elenco collegato.

Gli elenchi collegati sono raccolte di nodi, che sono oggetti archiviati in modo casuale. Ogni nodo ha due elementi interni: un campo Dati e un campo Collegamento. Il campo Dati contiene il valore che ha il nodo particolare, mentre il campo Collegamento ha un puntatore al nodo successivo a cui questo è collegato. A seconda della situazione, una Linked List può essere considerata sia come una struttura dati lineare che non lineare.

10. In che modo le liste collegate sono migliori degli array?

Gli elenchi collegati sono migliori degli array nei seguenti modi:

• Le dimensioni degli array sono fisse in fase di esecuzione e non possono essere modificate in seguito, ma gli elenchi collegati possono essere espansi in tempo reale, secondo i requisiti.
• Gli elenchi collegati non vengono archiviati in modo contiguo nella memoria, di conseguenza sono molto più efficienti in termini di memoria rispetto agli array archiviati staticamente.
• Il numero di elementi che possono essere archiviati in qualsiasi Linked List è limitato al solo spazio di memoria disponibile, mentre il numero di elementi è limitato dalla dimensione dell'array.

11. Nel linguaggio di programmazione C, quale puntatore useresti per implementare una lista concatenata eterogenea?

Elenchi collegati eterogenei, come suggerisce il nome, contengono tipi di dati diversi. Di conseguenza, qui non è possibile utilizzare puntatori ordinari. Quindi, i puntatori Void vengono normalmente utilizzati in uno scenario del genere poiché sono in grado di puntare a qualsiasi tipo di valore.

12. Che cos'è una lista doppiamente collegata?

Come suggerisce il nome, una lista doppiamente collegata è una lista collegata che ha nodi collegati sia al nodo successivo che a quello precedente. Di conseguenza, i nodi di Double Linked List hanno tre, non due, campi:

• Il campo dati
• Puntatore successivo (per puntare al nodo successivo)
• Puntatore precedente (per puntare il nodo precedente)

13. Spiega la struttura dei dati della coda con alcune delle sue applicazioni.

Una coda è un elenco ordinato che consente l'inserimento e la cancellazione di elementi non da una ma da due estremità, chiamate REAR e FRONT. L'inserimento avviene dall'estremità ANTERIORE mentre la cancellazione dall'estremità POSTERIORE. Di conseguenza, la coda è spesso chiamata First-In-First-Out (FIFO). Ecco alcune applicazioni diffuse di Code come struttura dati:

• Per le liste di attesa per risorse condivise singolarmente come CPU, stampante, disco, ecc.
• Per il trasferimento asincrono di dati, file di esempio IO, socket, pipe.
• Come buffer nella maggior parte delle applicazioni del lettore multimediale.
• Nei sistemi operativi per la gestione delle interruzioni.

14. Puoi elencare alcuni inconvenienti dell'implementazione di code usando gli array?

Ci sono principalmente due inconvenienti che si verificano quando si implementano code con array:

• Cattiva gestione della memoria, poiché gli array sono strutture di dati statici, quindi l'implementazione di code con array rimuove molte funzionalità delle code.
• Problema con le dimensioni, poiché le dimensioni dell'array vengono definite durante la definizione dell'array. Quindi, se vogliamo aggiungere più elementi alla nostra coda rispetto alla dimensione dell'array, non sarà possibile.

15. Quali condizioni devono essere soddisfatte affinché un elemento venga inserito in una coda circolare?

Ecco alcune condizioni rilevanti per l'inserimento in code circolari:

• If (rear + 1)%maxsize == front -> significa che la coda è piena -> non è più possibile l'inserimento.
• Se rear != max – 1, il valore di rear viene incrementato a maxsize e un nuovo valore verrà inserito all'estremità posteriore.
• Se front != 0 e back == max -1 –> significa che la coda non è piena. Quindi, il valore di rear viene impostato su 0 e un nuovo elemento viene inserito nell'estremità posteriore della coda circolare.

16. Che cos'è una coda?

Coda a doppia estremità o deque è un insieme ordinato di elementi che facilita l'inserimento e l'eliminazione da entrambe le estremità, posteriore e anteriore. Di conseguenza, questo è ancora più flessibile della struttura dei dati della coda.

17. Definire la struttura dei dati dell'albero ed elencare alcuni tipi di alberi.

Tree è una struttura di dati non lineare e ricorsiva che contiene vari nodi. Un nodo particolare è designato come radice dell'albero da cui emergono tutti gli altri nodi. A parte root, tutti gli altri nodi sono chiamati nodi figli. Esistono sostanzialmente i seguenti tipi di strutture dati ad albero:

• Alberi generali
• Alberi binari
• Alberi di ricerca binari
• Foreste
• Albero delle espressioni
• Albero del torneo

18. Come funziona l'ordinamento a bolle?

Bubble Sort è uno degli algoritmi di ordinamento più utilizzati e viene utilizzato con gli array confrontando elementi adiacenti e scambiando le loro posizioni in base ai loro valori. Si chiama bubble sort perché la visualizzazione di come funziona è come bolle che galleggiano dall'alto dell'acqua e entità più grandi che affondano.

Leggi: Strutture dati in C e come usarle?

19. Qual è l'algoritmo di ordinamento più veloce disponibile?

Sono disponibili molti algoritmi di ordinamento diversi, come merge sort, quick sort, bubble sort e altro ancora. Tra questi, non possiamo scegliere un algoritmo specifico che sia oggettivamente il più veloce poiché le loro prestazioni variano notevolmente in base ai dati di input, alla reazione dopo che l'algoritmo ha elaborato i dati e al modo in cui vengono archiviati.

20. Cosa sono gli alberi binari?

Gli alberi binari sono tipi speciali di alberi in cui ogni nodo può avere MASSIMO due figli. Per semplificare le cose, gli alberi binari sono generalmente divisi in tre insiemi disgiunti: nodo radice, sottoalbero destro e sottoalbero sinistro.

21. In che modo gli alberi AVL possono essere utilizzati in varie operazioni rispetto a BST?

Gli alberi AVL sono alberi equilibrati in altezza, quindi non consentono all'albero di essere inclinato da un lato qualsiasi. Il tempo impiegato per tutte le operazioni eseguite su BST di altezza h è O(h). Tuttavia, questo può continuare ad essere O(n) nel peggiore dei casi, dove la BST diventa distorta. AVL aiuta ad eliminare questa limitazione limitando l'altezza dell'albero. In tal modo, impone un limite superiore a tutte le operazioni per essere massimo di O(log n) dove n = numero di nodi.

22. Quali sono le proprietà di un B-Tree?

Un albero B di un ordine m contiene le seguenti proprietà:

• Tutte le proprietà di un albero M-way.
• Ogni nodo del B_tree avrà un massimo di m figli.
• Ogni nodo eccetto radice e foglia avrà almeno m / 2 figli.
• Il nodo radice deve avere almeno 2 nodi figlio.
• Tutti i nodi foglia devono trovarsi sullo stesso livello orizzontale.

23. Cosa capisci della struttura dei dati del grafico?

La struttura dati Graph (G) può essere definita come un insieme ordinato G(V,E) dove V rappresenta l'insieme dei vertici ed E sono gli archi che formano le connessioni. Fondamentalmente, un grafico può essere pensato come un albero ciclico in cui i nodi possono mantenere relazioni complesse tra loro e non solo relazioni genitore-figlio.

24. Distinguere tra ciclo, percorso e circuito con riferimento alla struttura dati del grafico.

Le differenze tra il ciclo, il percorso e il circuito sono le seguenti:

• Una patch è un ordine di vertici vicini collegati da spigoli senza alcuna restrizione.
• Un ciclo è un percorso chiuso in cui il vertice iniziale è uguale al vertice finale. In un ciclo, nessun vertice particolare può essere visitato due volte.
• Un circuito, come un ciclo, è un percorso chiuso con il vertice iniziale uguale al vertice finale. Tuttavia, qualsiasi vertice particolare in un circuito può essere visitato più di una volta.

25. Come funziona l'algoritmo di Kruskal?

L'algoritmo di Kruskal considera il grafo come una foresta e ciascuno dei suoi nodi come un albero individuale. Si dice che un albero si connetta a un altro albero se e solo se ha il costo minore tra tutte le opzioni e non viola alcuna proprietà di un albero di copertura minimo (MST).

Correlati: albero binario nella struttura dei dati

26. In che modo l'algoritmo di Prim trova lo spanning tree?

L'algoritmo di Prim funziona considerando i nodi come singoli alberi. Quindi, continua ad aggiungere nuovi nodi allo spanning tree dal grafico dato che deve essere convertito nello spanning tree richiesto.

27. Che cos'è un albero di copertura minimo (MST)?

Gli MST, nei grafici pesati, sono alberi che hanno un peso minimo, ma si estendono su tutti i vertici.

28. Cos'è una funzione ricorsiva?

Per definizione, una funzione ricorsiva richiama se stessa o chiama direttamente una funzione che la chiama. Ogni funzione ricorsiva ha alcuni criteri di base, in base ai quali la funzione smette di chiamare se stessa.

29. Qual è la tecnica di ricerca per interpolazione?

La tecnica di ricerca per interpolazione è una modifica rispetto al metodo di ricerca binaria. L'algoritmo di ricerca per interpolazione lavora sulla posizione di tastatura dei valori desiderati.

30. Cos'è l'hashing?

L'hashing è una tecnica molto utile utilizzata per convertire un intervallo di coppie chiave-valore in indici di un array. Le tabelle hash sono utili durante la creazione di un archivio dati associativo in cui è possibile trovare facilmente l'indice dei dati semplicemente fornendo la sua coppia chiave-valore!

In conclusione

Le strutture dati sono davvero le fondamenta di tutto ciò che accade in Informatica. Anche le applicazioni più complesse dell'Informatica, come Data Science, Machine Learning, Intelligenza Artificiale, IoT, sono tutte costruite su Strutture Dati e Algoritmi.

Quindi, se sei un principiante che cerca di fare carriera in uno qualsiasi dei campi della new age, ti consigliamo di iniziare padroneggiando le strutture dei dati e gli algoritmi. Oppure, puoi anche dare un'occhiata al nostro corso sul programma Executive PG in Data Science , progettato per i principianti. Impara da zero e diventa un esperto di Data Science. Iscriviti oggi stesso!