många programmerare och mina läsare har bett mig att dela några binära trädbaserade kodningsintervjufrågor, precis som jag har gjort för array, länkad lista, sträng, mjukvarudesign, mönster, hashtabell och datastruktur i allmänhet. Denna uppgift väntade faktiskt ganska länge och det var fast för mig att försöka hitta lösningen för varje fråga jag kunde ha samlat in. Så, jag bestämde mig för att publicera listan över binära träd intervjufrågor nu och eventuellt publicera lösningen som en separat artikel senare. Det här är som att skapa ett gränssnitt och tillhandahålla implementering senare så att du inte blockerar andra personer som är beroende av ditt gränssnitt (det är faktiskt en fördel med att använda gränssnittet i Java eller något annat programmeringsspråk).
Vad är binär Träddatastruktur?
hur som helst, när jag kommer tillbaka till ett binärt träd, skulle jag vilja upprepa några av de användbara punkterna om träddatastruktur i allmänhet som hjälper dig att lösa dessa frågor på egen hand:
1) ett träd är den hierarkiska datastrukturen till skillnad från en array eller länkad lista som är linjär. Det betyder att du kan lagra hierarkisk information med hjälp av en träddatastruktur, som en organisationsstruktur, släktträd etc.
2) ett träd har noder och barn. Den övre eller första noden kallas roten.
3) Om du vill visualisera är träddatastrukturen som ett inverterat träd i den verkliga världen. Jag menar, när du ser träd omkring dig, är deras rötter i botten men när du ritar en träddatastruktur i programmering eller datavetenskap, är deras rot på toppen.
4) ett binärt träd är ett speciellt träd, där du kan ha högst två barn. Det betyder att en nod kan antingen inget barn, ett barn eller två barn. De kan inte ha tre barn eller fler.
5) alla noder som inte har några barn är kända som en bladnod.
6) binärt sökträd är en speciell typ av binärt träd där värden för vänster underträd är mindre än eller lika med rot och värden för noder på höger underträd är större än eller lika med rot. Detta ger en sorteringsstruktur till ett binärt sökträd, vilket gör sökningen riktigt snabb.
du kan också kontrollera datastrukturer och algoritmer: djupdykning med Java-kurs på Udemy för att lära dig mer om binära sökträd. Det är en av de bästa kurserna för att uppdatera din datastruktur och algoritmer färdigheter.
7) det binära sökträdet är nära förknippat med en binär sökning som fungerar på principen att minska inmatningsstorleken till hälften efter varje iteration. Detta gör sökningen riktigt snabb och du kan hitta något element i det binära sökträdet på O(logN) tid, men bara om trädet är balanserat.
8) Det finns två sätt att korsa en träddatastruktur, djup först eller nivå först. På djupet-först går du ner tills det inte finns mer nod att besöka och sedan kommer du tillbaka för att besöka noder på samma nivå.
medan du går i nivåordning, besöker du alla noder på samma nivå innan du går vidare till nästa nivå. Det finns också förbeställning, postorder och in-order traversal för binär som används för att korsa noder av ett binärt träd. Inorder traversal är speciellt eftersom det besöker alla noder i sorterad ordning.
9) ett balanserat binärt träd är som att ha lika många noder på varje underträd om du har alla noder på det enda vänstra eller högra underträdet än ditt binära träd blir obalanserat och det kommer att fungera som en länkad lista som visas i diagrammet nedan:
10) ett obalanserat eller icke-balanserat binärt sökträd fungerar som en länkad lista där en sökning tar O(n) tid i motsats till O(logN) tid i ett balanserat binärt sökträd.
det här är några av de viktiga punkterna som varje programmerare borde veta om binär träddatastruktur. Det hjälper dig att lösa trädbaserade kodningsproblem. Om du vill lära dig mer om binary tree och andra datastrukturer föreslår jag att du går med i en bra datastruktur och algoritmkurs som datastrukturer och algoritmer: djupdykning med Java på Udemy för att borsta dina grunder.
40+ Binary Tree intervjufrågor för Java programmerare
utan att slösa mer av din tid, här är min lista över binary tree och binary search tree (BST) baserade kodningsproblem från programmering jobbintervjuer. Jag har länkat till lösning där det är möjligt men om det inte finns någon länk kan du också hitta en lösning genom att bara göra en Google-sökning. De är mycket populära frågor och många har redan löst dem.
för att få ut det mesta av den här listan, försök lösa problemet innan du tittar på lösningen först då kommer ditt sinne att fungera och du kommer att möta utmaningar och konsolidera din förståelse. Om du tittar på lösningen omedelbart lär du dig bara 10% men om du försöker lär du dig 80 till 90% av koncept och tricks bakom varje fråga.
1) Hur hittar du den lägsta gemensamma förfadern till ett binärt träd i Java? (lösning)
2) Hur skriver du ut den vänstra vyn av ett binärt träd i Java? (lösning)
3) Skriv ett program för att konstruera ett träd från Inorder och förbeställa traversal i Java? (lösning)
4) Hur skriver du ut vanliga noder i två binära sökträd i Java? (lösning)
5) Varför binär heap är ett bättre val än BST för att implementera prioritetskö? (svar)
6) Hur kontrollerar du om ett givet binärt träd är balanserat eller inte? Skriv en Java-metod, som accepterar ett binärt träd och returnerar sant om det är balanserat eller falskt på annat sätt. (lösning)
7) Vilka är några fördelar med ett binärt sökträd över en hashtable datastruktur? (svar)
8) Hur kontrollerar du om ett givet binärt träd är ett underträd av ett annat binärt träd? (lösning)
du har gett två binära träd, och du måste returnera true om ett första binärt träd är ett underträd av det andra. Ett subtree av binärt träd BT är ett träd T bestående av en nod från BT och alla dess ättlingar. Till exempel, i följande fall är T1 ett underträd av binärt träd BT
9) Hur hittar du avståndet mellan två noder i ett binärt träd? (lösning)
10) Hur hittar man den lägsta gemensamma förfadern i ett binärt träd i Java? (lösning)
11) Skriv ett Java-program för att kontrollera om alla blad i ett givet binärt träd är på samma nivå? (lösning)
12) Hur konverterar du ett givet binärt träd till dubbellänkad lista i Java? (lösning)
13) Skriv ett program för att hitta ett djup för ett givet binärt träd i Java? (lösning)
14) Vad är skillnaden mellan binära och binära sökträd? (svar)
15) Vad är ett självbalanserat träd? (svar)
16) Vad är AVL-trädet? (svar)
17) Skriv ett Java-program för att skriva ut förbeställning av ett binärt sökträd? Ge en lösning med både iteration och rekursion? (lösning)
18) Skriv ut post-order traversal av BST? Ge iterativ och rekursiv algoritm (lösning)
19) Skriv ut inorder traversal av en BST i Java? Ge både iterativa och rekursiva algoritmer (lösning)
20) du har gett en BST, där två noder byts ut? Hur återställer du den ursprungliga BST? (lösning)
21) Hur konverterar du ett binärt träd till ett binärt sökträd i Java? (lösning)
22) hitta det största BST-underträdet för ett givet binärt träd i Java? (lösning)
23) Skriv ett Java-program för att ansluta noder på samma nivå som ett binärt träd? (lösning)
24) Vad är en Trie datastruktur? (svar)
25) Vad är skillnaden mellan det binära trädet och Trie? (svar)
26) Skriv ut förfäder till en given nod i ett binärt träd i Java? (lösning)
27) Skriv ett Java-program för att skriva ut nivån på en given nod i ett binärt träd? (lösning)
28) Skriv ut vanliga noder av två givna BST i Java? (lösning)
29) ge ett binärt träd, Skriv ut alla rot-till-blad-sökvägar i Java? (lösning)
30) Skriv ut Inorder tree traversal utan rekursion i Java? (lösning)
31) Skriv ut förbeställning träd traversal utan rekursion och stack i Java? (lösning)
32) Skriv ut PostOrder träd traversal utan rekursion i Java? (lösning)
33) Java-Program för att kontrollera om ett givet binärt träd är BST eller inte? (lösning)
34) Skriv ett Java-Program för att räkna bladnoder i ett binärt träd? (lösning)
35) Skriv ett Java-program för att hitta höjden eller djupet på ett binärt träd? (lösning)
36) hur hittar du om två givna binära träd är desamma? (lösning)
Skriv en metod i Java, som accepterar två binära träd och returnerar true om de är desamma, annars returnerar false.
37) Hur tar du bort en given nod från ett binärt sökträd i Java? (lösning)
38) Skriv en Java-funktion för att lägga till en given nod i ett binärt sökträd? (lösning)
39) Skriv ut ett binärt träd i vertikal ordning i Java? (lösning)
40) Vad är den röd-svarta Träddatastrukturen? (svar)
svar – Röd-svart träd är ett självbalanserande binärt sökträd (BST) där varje nod har följande egenskaper
a) varje nod har en färg, antingen röd eller svart.
b) trädets rot är alltid svart.
c) det finns inga två intilliggande röda noder (en röd nod kan inte ha en röd förälder eller rött barn).
d) varje väg från roten till en NOLLNOD har samma antal svarta noder.
du kan också kontrollera datastrukturer i Java: en intervju repetitionskurs på Educative att lära sig mer om Red Black Tree datastruktur.
det är allt i den här listan över topp 40 binära träd och binära sökträdbaserade kodningsproblem från programmeringsintervjuer. Även om lösningen ges i Java-programmeringsspråk är du välkommen att lösa dessa frågor på valfritt programmeringsspråk som Python, C, C++, JavaScript, Ruby eller till och med Swift. Du kan också lägga upp din lösning i kommentarfältet så att gemenskapen kan granska din lösning och ge användbar feedback.
allt det bästa för din kodningsintervju.
Vidareutbildning
11 Viktiga Kodningsintervjufrågor.
behärska Kodningsintervjun: datastrukturer + algoritmer
Grokking Kodningsintervjun: Mönster för Kodningsfrågor
andra Kodningsintervjufrågor L du kanske gillar
- hur implementerar du insättningsorteringsalgoritmen i Java? (handledning)
- Hur applicerar du Quicksort-algoritmen på plats i Java? (handledning)
- hur man implementerar Bubble sorteringsalgoritmen i Java? (handledning)
- skillnad mellan jämförelse och icke-Jämförelsebaserad sorteringsalgoritm? (svar)
- Hur ansöker jag Bucket Sort i Java? (handledning)
- hur man implementerar Quicksort-algoritmen utan rekursion? (handledning)
- hur man utför en binär sökalgoritm i Java? (handledning)
- hur hittar man alla par i en array vars summa är lika med k (lösning)
- Hur tar man bort dubbletter från en array i Java? (lösning)
- hur hittar man det mest signifikanta och minsta antalet i en array utan sortering? (lösning)
- hur hittar du dubbletter från en osorterad array i Java? (lösning)
- hur hittar man ett saknat nummer i en sorterad array? (lösning)
- hur hittar man ett saknat värde från en array som innehåller 1 till 100? (lösning)
- 50+ datastruktur och algoritmer problem från intervjuer (frågor)
- min favorit gratis kurser för att lära sig datastruktur djupgående (FreeCodeCamp)
- Hur tar man bort ett element från en array i Java? (lösning)
- Hur kontrollerar jag om en array innehåller ett visst värde? (lösning)
- 10 gratis datastruktur och Algoritmkurser för programmerare (kurser)
- 100 + Datastrukturkodningsproblem från intervjuer (frågor)
Tack för att du läste den här artikeln. Om du gillar den här artikeln, vänligen dela den med dina vänner och kollegor. Om du har några frågor eller feedback, vänligen släpp en anteckning.
P. S. – Om du letar efter några gratis algoritmer kurser för att förbättra din förståelse av datastruktur och algoritmer, så ska du också kontrollera lätt att avancerade datastrukturer kurs på Udemy. Det är författat av en Google-programvaruingenjör och Algoritmexpert, och det är helt kostnadsfritt.