Mülakat kalıpları: bağlı liste, ağaç, trie, graf, aralık ve 2B DP

Neden ikinci bir kalıp dersi?

algoritmalar ve Mülakat hazırlığı: Python soruları, algoritmalar, canlı kodlama derslerinde dizi, sözlük, iki işaretçi, kayan pencere, ikili arama, BFS ve tek boyutlu dinamik programlama kalıplarını gördün. Teknik mülakatların ikinci yarısı genellikle işaretçi tabanlı yapılar (bağlı liste, ağaç, trie), ileri graf (ağırlıklı en kısa yol, bağımlılık sırası, bağlı bileşenler), aralıklar ve iki boyutlu DP üzerinedir. Bu kalıplar iş hayatında da karşına çıkar: Kanat Havayolları'nda en kısa aktarma rotası, Pusula İK'da organizasyon ağacı, Lezzet Kurye'de aynı anda yoldaki kurye sayısı, arama kutusunda otomatik tamamlama.

Bu derste her kalıbın tanıma ipucunu, Python iskeletini ve karmaşıklığını öğreneceksin; örneklerin çoğu gerçek veri setleri üzerinde çalışır.

1. Bağlı liste problemleri

Veri yapıları: yığın, kuyruk, öncelik kuyruğu, bağlı liste, hash, ağaç ve graf dersinde düğümlerden bağlı liste kurdun. Mülakat soruları genelde üç işaretçi hilesine dayanır: ters çevirme (önceki/şimdiki/sonraki), hızlı-yavaş işaretçi (Floyd: döngü tespiti, ortadaki eleman) ve sahte baş düğüm (dummy head: birleştirme, silme).

class Dugum:
    def __init__(self, deger, sonraki=None):
        self.deger = deger
        self.sonraki = sonraki

def listeden(degerler):
    bas = None
    for d in reversed(degerler):
        bas = Dugum(d, bas)
    return bas

def listeye(bas, sinir=100):
    sonuc = []
    while bas and len(sonuc) < sinir:
        sonuc.append(bas.deger)
        bas = bas.sonraki
    return sonuc


def ters_cevir(bas):
    onceki = None
    while bas:
        bas.sonraki, onceki, bas = onceki, bas, bas.sonraki
    return onceki

def dongu_var_mi(bas):
    yavas = hizli = bas
    while hizli and hizli.sonraki:
        yavas, hizli = yavas.sonraki, hizli.sonraki.sonraki
        if yavas is hizli:
            return True
    return False

rota = listeden(["Depo", "Konak", "Alsancak", "Bornova"])
print(listeye(ters_cevir(rota)))
dongulu = listeden([1, 2, 3, 4])
dongulu.sonraki.sonraki.sonraki.sonraki = dongulu.sonraki   # 4 → 2
print(dongu_var_mi(dongulu), dongu_var_mi(listeden([1, 2, 3])))

2. Ağaçlar: gezinme, derinlik, BST, LCA

