Cele mai frecvente întrebări și răspunsuri la interviu cu arbore binar [pentru cei proaspăt și cu experiență]

Introducere

Structurile de date sunt unul dintre cele mai fundamentale concepte în programarea orientată pe obiecte. Pentru a explica simplu, o structură de date este un mod special de organizare a datelor într-un computer, astfel încât acestea să poată fi procesate eficient. Există mai multe structuri de date, cum ar fi stive, cozi și arbori, care au propriile lor proprietăți unice.

Arborii ne permit să organizăm datele într-un mod ierarhic. O astfel de structură de date este foarte diferită de structurile de date liniare, cum ar fi listele sau matricele legate. Un arbore este format din noduri care transportă informații.

Un arbore binar este un tip special de arbore care poate avea până la doi copii. Aceasta înseamnă că un anumit nod dintr-un arbore binar nu poate avea niciun copil, un copil sau doi copii, dar nu mai mulți. Un arbore binar este o structură de date importantă care ne poate permite să rezolvăm probleme dificile și să construim coduri complexe.

Dacă aplici pentru un loc de muncă ca dezvoltator Java sau inginer software, interviul tău poate conține mai multe întrebări care se învârt în jurul acestui concept. Adesea, candidaților le este greu să răspundă la întrebări bazate pe arbori binari, arbori binari de căutare și programe conexe. În acest articol, vom explora unele dintre cele mai frecvente întrebări de interviu legate de arborii binari. Acest articol vă va ajuta să înțelegeți mai bine conceptul și să vă pregătiți astfel încât să puteți obține jobul de vis!

Cele mai bune întrebări și răspunsuri la interviu în arbore binar

Următoarea secțiune conține un catalog de întrebări și răspunsurile așteptate ale acestora bazate pe conceptul de arbore binar.

1) Ce este un nod frunză?

Orice nod dintr-un arbore binar sau un arbore care nu are copii se numește nod frunză.

2) Ce este un nod rădăcină?

Primul nod sau nodul de sus dintr-un arbore se numește nod rădăcină.

3) Cum găsești cel mai mic strămoș comun (LCA) al unui arbore binar în Java?

Să considerăm două noduri n1 și n2 care fac parte dintr-un arbore binar.

Cel mai mic strămoș comun (LCA) al lui n1 și n2 este strămoșul comun al lui n1 și n2 care este situat cel mai departe de rădăcină.

Puteți urma următoarea metodă pentru a găsi LCA.

1. a) Găsiți o cale de la nodul rădăcină la n1 și stocați-o într-o matrice.
2. b) Găsiți o cale de la nodul rădăcină la n2 și stocați-o într-o matrice.
3. c) Parcurgeți ambele căi până când valoarea este aceeași în ambele matrice.

4) Cum verifici dacă un arbore binar dat este un subarbore al altui arbore binar?

Să considerăm că avem un arbore binar T. Acum dorim să verificăm dacă un arbore binar S este un subarbore al lui T.

Pentru a face acest lucru, mai întâi, încercați să verificați dacă găsiți un nod în T care este și în S.

Odată ce găsiți acest nod comun, verificați dacă următoarele noduri fac, de asemenea, parte din S.

Dacă da, putem spune cu siguranță că S este un subarboresc al lui T.

Trebuie citit: Idei și subiecte de proiecte cu structura datelor

5) Cum găsiți distanța dintre două noduri dintr-un arbore binar?

Luați în considerare două noduri n1 și n2 care fac parte dintr-un arbore binar.

Distanța dintre n1 și n2 este egală cu numărul minim de muchii care trebuie parcurse pentru a ajunge de la un nod la altul.

Este important să rețineți că parcurgeți cea mai scurtă distanță dintre noduri.

6) Ce este un arbore binar de căutare?

Un arbore de căutare binar (BST) este un tip special de arbore binar în care fiecare nod intern conține o cheie. Pentru un arbore de căutare binar, regula este:

1. a) Un nod poate avea o cheie care este mai mare decât toate cheile din subarborele din stânga al nodului.
2. b) Un nod poate avea o cheie mai mică decât toate cheile din subarborele din dreapta al nodului.

Astfel, dacă n1 este un nod care are o cheie 8, atunci fiecare nod din subarborele din stânga al lui n1 va conține chei mai mici decât 8 și fiecare nod din subarborele din dreapta al lui n1 va conține chei mai mari de 8.

7) Ce este un copac autoechilibrat?

