Veri Yapıları mülakat soruları

Açgözlü algoritma, önceki kararları yeniden düşünmeden her adımda o an en iyi görünen seçimi yaparak çözümü adım adım kuran bir algoritmadır.

Problem açgözlü seçim özelliğine, yani yerel olarak en iyi bir seçimin en iyi genel çözümü asla dışarıda bırakmadığı bir yapıya ve optimal alt yapıya sahip olduğunda. Aralık zamanlaması, minimum kapsayan ağaçlar ve Huffman kodlaması kanıtlanmış durumlardır; diğer birçok problemde açgözlü yöntem yalnızca bir yaklaşık çözüm verir.

Açgözlü algoritma, o an en iyi görünene göre adım başına geri döndürülemez tek bir seçim yapar. Dinamik programlama ise alt problemlerin saklanmış cevaplarını kullanarak tüm seçimleri değerlendirir; bu daha çok zaman ve bellek harcar ama açgözlü seçimlerin başarısız olduğu yerde optimumu bulur.

Evet. Her adımda bilinen en küçük uzaklıklı ziyaret edilmemiş düğümü kesinleştirir; bu açgözlü bir seçimdir ve hiçbir kenar ağırlığı negatif olmadığı sürece doğru olduğu kanıtlanmıştır.

Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.

Ağaç kısıtlı bir çizgedir: bağlantılıdır, döngü içermez ve herhangi iki düğüm arasında tam olarak bir yol vardır. Çizge ise döngülere, kopuk parçalara ve herhangi bir bağlantı örüntüsüne sahip olabilir.

İkili ağaç yalnızca her düğümü en fazla iki çocukla sınırlar. İkili arama ağacı ise küçük değerlerin solda, büyük değerlerin sağda olması kuralını ekler; hızlı aramayı mümkün kılan da budur.

Dengeli ağaç, her düğümün alt ağaçlarının yüksekliğini benzer tutar; böylece tüm ağaç yaklaşık log n seviye yüksekliğinde kalır. Bu, O(log n) işlemleri garanti eder; dengesiz bir ağaç ise n seviye yüksekliğe çıkıp bir bağlı liste gibi davranabilir.

B-tree, düğümleri çok sayıda sıralı anahtar ve çocuk tutan, kendini dengeleyen arama ağacıdır; sığ kaldığından aramalar çok az disk ya da sayfa okuması ister.

İkili arama ağacı düğümü bir anahtar tutar ve en fazla iki çocuğu vardır; bu yüzden büyük bir ağaç çok sayıda seviye derinliğindedir. B-tree düğümü ise çok sayıda anahtar tutar ve çok sayıda çocuğu vardır; bu da ağacı yalnızca birkaç seviye derinlikte tutar ve depolamadan yapılan yavaş okumaları en aza indirir.

B-tree'de anahtarlar ve değerleri herhangi bir düğümde bulunabilir. B+ tree'de iç düğümler yalnızca aramaya yön verir ve tüm değerler, sıralı olarak bağlı yapraklarda yaşar; bu da aralık taramalarını hızlandırır. Çoğu veritabanı indeksi B+ tree'dir.

Kimse tam olarak bilmiyor. Yapıyı 1970 civarında icat eden Rudolf Bayer ve Edward McCreight bunu hiçbir zaman tanımlamadı; yaygın tahminler arasında balanced (dengeli), broad (geniş), Bayer ve o sırada çalıştıkları yer olan Boeing bulunuyor.

Bağlı liste, öğeleri ayrı düğümlerde saklayan bir veri yapısıdır; her düğüm bir değer ile zincirdeki sonraki düğüme bir referans tutar.

Uçlara sık sık öğe ekliyor ya da uçlardan öğe siliyorsanız, ya da referansını zaten elinizde tuttuğunuz düğümlerin yanına ekleme yapıyorsanız ve nadiren bir indekse atlamanız gerekiyorsa bağlı liste kullanın. Günlük işlerin çoğunda dizi ya da dilinizin yerleşik listesi daha basit ve daha hızlıdır.

Tek yönlü bağlı listede her düğüm yalnızca sonraki düğüme işaret eder. Çift yönlü bağlı listede her düğüm ayrıca öncekine de işaret eder; bu daha fazla bellek kullanır ama geriye doğru yürümenize ve bilinen bir düğümü O(1)'de silmenize olanak tanır.

