Molti programmatori e i miei lettori mi hanno chiesto di condividere alcune domande di intervista di codifica basate su albero binario, proprio come ho fatto per l’array, linked list, string, software design, patterns, hash table e data structure in generale. Questo compito è stato in realtà in sospeso per un bel po ‘ di tempo ed è stato bloccato per me cercando di trovare la soluzione per ogni domanda che avrei potuto raccogliere. Così, ho deciso di pubblicare l’elenco delle domande di intervista ad albero binario ora e possibilmente pubblicare la soluzione come articolo separato in seguito. Questo è come creare un’interfaccia e fornire l’implementazione in seguito in modo da non bloccare altre persone che dipendono dalla tua interfaccia (in realtà, questo è un vantaggio dell’utilizzo dell’interfaccia in Java o in qualsiasi altro linguaggio di programmazione).
Che cos’è la struttura dati ad albero binario?
Ad ogni modo, tornando a un albero binario, vorrei ripetere alcuni dei punti utili sulla struttura dei dati dell’albero in generale che ti aiuteranno a risolvere queste domande da solo:
1) Un albero è la struttura dati gerarchica a differenza di un array o di un elenco collegato che sono lineari. Ciò significa che è possibile memorizzare informazioni gerarchiche utilizzando una struttura dati ad albero, come una struttura organizzativa, un albero genealogico, ecc.
2) Un albero ha nodi e figli. Il nodo superiore o primo è chiamato radice.
3) Se si desidera visualizzare, la struttura dei dati ad albero è come un albero invertito nel mondo reale. Voglio dire, quando vedi alberi intorno a te, le loro radici sono in basso, ma quando disegni una struttura dati ad albero in programmazione o informatica, la loro radice è in cima.
4) Un albero binario è un albero speciale, dove puoi avere al massimo due bambini. Ciò significa che un nodo non può essere un bambino, un bambino o due bambini. Non possono avere tre figli o più.
5) Tutti i nodi che non hanno figli sono noti come nodo foglia.
6) L’albero di ricerca binario è un tipo speciale di albero binario in cui i valori dei sottoalberi di sinistra sono inferiori o uguali a root e i valori dei nodi sui sottoalberi di destra sono maggiori o uguali a root. Ciò fornisce una struttura di ordinamento a un albero di ricerca binario, che rende la ricerca molto veloce.
Puoi anche controllare le strutture dati e gli algoritmi: Deep Dive Usando il corso Java su Udemy per saperne di più sugli alberi di ricerca binari. È uno dei migliori corsi per aggiornare le tue capacità di struttura dati e algoritmi.
7) L’albero di ricerca binaria è strettamente associato a una ricerca binaria che funziona sul principio di ridurre la dimensione dell’input a metà dopo ogni iterazione. Questo rende la ricerca molto veloce e puoi trovare qualsiasi elemento nell’albero di ricerca binario sul tempo O(logN), ma solo se l’albero è bilanciato.
8 )Ci sono due modi per attraversare una struttura dati ad albero, prima la profondità o prima il livello. In profondità-in primo luogo, si scende fino a quando non c’è più nodo da visitare e poi si torna a visitare i nodi sullo stesso livello.
Durante l’attraversamento dell’ordine di livello, si visitano tutti i nodi allo stesso livello prima di passare al livello successivo. C’è anche pre-order, post-order e in-order traversal for binary che viene utilizzato per attraversare i nodi di un albero binario. Inorder traversal è speciale perché visita tutti i nodi in ordine ordinato.
9) Un albero binario bilanciato è come avere un numero uguale di nodi su ogni sottoalbero se hai tutti i nodi sull’unico sottoalbero sinistro o destro che il tuo albero binario diventerà non bilanciato e agirà come un elenco collegato come mostrato nel diagramma seguente:
10) Un albero di ricerca binario sbilanciato o non bilanciato agisce come un elenco collegato in cui una ricerca richiederà tempo O(n) rispetto al tempo O(logN) in un albero di ricerca binario bilanciato.
Questi sono alcuni dei punti importanti che ogni programmatore dovrebbe conoscere sulla struttura dei dati ad albero binario. Ti aiuterà a risolvere i problemi di codifica basati su alberi. Se vuoi saperne di più sull’albero binario e su altre strutture dati, ti suggerisco di unirti a un buon corso di struttura dati e algoritmo come Strutture dati e algoritmi: Deep Dive Usando Java su Udemy per spazzolare i tuoi fondamenti.
40+ Domande di intervista ad albero binario per programmatori Java
Senza perdere altro tempo, ecco la mia lista dei problemi di codifica basati su binary tree e binary search tree (BST) dai colloqui di lavoro di programmazione. Ho collegato alla soluzione ovunque sia possibile, ma se non c’è alcun collegamento, puoi anche trovare una soluzione semplicemente facendo una ricerca su Google. Sono domande molto popolari e molte persone le hanno già risolte.
Per ottenere il massimo da questa lista, prova a risolvere il problema prima di esaminare la soluzione solo allora la tua mente funzionerà e dovrai affrontare sfide e consolidare la tua comprensione. Se guardi immediatamente la soluzione, imparerai solo il 10%, ma se ci provi imparerai dall ‘ 80 al 90% dei concetti e dei trucchi dietro ogni domanda.
1) Come si trova l’antenato comune più basso di un albero binario in Java? (soluzione)
2) Come si stampa la vista a sinistra di un albero binario in Java? (soluzione)
3) Scrivi un programma per costruire un albero da Inorder e PreOrder traversal in Java? (soluzione)
4) Come si stampano nodi comuni in due alberi di ricerca binari in Java? (soluzione)
5) Perché binary heap è una scelta migliore rispetto a BST per l’implementazione della coda di priorità? (risposta)
6) Come si controlla se un determinato albero binario è bilanciato o meno? Scrivi un metodo Java, che accetta un albero binario e restituisce true se è bilanciato o false altrimenti. (soluzione)
7) Quali sono alcuni vantaggi di un albero di ricerca binario su una struttura di dati hashtable? (risposta)
8) Come si controlla se un dato albero binario è un sottoalbero di un altro albero binario? (soluzione)
Hai dato due alberi binari e devi restituire true se un primo albero binario è un sottoalbero del secondo. Un sottoalbero di albero binario BT è un albero T costituito da un nodo da BT e tutti i suoi discendenti. Ad esempio, nel caso seguente, T1 è un sottoalbero dell’albero binario BT
9) Come si trova la distanza tra due nodi in un albero binario? (soluzione)
10) Come trovare l’antenato comune più basso in un albero binario in Java? (soluzione)
11) Scrivi un programma Java per verificare se tutte le foglie di un determinato albero binario sono allo stesso livello? (soluzione)
12) Come si converte un determinato albero binario in un doppio elenco collegato in Java? (soluzione)
13) Scrivi un programma per trovare una profondità di un dato albero binario in Java? (soluzione)
14) Qual è la differenza tra alberi di ricerca binari e binari? (risposta)
15) Che cos’è un albero auto-bilanciato? (risposta)
16) Qual è l’albero AVL? (risposta)
17) Scrivi un programma Java per stampare l’attraversamento pre-ordine di un albero di ricerca binario? Dare una soluzione usando sia l’iterazione che la ricorsione? (soluzione)
18) Stampa l’attraversamento post-ordine di BST? Dare algoritmo iterativo e ricorsivo (soluzione)
19) Stampare l’attraversamento inorder di un BST in Java? Dare sia algoritmi iterativi che ricorsivi (soluzione)
20) Hai dato un BST, dove due nodi vengono scambiati? Come si fa a recuperare il BST originale? (soluzione)
21) Come si converte un albero binario in un albero di ricerca binario in Java? (soluzione)
22) Trova il sottoalbero BST più grande di un dato albero binario in Java? (soluzione)
23) Scrivere un programma Java per collegare i nodi allo stesso livello di un albero binario? (soluzione)
24) Che cos’è una struttura dati Trie? (risposta)
25) Qual è la differenza tra l’albero binario e Trie? (risposta)
26) Stampa antenati di un dato nodo di un albero binario in Java? (soluzione)
27) Scrivere un programma Java per stampare il livello di un dato nodo in un albero binario? (soluzione)
28) Stampa nodi comuni di due dati BST in Java? (soluzione)
29) Dare un albero binario, stampare tutto il percorso root-to-leaf in Java? (soluzione)
30) Stampa Inorder tree traversal senza ricorsione in Java? (soluzione)
31) Stampa preordine tree traversal senza ricorsione e stack in Java? (soluzione)
32) Stampa PostOrder tree traversal senza ricorsione in Java? (soluzione)
33) Programma Java per verificare se un determinato albero binario è BST o no? (soluzione)
34) Scrivere un programma Java per contare i nodi foglia in un albero binario? (soluzione)
35) Scrivi un programma Java per trovare l’altezza o la profondità di un albero binario? (soluzione)
36) Come trovi se due alberi binari dati sono uguali? (soluzione)
Scrivi un metodo in Java, che accetterà due alberi binari e restituirà true se sono uguali, altrimenti restituirà false.
37) Come si elimina un dato nodo da un albero di ricerca binario in Java? (soluzione)
38) Scrivere una funzione Java per aggiungere un dato nodo in un albero di ricerca binario? (soluzione)
39) Stampa un albero binario in ordine verticale in Java? (soluzione)
40) Qual è la struttura dei dati ad albero rosso-nero? (answer)
Answer – Red-Black Tree è un albero di ricerca binario autobilanciato (BST) in cui ogni nodo ha le seguenti proprietà
a) Ogni nodo ha un colore, rosso o nero.
b) La radice dell’albero è sempre nera.
c )Non ci sono due nodi rossi adiacenti (un nodo rosso non può avere un genitore rosso o un figlio rosso).
d )Ogni percorso dalla radice a un nodo NULLO ha lo stesso numero di nodi neri.
Puoi anche controllare le strutture dati in Java: un corso di aggiornamento dell’intervista su Educative per saperne di più sulla struttura dei dati Red Black Tree.
Questo è tutto in questo elenco dei primi 40 alberi binari e problemi di codifica basati su albero di ricerca binario dalle interviste di programmazione. Anche se la soluzione è data in linguaggio di programmazione Java, siete invitati a risolvere queste domande su qualsiasi linguaggio di programmazione di vostra scelta come Python, C, C++, JavaScript, Ruby, o anche Swift. Puoi anche pubblicare la tua soluzione nella sezione commenti in modo che la comunità possa rivedere la tua soluzione e fornire alcuni feedback utili.
Tutto il meglio per la tua intervista di codifica.
Ulteriore apprendimento
11 Domande essenziali di codifica intervista.
Master the Coding Interview: Strutture dati + algoritmi
Grokking the Coding Interview: Modelli per domande di codifica
Altre domande di intervista di codifica l ti potrebbe piacere
- Come implementare l’algoritmo di ordinamento di inserimento in Java? (tutorial)
- Come applicare l’algoritmo Quicksort sul posto in Java? (tutorial)
- Come implementare l’algoritmo di ordinamento a bolle in Java? (tutorial)
- Differenza tra algoritmo di ordinamento basato sul confronto e non sul confronto? (risposta)
- Come applicare Bucket Sort in Java? (tutorial)
- Come implementare l’algoritmo Quicksort senza ricorsione? (tutorial)
- Come eseguire un algoritmo di ricerca binario in Java? (tutorial)
- Come trovare tutte le coppie in un array la cui somma è uguale a k (solution)
- Come rimuovere i duplicati da un array in Java? (soluzione)
- Come trovare il numero più significativo e più piccolo in un array senza ordinamento? (soluzione)
- Come trovare i duplicati da un array non ordinato in Java? (soluzione)
- Come trovare un numero mancante in un array ordinato? (solution)
- Come trovare un valore mancante da un array contenente da 1 a 100? (soluzione)
- 50+ Struttura dati e algoritmi Problemi da interviste (domande)
- I miei corsi gratuiti preferiti per imparare la struttura dei dati in profondità (FreeCodeCamp)
- Come rimuovere un elemento da un array in Java? (soluzione)
- Come verificare se un array contiene un valore particolare? (soluzione)
- 10 Corsi gratuiti di struttura dati e algoritmi per programmatori (corsi)
- 100 + Problemi di codifica della struttura dati da interviste (domande)
Grazie per aver letto questo articolo. Se ti piace questo articolo, per favore condividilo con i tuoi amici e colleghi. Se avete domande o commenti, quindi si prega di rilasciare una nota.
P. S.-Se stai cercando alcuni corsi di algoritmi gratuiti per migliorare la tua comprensione della struttura dei dati e degli algoritmi, dovresti anche controllare il corso di strutture dati facili e avanzate su Udemy. E ‘ scritto da un ingegnere del software di Google ed esperto di algoritmi, ed è completamente gratuito.