Ağaç sorularının çoğu tek bir özyinelemeli fikre indirgenir: "sol alt ağaç için cevabı bil, sağ alt ağaç için cevabı bil, ikisini birleştir". Derinlik öncelikli (DFS) gezinmenin üç sırası vardır: pre-order (kök, sol, sağ: ağacı kopyalamak), in-order (sol, kök, sağ: BST'de sıralı çıktı), post-order (sol, sağ, kök: alt ağaç boyutu, silme). Genişlik öncelikli (BFS) gezinme ise kuyrukla seviye seviye ilerler.

class Agac:
    def __init__(self, deger, sol=None, sag=None):
        self.deger = deger
        self.sol = sol
        self.sag = sag

from collections import deque

kok = Agac(8, Agac(3, Agac(1), Agac(6)), Agac(10, None, Agac(14)))

def inorder(d):
    return inorder(d.sol) + [d.deger] + inorder(d.sag) if d else []

def derinlik(d):
    return 1 + max(derinlik(d.sol), derinlik(d.sag)) if d else 0

def seviyeler(kok):
    sonuc, q = [], deque([kok] if kok else [])
    while q:
        sonuc.append([d.deger for d in q])
        q = deque(c for d in q for c in (d.sol, d.sag) if c)
    return sonuc

print("in-order:", inorder(kok), "derinlik:", derinlik(kok))
print("seviyeler:", seviyeler(kok))

BST doğrulamada sık yapılan hata yalnız çocuklarla karşılaştırmaktır; doğru yöntem her düğüme izin verilen (alt, üst) aralığını aşağı taşımaktır. En yakın ortak ata (Lowest Common Ancestor, LCA) ise organizasyon ağacında "iki çalışanın ortak yöneticisi" sorusudur: ebeveyn işaretçisi varsa birinin atalarını kümeye koyup diğerinden yukarı çıkarsın.

3. Trie: önek ağacı ve otomatik tamamlama

Trie, her kenarı bir karakter olan bir ağaçtır; aynı öneki paylaşan kelimeler aynı yolu paylaşır. "Bu önekle başlayan kelime var mı?" sorusu kelime sayısından bağımsız, yalnız önek uzunluğu kadar (O(L)) sürer. Anadolu Market arama kutusundaki ürün önerisi tipik kullanımdır:

import veri

class Trie:
    def __init__(self):
        self.kok = {}

    def ekle(self, kelime):
        dugum = self.kok
        for harf in kelime:
            dugum = dugum.setdefault(harf, {})
        dugum["$"] = True                       # kelime sonu işareti

    def tamamla(self, onek, k=5):
        dugum = self.kok
        for harf in onek:
            if harf not in dugum:
                return []
            dugum = dugum[harf]
        sonuc, yigin = [], [(dugum, onek)]
        while yigin and len(sonuc) < k:
            d, yol = yigin.pop()
            if "$" in d:
                sonuc.append(yol)
            for harf in sorted((h for h in d if h != "$"), reverse=True):
                yigin.append((d[harf], yol + harf))
        return sonuc

t = Trie()
for urun in veri.kayitlar("anadolu_market", "products"):
    t.ekle(urun["name"].replace("İ", "i").replace("I", "ı").lower())
print(t.tamamla("k", 4))
print(t.tamamla("su"), t.tamamla("xyz"))

4. İleri graf: Dijkstra, topolojik sıralama, union-find

Dijkstra, kenar ağırlıkları negatif olmayan grafta tek kaynaktan en kısa yolları bulur: bir öncelik kuyruğundan (heapq) her seferinde en yakın düğümü çıkar, komşuların mesafesini gevşet (relax). Kuyruktan eski (stale) bir kayıt çıkarsa atla. Karmaşıklık O((V + E) log V). Kanat Havayolları'nın gerçek rota tablosunda Berlin'den Ankara'ya en kısa yol:

import heapq
from collections import defaultdict

graf = defaultdict(list)
for r in veri.kayitlar("kanat_havayollari", "hv_routes"):
    graf[r["origin"]].append((r["dest"], r["distance_km"]))

def dijkstra(bas, hedef):
    mesafe, onceki = {bas: 0}, {}
    kuyruk = [(0, bas)]
    while kuyruk:
        d, u = heapq.heappop(kuyruk)
        if u == hedef:
            yol = [u]
            while yol[-1] != bas:
                yol.append(onceki[yol[-1]])
            return d, yol[::-1]
        if d > mesafe[u]:
            continue                            # eski kayıt
        for v, w in graf[u]:
            if d + w < mesafe.get(v, float("inf")):
                mesafe[v], onceki[v] = d + w, u
                heapq.heappush(kuyruk, (d + w, v))
    return None

print(dijkstra("BER", "ESB"))
print(dijkstra("FRA", "BER"))

BER→ESB için en az aktarmalı yollar iki tane (SAW-ADB ve SAW-AYT üzerinden, ikisi de 3 uçuş); BFS hangisini önce bulursa onu verir, Dijkstra ise kilometreye bakarak AYT üzerinden olanı (2618 km) seçer. Negatif ağırlık varsa Dijkstra yanlış sonuç verir; Bellman-Ford gerekir.

Topolojik sıralama, yönlü döngüsüz grafta (DAG) her kenarın (a → b) a'yı b'den önce koyan sıralamadır: derleme sırası, veri hattı görevleri, ön koşullu dersler, departman hiyerarşisi. Kahn algoritması giriş derecesi 0 olanlardan başlar; tüm düğümler çıkarılamıyorsa döngü vardır. Union-find (ayrık küme, disjoint set) ise "bu iki öğe aynı grupta mı?" sorusunu neredeyse O(1)'de cevaplar; yol sıkıştırma (path compression) ve boyuta göre birleştirme ile.

departman = veri.kayitlar("pusula_ik", "ik_departments")
ad = {d["dept_id"]: d["name"] for d in departman}
giris = {d["name"]: 0 for d in departman}
cocuk = defaultdict(list)
for d in departman:
    if d["parent_id"] is not None:
        cocuk[ad[d["parent_id"]]].append(d["name"])
        giris[d["name"]] += 1
hazir = sorted(n for n, g in giris.items() if g == 0)
sira = []
while hazir:
    u = hazir.pop(0)
    sira.append(u)
    for v in cocuk[u]:
        giris[v] -= 1
        if giris[v] == 0:
            hazir.append(v)
print(sira[:6], "...", len(sira) == len(giris))

ebeveyn = {}
def bul(x):
    ebeveyn.setdefault(x, x)
    while ebeveyn[x] != x:
        ebeveyn[x] = ebeveyn[ebeveyn[x]]        # yol sıkıştırma (yarılama)
        x = ebeveyn[x]
    return x
for a, b in [("ali", "ayse"), ("veli", "can"), ("ayse", "can")]:
    ebeveyn[bul(a)] = bul(b)
print(bul("ali") == bul("veli"), bul("ali") == bul("zeynep"))

5. Aralıklar ve sweep line

Aralık problemlerinin anahtarı başlangıca göre sıralamaktır. Birleştirme (merge), ekleme (insert) ve çakışma kontrolü bu sıralamadan sonra tek geçişle çözülür. "Aynı anda en çok kaç ...?" sorusu ise sweep line (süpürme çizgisi) ile çözülür: her aralığı (+1 başlangıç, −1 bitiş) olaylarına çevir, zamana göre sırala, sayacı gez. Aynı anda biten ve başlayan olayda bitişi önce işlemek, yarı açık [başlangıç, bitiş) aralığı anlamına gelir.

olaylar = []
for s in veri.kayitlar("lezzet_kurye", "lk_orders"):
    if s["picked_at"] and s["delivered_at"]:
        olaylar += [(s["picked_at"], 1), (s["delivered_at"], -1)]
olaylar.sort()                                  # aynı saniyede -1, +1'den önce gelir
yolda = en_cok = 0
for zaman, degisim in olaylar:
    yolda += degisim
    if yolda > en_cok:
        en_cok, an = yolda, zaman
print(f"{len(olaylar) // 2} teslimat; aynı anda en çok {en_cok} kurye yolda ({an})")

6. İki boyutlu dinamik programlama

İki dizi ya da bir ızgara üzerinde "en uzun / en az / kaç yol" soruları genelde 2B DP'dir: dp[i][j] = ilk dizinin ilk i, ikincinin ilk j elemanı için cevap. Algoritmalar ve Big-O: arama, sıralama, iki işaretçi, dinamik programlama, BFS/DFS dersinde LCS'yi gördün. Düzenleme mesafesi (edit distance, Levenshtein) bir metni diğerine çeviren en az ekleme/silme/değiştirme sayısıdır; adres ve şehir adlarındaki yazım hatalarını eşleştirmede kullanılır. Her satır yalnız bir önceki satıra baktığı için tabloyu iki satıra indirip belleği O(n·m)'den O(m)'ye düşürebilirsin.

def duzenleme(a, b):
    onceki = list(range(len(b) + 1))           # boş a → b'nin ilk j harfi: j ekleme
    for i in range(1, len(a) + 1):
        simdiki = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                simdiki[j] = onceki[j - 1]
            else:
                simdiki[j] = 1 + min(onceki[j], simdiki[j - 1], onceki[j - 1])
        onceki = simdiki
    return onceki[-1]

for yazilan in ["Eskisehir", "Kayseeri", "Ankra", "İzmir"]:
    print(yazilan, "→", min(["Eskişehir", "Kayseri", "Ankara", "İzmir"], key=lambda s: duzenleme(yazilan, s)))

7. Bit manipülasyonu

8. Kalıp tanıma tablosu