Kendisinden önceki düğümün referansına zaten sahipseniz ya da başa ekliyorsanız yeni bir düğümü bağlamak O(1)'dir. Rastgele bir konumu bulmak önce O(n) sürer; dolayısıyla belirli bir indekse eklemek toplamda O(n)'dir.

Bloom filter, çok az bellek kullanarak bir öğenin kümede kesinlikle olmadığını ya da büyük olasılıkla olduğunu söyleyen kompakt, olasılıksal bir veri yapısıdır.

Hayır. Bir öğe eklendiyse tüm bitleri 1 olarak ayarlanmıştır; bu yüzden filtre onu her zaman olası var olarak bildirir. Yalnızca, başka öğelerin tesadüfen aynı bitlerin hepsini ayarlamış olması durumunda yanlış pozitifler mümkündür.

Kaç öğe beklediğinize ve hangi yanlış pozitif oranını kabul edebileceğinize bağlıdır. Genel bir kural olarak öğe başına yaklaşık 10 bit ve 7 hash fonksiyonu yüzde 1'in hemen altında bir oran verir ve öğe başına eklenen her 5 bit bu oranı yaklaşık on kat düşürür.

Hash set her öğeyi saklar ve üyeliği kesin olarak yanıtlar, ancak tüm öğeler için bellek ister. Bloom filter yalnızca bit sakladığı için çok daha küçüktür, ancak yanlış pozitif döndürebilir ve temel biçimiyle öğeleri listeleyemez ya da silemez.

Böl ve yönet, bir problemi daha küçük bağımsız parçalara bölen, her birini özyinelemeyle çözen ve sonuçları birleştiren bir algoritma tasarım tekniğidir.

İkisi de bir problemi alt problemlere böler, ancak böl ve yönet alt problemler bağımsız olduğunda çalışır ve her biri bir kez çözülür. Dinamik programlama çakışan alt problemler içindir ve yeniden hesaplanmasınlar diye cevaplarını saklar.

Evet, basit bir biçimde: arama aralığını ikiye böler ve birleştirme adımı olmadan yalnızca bir yarıda devam eder. Bazı ders kitapları bu özel duruma decrease and conquer der.

Klasik olanlar merge sort ve quicksort'tur. Merge sort asıl işini birleştirirken, sıralı yarıları birleştirerek yapar; quicksort ise bölerken, öğeleri bir pivot etrafında bölümleyerek yapar.

Bubble sort (kabarcık sıralaması), sırası bozuk komşu öğeleri yer değiştiren basit bir sıralama algoritmasıdır; her geçiş kalan en büyük değeri sona taşır.

Çünkü öğeleri bir seferde yalnızca bir konum taşır ve n öğe üzerinde yaklaşık n geçişe ihtiyaç duyabilir; bu da O(n²) karşılaştırma demektir. Girdiyi iki katına çıkarmak işi kabaca dört katına çıkarır.

Evet. Komşuları yalnızca soldaki kesinlikle daha büyük olduğunda yer değiştirir; bu yüzden eşit öğeler asla birbirinin önüne geçmez ve ilk sıralarını korur.

İkisi de en kötü durumda O(n²)'dir. Bubble sort her geçişte bütün liste boyunca komşuları yer değiştirir; insertion sort ise sıralı bir ön kısım kurar ve her yeni öğeyi yerine yerleştirir; bu da genellikle çok daha az işlem yapar.

Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan ve yollar, arkadaşlıklar ve bağımlılıklar gibi ilişkileri modellemekte kullanılan bir veri yapısıdır.

Ağaç, ek kuralları olan bir çizgedir: bağlantılıdır, döngü içermez ve genellikle tek bir kökü vardır. Çizge ise döngülere, birkaç kopuk parçaya ve herhangi bir bağlantı örüntüsüne sahip olabilir.

DAG, döngüsü olmayan yönlü bir çizgedir; yani kenarları izlemek sizi asla başladığınız yere geri götüremez. DAG'lar derleme adımları, veri pipeline'ları ve Git'teki commit geçmişi gibi bağımlılıkları modeller.

Başlangıçtan uzaklık sırasına göre düğümleri keşfettiği için kenar sayısına göre en kısa yola ihtiyaç duyduğunuzda genişlik öncelikli aramayı kullanın. Tüm yolları keşfetmek, döngüleri bulmak ya da bağımlılıkları sıralamak için derinlik öncelikli aramayı kullanın; ikisi de O(V + E) sürede çalışır.