En Çok Sorulan Veri Yapıları ve Algoritma (DSA) Röportaj Soruları
Yazılım mühendisliği dünyasında, **Veri Yapıları ve Algoritmalar (DSA)** kavramları son derece önemlidir. Bu konular, verileri nasıl yapılandırıp işleyeceğinizi anlamak, etkili ve verimli algoritmalar geliştirmek için temeldir. İşe alım süreçlerinde, özellikle yazılım mühendisliği pozisyonları için, DSA ile ilgili sorular oldukça yaygındır. Bu makalede, röportajlarda sıkça sorulan bazı DSA sorularını ve bunların çözüm stratejilerini ele alacağız.
1. Tersine Çevrilmiş Bağlantılı Liste
Bir bağlantılı listenin düğümlerinin sırasını tersine çevirmeniz istenen bu klasik soru, temel bağlantılı liste işlemlerini anladığınızı göstermenizi sağlar.
Çözüm Stratejisi
1. İlk düğümü işaret edin (başlangıç düğümü).
2. İkinci düğümü işaretleyin.
3. İlk düğümün bir sonraki göstergesini (next) ikinci düğümle değiştirin.
4. Birinci düğümü “sonraki” düğüm olarak ayarlayın.
5. İkinci düğümü “başlangıç” düğümü olarak ayarlayın.
6. Bu adımları listenin sonuna kadar tekrarlayın.
2. İki Toplam Sayıyı Tersine Çevirme
İki sayının basamakları tersine çevrilmiş olarak verildiğinde (örneğin, 321 ve 456) bu iki sayıyı toplayıp sonucu yine tersine çevrilmiş şekilde döndürmeniz istenir. Bu soru, sayı manipülasyonu ve temel algoritma anlayışınızı test eder.
Çözüm Stratejisi
1. Sayıları ayrı ayrı listeler halinde temsil edin (örneğin, 321 -> [3, 2, 1]).
2. Her iki listeyi de aynı boyuta getirmek için sıfır ekleyin.
3. Her iki listenin karşılık gelen düğümlerini toplayın.
4. Toplamı bir yeni listeye ekleyin.
5. Bu listeyi tersine çevirin.
6. Listeyi bir sayıya dönüştürün.
3. İki Sıralama Listesinde Birleştirme
İki sıralı bağlantılı listenizi birleştirerek yeni bir sıralı bağlantılı liste oluşturmanız gereken bu soru, verimli bir algoritma oluşturma becerinizi göstermenizi sağlar.
Çözüm Stratejisi
1. İki liste için ayrı ayrı işaretçiler oluşturun (head1 ve head2).
2. Yeni bir boş liste oluşturun (mergedList).
3. Her iki listeyi de yineleyerek en küçük değeri mergedList‘e ekleyin.
4. Listelerden birine ulaşana kadar bu adımları tekrarlayın.
5. Kalan listeyi mergedList‘e ekleyin.
4. Matriste En Büyük Kare Alt Matris
Bir matris verildiğinde, en büyük kare alt matrisin boyutunu bulmanız istenen bu problem, dinamik programlama tekniklerinin kullanımı ve algoritmik düşünce yeteneğinizi göstermenizi sağlar.
Çözüm Stratejisi
1. Bir matris oluşturun (dp), aynı boyutta girdi matrisini temsil eden ve kare alt matrislerin boyutlarını depolayan matris.
2. Matrisi yineleyerek, her bir hücre için, en büyük kare alt matrisin boyutunu hesaplayın.
3. dp matrisini kullanarak en büyük kare alt matrisin boyutunu belirleyin.
5. “K” En Büyük Elemanları Bulma
Bir dizi verildiğinde, en büyük “k” elemanı bulmanız gereken bu soru, veri sıralamasını ve verimli algoritmalar oluşturma becerinizi göstermenizi sağlar.
Çözüm Stratejisi
1. **Sıralama**: Diziyi sıralayın ve en büyük “k” elemanı alın. Bu basit ancak verimli olmayan bir yaklaşım olabilir.
2. **Yığın**: Bir yığın (maxHeap) kullanın. Yığına “k” elemanı ekleyin. Sonraki elemanlar için, yığındaki en küçük elemandan daha büyükse, en küçük elemanı çıkarıp yeni elemanı ekleyin. Bu, zaman karmaşıklığı açısından daha verimlidir.
6. İki Dizinin Ara kesişimi
İki dizi verildiğinde, bu iki dizinin ara kesişimindeki ortak elemanları bulmanız gereken bu soru, veri yapıları ve algoritmaların pratik uygulamalarını anladığınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **Küme**: Bir dizinin elemanlarını bir kümeye ekleyin. Ardından, ikinci diziyi yineleyin ve her eleman kümede varsa, onu ara kesişim kümesine ekleyin.
2. **Sıralama**: Her iki diziyi sıralayın ve aynı anda her iki diziyi yineleyerek ortak elemanları bulun. Bu yaklaşım özellikle büyük diziler için daha verimli olabilir.
7. Bir Ağacın Yüksekliğini Hesaplama
Bir ikili arama ağacı verildiğinde, ağacın yüksekliğini (ağacın en uzun yolunun uzunluğu) hesaplamanız gereken bu soru, ağaç travers ve rekursif algoritmaların kullanımıyla ilgili anlayışınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **Rekürsif Yaklaşım**: Ağacın kök düğümünden başlayarak, sol ve sağ alt ağaçların yüksekliklerini rekursif olarak hesaplayın. Daha yüksek yüksekliğin 1 artırılmış değerini (kök düğümü için) döndürün.
8. İkili Arama Ağacında Bir Düğümü Arama
Bir ikili arama ağacında belirli bir düğümün var olup olmadığını bulmanız gereken bu soru, ikili arama ağaçlarının çalışma mantığını ve verimli arama algoritmaları geliştirme becerinizi göstermenizi sağlar.
Çözüm Stratejisi
1. **İteratif Yaklaşım**: Ağacın kök düğümünden başlayarak, aranacak değeri geçerli düğümle karşılaştırın. Değer daha küçükse, sol alt ağaca hareket edin; daha büyükse sağ alt ağaca hareket edin. Değer bulunana kadar bu adımları tekrarlayın.
9. Bir İkili Arama Ağacının Preorder Travers
Bir ikili arama ağacının preorder traversını gerçekleştirmeniz gereken bu soru, ağaç travers ve rekursif algoritmaların kullanımıyla ilgili anlayışınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **Rekürsif Yaklaşım**: Kök düğümü ziyaret edin, ardından sol alt ağacın preorder traversini ve ardından sağ alt ağacın preorder traversini yapın.
10. Fibonacci Sayılarını Hesaplama
Belirli bir sayı için Fibonacci dizisindeki değeri hesaplamanız gereken bu soru, rekursif algoritmalar ve dinamik programlama teknikleri ile ilgili anlayışınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **Rekürsif Yaklaşım**: Fonksiyonu kendisi için çağırarak n-inci Fibonacci sayısını hesaplayın. Bu yaklaşım, aynı alt problemleri tekrar tekrar hesapladığından, verimsiz olabilir.
2. **Dinamik Programlama**: Daha önce hesaplanan değerleri bir diziye (dp) depolayın. Bu, tekrarlanan hesaplamaları önleyerek verimliliği artırır.
11. En Uzun Ortak Alt Dizgi
İki dize verildiğinde, bu iki dizede bulunan en uzun ortak alt dizginin uzunluğunu bulmanız gereken bu soru, dinamik programlama teknikleri ve dize işleme ile ilgili anlayışınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **Dinamik Programlama**: İki dize için bir matris (dp) oluşturun ve her bir hücreye, ilgili alt diziler arasındaki en uzun ortak alt dizginin uzunluğunu depolayın. Matrisi yineleyerek, dp matrisini kullanarak en uzun ortak alt dizginin uzunluğunu belirleyin.
12. En Küçük Ortak Kat
İki tam sayı verildiğinde, bu iki sayının en küçük ortak katını (EKK) bulmanız gereken bu soru, sayı teorisi ve algoritmaların kullanımıyla ilgili anlayışınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **EBOB’u Hesaplama**: Öncelikle iki sayının en büyük ortak bölenini (EBOB) hesaplayın.
2. **EKK Hesaplama**: EBOB’u kullanarak iki sayının EKK’sini hesaplayın: EKK(a, b) = (a * b) / EBOB(a, b).
13. Merdiven Sorunu
Bir merdiven verildiğinde, n basamağı çıkmak için kaç farklı yol olduğunu bulmanız gereken bu soru, rekursif düşünce ve dinamik programlama teknikleri ile ilgili anlayışınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **Rekürsif Yaklaşım**: Fonksiyonu kendisi için çağırarak n basamağı çıkmak için kaç yol olduğunu hesaplayın. Bu yaklaşım, aynı alt problemleri tekrar tekrar hesapladığından, verimsiz olabilir.
2. **Dinamik Programlama**: Daha önce hesaplanan değerleri bir diziye (dp) depolayın. Bu, tekrarlanan hesaplamaları önleyerek verimliliği artırır.
14. Dairesel Bağlantılı Listede Döngü Bulma
Bir bağlantılı listenin dairesel olup olmadığını belirlemeniz gereken bu soru, bağlantılı listelerde döngüleri tespit etme algoritmaları ve uzamsal karmaşıklığı azaltma yeteneğinizi göstermenizi sağlar.
Çözüm Stratejisi
1. **İki İşaretçi Yöntemi**: İki işaretçi oluşturun, biri yavaş hareket eder (tek adımda) ve diğeri hızlı hareket eder (iki adımda). Eğer liste dairesel ise, hızlı işaretçi yavaş işaretçiyi yakalayacaktır.
15. Bir Ağacın Simetrisini Kontrol Etme
Bir ikili arama ağacının simetrik olup olmadığını belirlemeniz gereken bu soru, ağaç travers ve rekursif algoritmaların kullanımıyla ilgili anlayışınızı göstermenizi sağlar.
Çözüm Stratejisi
1. **Rekürsif Yaklaşım**: Sol ve sağ alt ağaçları rekursif olarak karşılaştırın. İki alt ağacın da simetrik olması durumunda, tüm ağaç simetriktir.
16. “K” En Büyük Elemanları Bulma (Sıralama Olmadan)
Bir dizi verildiğinde, en büyük “k” elemanı bulmanız gereken bu soru, önceki sorunun bir varyasyonudur ve sıralama olmadan daha verimli bir çözüm bulma becerinizi göstermenizi sağlar.
Çözüm Stratejisi
1. **Yığın (Öncelik Sırası Kuyruğu)**: En büyük “k” elemanı bir yığına (özellikle bir minimum öncelik sırası kuyruğu) ekleyin. Sonraki elemanlar için, yığındaki en küçük elemandan daha büyükse, en küçük elemanı çıkarıp yeni elemanı ekleyin. Bu yaklaşım, zaman karmaşıklığı açısından daha verimlidir.
17. İki Toplam Sayıyı Tersine Çevirme (Toplama İşlemi Olmadan)
İki sayının basamakları tersine çevrilmiş olarak verildiğinde (örneğin, 321 ve 456) bu iki sayıyı toplayıp sonucu yine tersine çevrilmiş şekilde döndürmeniz istenir, ancak toplama işlemini kullanmadan.
Çözüm Stratejisi
1. Sayıları ayrı ayrı listeler halinde temsil edin (örneğin, 321 -> [3, 2, 1]).
2. Her iki listeyi de aynı boyuta getirmek için sıfır ekleyin.
3. Her iki listenin karşılık gelen düğümlerini toplayın.
4. Toplamı bir yeni listeye ekleyin.
5. Bu listeyi tersine çevirin.
6. Listeyi bir sayıya dönüştürün.
18. “K” En Büyük Elemanları Bulma (Zaman Karmaşıklığı: O(n log k))
Bir dizi verildiğinde, en büyük “k” elemanı bulmanız gereken bu soru, önceki sorunun bir varyasyonudur ve zaman karmaşıklığı açısından daha verimli bir çözüm bulma becerinizi göstermenizi sağlar.
Çözüm Stratejisi
1. **Min Heap**: İlk “k” elemanı bir minimum yığına (minHeap) ekleyin.
2. Diziyi yineleyin. Her eleman için, minHeap‘in tepesindeki elemandan daha büyükse, minHeap‘in tepesindeki elemanı çıkarın ve yeni elemanı ekleyin.
3. Diziyi tamamladığınızda, minHeap‘in içindeki elemanlar “k” en büyük elemandır.
19. “K” En Büyük Elemanları Bulma (Zaman Karmaşıklığı: O(n))
Bir dizi verildiğinde, en büyük “k” elemanı bulmanız gereken bu soru, önceki sorunun bir varyasyonudur ve zaman karmaşıklığı açısından daha verimli bir çözüm bulma becerinizi göstermenizi sağlar.
Çözüm Stratejisi
1. **Quick Select**: Quick select algoritması kullanarak “k” en büyük elemanı bulun. Bu algoritma, pivot seçerek ve dizinin parçalarını tekrarlayan bir şekilde sıralayarak “k” en büyük elemanı bulmayı amaçlar.
2. **Quick Select (Gelişmiş)**: Quick select’in zaman karmaşıklığı ortalama olarak O(n) olsa da, en kötü durumda O(n2) olabilir. Daha gelişmiş bir Quick select algoritması kullanarak, en kötü senaryoların önüne geçebilir ve O(n) zaman karmaşıklığına ulaşabilirsiniz.
20. Matriste En Büyük Kare Alt Matris (Gelişmiş)
Bir matris verildiğinde, en büyük kare alt matrisin boyutunu bulmanız gereken bu problem, dinamik programlama tekniklerinin kullanımı ve algoritmik düşünce yeteneğinizi göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **Dinamik Programlama (Gelişmiş)**: dp matrisini oluştururken, sadece matrisin bir kısmını hesaplamak yerine, sadece son satır ve sütunları hesaplayın. Bu, matrisin tamamını depolamak yerine sadece birkaç satır ve sütunu depolamanıza izin vererek uzamsal karmaşıklığı azaltır.
21. Matriste En Büyük Kare Alt Matris (Daha Fazla Gelişmiş)
Bir matris verildiğinde, en büyük kare alt matrisin boyutunu bulmanız gereken bu problem, dinamik programlama tekniklerinin kullanımı ve algoritmik düşünce yeteneğinizi göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **Dinamik Programlama (Daha Fazla Gelişmiş)**: dp matrisini oluştururken, sadece matrisin bir kısmını hesaplamak yerine, sadece son satır ve sütunu ve ayrıca “en büyük boyut” değişkenini kullanın. Bu, matrisin tamamını depolamak yerine sadece birkaç satır ve sütunu ve bir değişkeni depolamanıza izin vererek uzamsal karmaşıklığı daha da azaltır.
22. Bağlantılı Listede Döngü Bulma (Gelişmiş)
Bir bağlantılı listenin dairesel olup olmadığını belirlemeniz gereken bu soru, bağlantılı listelerde döngüleri tespit etme algoritmaları ve uzamsal karmaşıklığı azaltma yeteneğinizi göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **Floyd’un Döngü Bulma Algoritması**: Floyd’un döngü bulma algoritmasını kullanarak, hızlı işaretçinin daha hızlı hareket etmesini ve yavaş işaretçinin daha yavaş hareket etmesini sağlayarak döngüyü bulma süresini azaltabilirsiniz.
23. İkili Arama Ağacında Bir Düğümü Arama (Gelişmiş)
Bir ikili arama ağacında belirli bir düğümün var olup olmadığını bulmanız gereken bu soru, ikili arama ağaçlarının çalışma mantığını ve verimli arama algoritmaları geliştirme becerinizi göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **İteratif Yaklaşım (Gelişmiş)**: İteratif yaklaşımı kullanırken, her adımda geçerli düğümü işaretçinin bir sonraki düğüme atandığından emin olun. Bu, ekstra bellek kullanmadan, önceki düğümü takip etme yeteneğini sağlar.
2. **Rekürsif Yaklaşım (Gelişmiş)**: Rekürsif yaklaşımı kullanırken, önceki düğümleri depolamak için bir yığın kullanabilirsiniz. Bu, herhangi bir zamanda geri dönmenize ve en son ziyaret edilen düğümlere erişmenize olanak sağlar.
24. Bir İkili Arama Ağacının Preorder Travers (Gelişmiş)
Bir ikili arama ağacının preorder traversını gerçekleştirmeniz gereken bu soru, ağaç travers ve rekursif algoritmaların kullanımıyla ilgili anlayışınızı göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **İteratif Yaklaşım**: Bir yığın kullanarak, kök düğümü yığına ekleyin. Sonra, yığının boş olmadığı sürece, yığının tepesinden düğümü çıkarın, ziyaret edin, sağ alt ağacını yığına ekleyin ve ardından sol alt ağacını yığına ekleyin.
25. Fibonacci Sayılarını Hesaplama (Gelişmiş)
Belirli bir sayı için Fibonacci dizisindeki değeri hesaplamanız gereken bu soru, rekursif algoritmalar ve dinamik programlama teknikleri ile ilgili anlayışınızı göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **İteratif Yaklaşım**: İki değişken (a ve b) kullanarak, ilk iki Fibonacci sayısını başlatın. Sonra, “n” döngüsünde, a ve b değişkenlerini sırasıyla b ve a + b olarak ayarlayın. Döngünün sonunda, a değişkeni n-inci Fibonacci sayısını temsil edecektir.
26. En Uzun Ortak Alt Dizgi (Gelişmiş)
İki dize verildiğinde, bu iki dizede bulunan en uzun ortak alt dizginin uzunluğunu bulmanız gereken bu soru, dinamik programlama teknikleri ve dize işleme ile ilgili anlayışınızı göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **Dinamik Programlama (Gelişmiş)**: İki dize için bir matris (dp) oluştururken, sadece bir satır veya sütun depolamanız yeterlidir. Bu, matrisin tamamını depolamak yerine sadece bir satır veya sütunu depolamanıza izin vererek uzamsal karmaşıklığı azaltır.
27. En Küçük Ortak Kat (Gelişmiş)
İki tam sayı verildiğinde, bu iki sayının en küçük ortak katını (EKK) bulmanız gereken bu soru, sayı teorisi ve algoritmaların kullanımıyla ilgili anlayışınızı göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **Öklid Algoritması**: Öklid algoritmasını kullanarak EBOB’u hesaplamak, EBOB’u hesaplamanın daha verimli bir yoludur.
28. Merdiven Sorunu (Gelişmiş)
Bir merdiven verildiğinde, n basamağı çıkmak için kaç farklı yol olduğunu bulmanız gereken bu soru, rekursif düşünce ve dinamik programlama teknikleri ile ilgili anlayışınızı göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **Dinamik Programlama (Gelişmiş)**: Daha önce hesaplanan değerleri bir diziye (dp) depolamak yerine, sadece iki değişken (a ve b) kullanabilirsiniz. Bu, diziyi depolamak yerine sadece iki değişkeni depolamanıza izin vererek uzamsal karmaşıklığı azaltır.
29. Dairesel Bağlantılı Listede Döngü Bulma (Daha Fazla Gelişmiş)
Bir bağlantılı listenin dairesel olup olmadığını belirlemeniz gereken bu soru, bağlantılı listelerde döngüleri tespit etme algoritmaları ve uzamsal karmaşıklığı azaltma yeteneğinizi göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **Floyd’un Döngü Bulma Algoritması (Gelişmiş)**: Floyd’un döngü bulma algoritmasını kullanarak, hızlı işaretçinin daha hızlı hareket etmesini ve yavaş işaretçinin daha yavaş hareket etmesini sağlayarak döngüyü bulma süresini daha da azaltabilirsiniz. Ayrıca, döngü içindeki düğümleri saymak için döngü uzunluğunu hesaplayabilir ve döngünün başlangıcını bulabilirsiniz.
30. Bir Ağacın Simetrisini Kontrol Etme (Gelişmiş)
Bir ikili arama ağacının simetrik olup olmadığını belirlemeniz gereken bu soru, ağaç travers ve rekursif algoritmaların kullanımıyla ilgili anlayışınızı göstermenizi sağlar. Ancak, bu sefer daha gelişmiş bir çözüm arıyoruz.
Çözüm Stratejisi
1. **İteratif Yaklaşım**: Bir yığın kullanarak, sol ve sağ alt ağaçları aynı anda yineleyin. Eğer iki alt ağaç aynı anda ziyaret edilen düğümlere sahipse, ağaç simetriktir. Aksi takdirde, ağaç simetrik değildir.
Özet
Bu makalede, yazılım mühendisliği röportajlarında sıkça sorulan bazı **Veri Yapıları ve Algoritma (DSA)** sorularını ele aldık. Bu sorular, temel DSA kavramlarını ve algoritmik düşünme yeteneğinizi değerlendirmek için tasarlanmıştır. Bu soruları çözerek ve farklı çözüm stratejilerini anlayarak, DSA ile ilgili konularda daha fazla güven kazanabilir ve yazılım mühendisliği röportajlarında başarı şansınızı artırabilirsiniz.
**İpuçları**:
- Soruları dikkatlice okuyun ve net bir şekilde anlayın.
- Çözüm stratejinizi açıklayın ve algoritmanızı adım adım izleyin.
- Kodu temiz ve okunaklı hale getirin.
- Zaman ve uzamsal karmaşıklığı hakkında düşünün.
- Farklı çözüm yaklaşımları tartışın ve kendi çözümünüzün avantajlarını ve dezavantajlarını açıklayın.
**Daha Fazla Öğrenme İçin**:
- En Çok Sorulan DSA Röportaj Soruları (İngilizce)
- Fatih Soysal’ın Blogu
- HackerRank
- LeetCode
- GeeksforGeeks
#Etiketler: DSA, Veri Yapıları, Algoritmalar, Röportaj Soruları, Yazılım Mühendisliği, Bağlantılı Liste, İkili Arama Ağacı, Yığın, Dinamik Programlama, Zaman Karmaşıklığı, Uzamsal Karmaşıklık, Algoritmik Düşünme, Kodlama, Problem Çözme, Fatih Soysal, Blog, HackerRank, LeetCode, GeeksforGeeks