Arborele de căutare binar auto-echilibrat își păstrează automat înălțimea cât mai mică posibil atunci când au loc operațiuni precum inserarea și ștergerea.

Pentru ca un BST să fie autoechilibrat, este important ca acesta să urmeze în mod constant regulile BST, astfel încât subarborele din stânga să aibă chei cu valori mai mici, în timp ce subarborele din dreapta să aibă chei cu valori mari.

Acest lucru se face folosind două operații:

– Rotire la stânga

– Rotire dreapta

8) Ce este un arbore AVL?

Arborele AVL este numit după inventatorii săi: Adelson, Velski și Landis. Un arbore AVL este un arbore binar cu auto-echilibrare care verifică înălțimea subarborelui din stânga și al subarborelui din dreapta și asigură că diferența nu este mai mare de 1. Această diferență se numește factor de echilibru

Astfel, BalanceFactor = înălțime (subarborele din stânga) – înălțime (subarborele din dreapta)

Dacă factorul de echilibru este mai mare de 1, arborele este echilibrat folosind unele dintre următoarele tehnici:

– Rotire la stânga

– Rotire dreapta

– Rotire stânga-dreapta

– Rotire dreapta-dreapta

Citește și: Sortarea în structura datelor

9) Cum convertiți un arbore binar într-un arbore binar de căutare în Java?

Principala diferență dintre un arbore binar și un arbore de căutare binar este că BST urmează subarborele din stânga ar trebui să aibă valori mai mici ale cheilor, iar subarborele din dreapta ar trebui să aibă o regulă cu valori mai mari. Acest lucru se poate face folosind o serie de tehnici de traversare, după cum urmează:

1. Creați o matrice temporară care stochează traversarea în ordine a arborelui
2. Sortați matricea temporară. Puteți utiliza orice algoritm de sortare aici.
3. Efectuați din nou o traversare în ordine pe arbore.
4. Copiați elementele matricei unul câte unul în fiecare nod de arbore.

10) Cum ștergeți un nod dintr-un arbore de căutare binar în Java?

Operația de ștergere pentru un BST poate fi dificilă, deoarece proprietățile sale trebuie păstrate după operație. Iată o privire asupra tuturor celor trei cazuri posibile:

1. Nodul de șters este un nod frunză.
   Pur și simplu eliminați nodul.
2. Nodul care urmează să fie eliminat are un copil.

În acest caz, copiați copilul în nod și ștergeți copilul.

1. Nodul de eliminat are doi copii.

În acest caz, găsiți succesorul în ordine al nodului. Puteți apoi să copiați conținutul acestuia în nod și să ștergeți succesorul în ordine.

11) Care este structura de date arbore roșu-negru?

Arborele roșu-negru este un tip special de arbore de auto-echilibrare care are următoarele proprietăți:

1. Fiecare nod are o culoare roșie sau neagră.
2. Rădăcina este întotdeauna neagră.
3. Un nod roșu nu poate avea un părinte roșu sau un copil roșu.
4. Fiecare cale de la nodul rădăcină la un nod NULL are același număr de noduri negre.

Trebuie citit: Idei și subiecte de proiecte cu structura datelor

12) Cum afli dacă doi copaci sunt identici?

Doi arbori binari sunt identici dacă au aceleași date și aranjament. Acest lucru se poate face prin parcurgerea ambilor copaci și comparând datele și aranjamentele acestora.

Iată algoritmul care ne poate permite să facem acest lucru:

1. Verificați datele nodului rădăcină (tree1 data ==tree2 data)
2. Verificați recursiv subarborele din stânga. apelați sameTree (arborele1-> subarborele stânga, arborele2-> subarborele stânga)
3. În mod similar, verificați subarborele din dreapta
4. dacă a,b,c sunt adevărate, return1

Checkout: Tipuri de arbore binar

Gânduri finale

În acest articol, am explorat unele dintre cele mai frecvente întrebări de interviu în arborele de căutare binar. Explorarea mai mult despre structurile de date vă poate ajuta să înțelegeți mai bine logica și programarea. Puteți încerca să vă uitați la exemplele menționate în acest articol și să exersați prin schimbarea valorilor pentru a vă construi bazele. Cu puțină practică, vei fi într-o poziție excelentă pentru a-ți termina interviul.

Dacă sunteți curios să aflați despre știința datelor, consultați programul Executive PG în știința datelor de la IIIT-B și upGrad, care este creat pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie, 1 -on-1 cu mentori din industrie, peste 400 de ore de învățare și asistență profesională cu firme de top.