DSA Interview Prep · Ders

Veri Akışından Medyan ve K-Yollu Birleştirme

Q: “Veri Akışından Medyan ve K-Yollu Birleştirme” dersi ücretsiz mi?

Evet — “Veri Akışından Medyan ve K-Yollu Birleştirme” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Q: DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.

Q: “Veri Akışından Medyan ve K-Yollu Birleştirme” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Medyanı O(log n) sürede güncellemek için iki yığın (küçük yarının maksimum yığını ve büyük yarının minimum yığını) tutun; k sıralı listeyi bir yığın kullanarak birleştirin.

Veri Akışından Medyan ve K-Yollu Birleştirme, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Veri Akışından Medyan Problemi

Veri Akışından Medyanı Bulma (LeetCode #295), iki işlemi verimli biçimde desteklemenizi ister: sayı eklemek için addNum(num) ve mevcut medyanı döndürmek için findMedian(). Çift uzunluktaki bir listenin medyanı, ortadaki iki değerin ortalamasıdır. Kaba kuvvetle kullanılan sıralı bir listede ekleme O(n), medyanı alma ise O(1) sürer. En iyi çözüm, O(log n) ekleme ve O(1) medyan için iki yığın kullanır.

import heapq

# Strategy: maintain two halves of the data
# max_heap: lower half (stores negated values for max behavior)
# min_heap: upper half
# Invariant: len(max_heap) == len(min_heap) or len(max_heap) == len(min_heap) + 1
# Invariant: max(max_heap) <= min(min_heap)
# Median:
#   odd count:  max_heap[0] (top of lower half)
#   even count: average of tops of both halves
print('Two-heap strategy for O(log n) insert, O(1) median')

İki Yığınlı MedianFinder Uygulaması

Alt yarı için bir maks-yığın ve üst yarı için bir min-yığın tutun. Maks-yığının, min-yığınla aynı sayıda veya ondan bir fazla öğeye sahip olmasını her zaman sağlayın. Bir sayı eklerken onu maks-yığına push edin; ardından, maks-yığının tepesi min-yığının minimumunu aşarsa tepe öğeyi min-yığına taşıyarak dengeleyin ve gerekirse boyutları yeniden dengeleyin.

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negated) for lower half
        self.hi = []  # min-heap for upper half

    def addNum(self, num):
        heapq.heappush(self.lo, -num)   # push to lower half
        # Ensure max of lower <= min of upper
        if self.hi and -self.lo[0] > self.hi[0]:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # Balance sizes: lo can have at most 1 more than hi
        if len(self.lo) > len(self.hi) + 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]  # odd count: top of lower half
        return (-self.lo[0] + self.hi[0]) / 2

mf = MedianFinder()
for n in [1, 2, 3, 4, 5]: mf.addNum(n)
print(mf.findMedian())  # 3.0

MedianFinder Adımlarını İzleme

İki yığın değişmezinin neden korunduğunu anlamak, çözümü bir mülakatta açıklamak için kritik öneme sahiptir. [5, 15, 1, 3] ekleme işlemini adım adım izleyelim. Her eklemeden sonra, alt yarıyı daha küçük öğeleri tutan maks-yığının içereceği şekilde dengeleyin. Değişmez, max(lo) <= min(hi) koşulunun her zaman geçerli olmasını sağlar; bu da medyana bir veya iki yığının tepesinden doğrudan erişilebilmesini mümkün kılar.

import heapq

# Manual trace for [5, 15, 1, 3]:
# add 5:   lo=[-5]        hi=[]       median=5
# add 15:  lo=[-5]        hi=[15]     median=(5+15)/2=10
# add 1:   lo=[-5,-1]     hi=[15]     median=5
# add 3:   lo=[-5,-3,-1]  hi=[15]     -- lo too big
#       -> lo=[-5,-3]      hi=[1,15]  -- wait, wrong direction
# Actually:
# add 1:   push to lo -> lo=[-5,-1], then 1>lo? No, -lo[0]=5>15? No
#          lo has 2, hi has 1: balance -> move lo top to hi
#          lo=[-1], hi=[5,15]
# Median = (-lo[0] + hi[0])/2 = (1+5)/2 = 3
mf2 = MedianFinder()
for n, expected in [(5, 5.0), (15, 10.0), (1, 5.0), (3, 4.0)]:
    mf2.addNum(n)
    print(f'After adding {n}: median={mf2.findMedian()} (expected ~{expected})')

Kayan Pencere Medyanı

Kayan Pencere Medyanı (LeetCode #480) daha zor bir çeşittir: dizi boyunca kayan k boyutundaki her pencerenin medyanını bulmanız gerekir. İki yığın yaklaşımı, pencereden kayan öğeleri yönetmek için bir tembel silme kümesiyle genişletilir. Bir öğe pencereden çıktığında onu silme kümesinde işaretleyin; öğe yığınlardan birinin tepesine ulaştığında onu atın.

import heapq

def median_sliding_window(nums, k):
    lo = []  # max-heap (negated)
    hi = []  # min-heap
    removed = {}
    result = []

    def balance():
        # Move valid tops to correct side
        while lo and removed.get(-lo[0], 0) > 0:
            removed[-lo[0]] -= 1; heapq.heappop(lo)
        while hi and removed.get(hi[0], 0) > 0:
            removed[hi[0]] -= 1; heapq.heappop(hi)

    for i, num in enumerate(nums):
        heapq.heappush(lo, -num)
        heapq.heappush(hi, -heapq.heappop(lo))
        if len(hi) > len(lo): heapq.heappush(lo, -heapq.heappop(hi))
        if i >= k:
            out = nums[i - k]
            removed[out] = removed.get(out, 0) + 1
        balance()
        if len(lo) > len(hi): heapq.heappush(hi, -heapq.heappop(lo))
        if i >= k - 1:
            if len(lo) > len(hi): result.append(float(-lo[0]))
            else: result.append((-lo[0] + hi[0]) / 2.0)
    return result

print(median_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [1,-1,-1,3,5,6]

K-Yollu Birleştirme: Problem

K Sıralı Listeyi Birleştirme (LeetCode #23), harici sıralama, veritabanı birleştirmeleri ve dağıtık sistemlerde uygulamaları bulunan temel bir problemdir. Toplam n düğüm içeren k sıralı bağlı liste verildiğinde, bunları tek bir sıralı listede birleştirin. Naif yaklaşım (bir seferde iki listeyi birleştirmek) O(kn) sürer; böl ve yönet yaklaşımıyla bu süre O(n log k) olur. Yığın yaklaşımı her düğümü tam bir kez işler ve düğüm başına O(log k) iş yapar; toplam süre O(n log k)'dir.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Build a linked list from a Python list
def build_list(arr):
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

# Convert linked list to Python list for printing
def to_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

print('K-way merge: O(n log k) using a min-heap of k heads')

Min-Yığın ile K-Yollu Birleştirme

Yığını her listenin ilk düğümüyle başlatın. Her adımda minimumu pop edin, sonuca ekleyin ve varsa o listeden sonraki düğümü push edin. Yığında her zaman en fazla k öğe bulunur; etkin her liste için bir baş düğüm vardır. Toplam n düğümü, her biri için O(log k) yığın işlemiyle işlediğimizden toplam süre O(n log k), yığın için alan kullanımı ise O(k)'dir.

import heapq

def merge_k_lists(lists):
    dummy = ListNode(0)
    curr = dummy
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

lists = [
    build_list([1, 4, 5]),
    build_list([1, 3, 4]),
    build_list([2, 6])
]
result = merge_k_lists(lists)
print(to_list(result))  # [1, 1, 2, 3, 4, 4, 5, 6]

K Listeyi Kapsayan En Küçük Aralık

En Küçük Aralık (LeetCode #632), k sıralı listenin her birinden en az bir öğenin [lo, hi] aralığında bulunduğu en küçük aralığı bulur. Her listenin ilk öğesiyle başlatılmış bir min-yığın kullanın ve mevcut maksimumu takip edin. Mevcut minimumu içeren listenin ilerlemesini sağlayarak aralığı sürekli daraltın. Listelerden biri tükendiğinde durun.

import heapq

def smallest_range(nums):
    heap = []
    current_max = float('-inf')
    for i, lst in enumerate(nums):
        heapq.heappush(heap, (lst[0], i, 0))
        current_max = max(current_max, lst[0])
    best = [float('-inf'), float('inf')]
    while heap:
        current_min, list_idx, elem_idx = heapq.heappop(heap)
        if current_max - current_min < best[1] - best[0]:
            best = [current_min, current_max]
        if elem_idx + 1 >= len(nums[list_idx]):
            break  # one list exhausted
        next_val = nums[list_idx][elem_idx + 1]
        heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
        current_max = max(current_max, next_val)
    return best

print(smallest_range([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]))
# [20, 24]

Matristeki K'inci En Küçük Öğeyi Bulma

Sıralı Matristeki K'inci En Küçük Öğe (LeetCode #378): Her satırı ve sütunu sıralı olan n×n boyutunda bir matris verilir. K'inci en küçük öğeyi bulun. Her satırı sıralı bir liste olarak ele alın ve yığınla k-yollu birleştirme kullanın. Alternatif olarak değer aralığı üzerinde ikili arama yapabilirsiniz. Yığın yaklaşımı O(k log n) sürer ve k küçük olduğunda verimlidir; ikili arama ise O(n log(max-min)) sürer ve büyük k değerlerini daha iyi yönetir.

import heapq

def kth_smallest_matrix(matrix, k):
    n = len(matrix)
    heap = [(matrix[0][0], 0, 0)]
    count = 0
    visited = {(0, 0)}
    while heap:
        val, r, c = heapq.heappop(heap)
        count += 1
        if count == k:
            return val
        # Push right neighbor
        if c + 1 < n and (r, c+1) not in visited:
            heapq.heappush(heap, (matrix[r][c+1], r, c+1))
            visited.add((r, c+1))
        # Push bottom neighbor
        if r + 1 < n and (r+1, c) not in visited:
            heapq.heappush(heap, (matrix[r+1][c], r+1, c))
            visited.add((r+1, c))
    return -1

matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kth_smallest_matrix(matrix, 8))  # 13

Sürekli İstatistikler için İki Yığın

İki yığın örüntüsü medyanın ötesine genellenebilir. Bunu sürekli quantile değerini (örneğin 25. yüzdelik dilimi) tutmak için kullanabilirsiniz: alt yığının boyutunu p*n öğe, üst yığının boyutunu ise (1-p)*n öğe tutacak şekilde ayarlayın. Her öğe eklendiğinde daha önce olduğu gibi yeniden dengeleyin. Bu örüntü, verimli ekleme ve quantile sorgularını aynı anda gerektiren akış istatistikleri problemlerinde görülür.

import heapq

# Generalised two-heap for arbitrary quantile p
# lo contains floor(p * count) elements
# hi contains the remaining elements
class QuantileFinder:
    def __init__(self, p):
        self.p = p  # quantile (e.g., 0.5 for median)
        self.lo = []  # max-heap
        self.hi = []  # min-heap
        self.count = 0

    def add(self, num):
        self.count += 1
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # Target: lo should have floor(p * count) elements
        target_lo = int(self.p * self.count)
        while len(self.lo) < target_lo:
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
        while len(self.lo) > target_lo:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))

    def quantile(self):
        return -self.lo[0] if self.lo else self.hi[0]

qf = QuantileFinder(0.5)  # median
for n in [1, 2, 3, 4, 5, 6]: qf.add(n)
print(qf.quantile())  # 3 (median of 1-6)

Başlangıca En Yakın K Noktayı Bulma

Başlangıca En Yakın K Nokta (LeetCode #973), k boyutunda bir maks-yığın kullanır. Karekök hesaplamaktan kaçınmak için her noktanın karesel uzaklığını push edin. Yığın k boyutunu aşarsa en uzaktaki noktayı pop edin. Geriye kalan k nokta, başlangıca en yakın k noktadır. Bu yaklaşım O(n log k) sürer. Alternatif olarak ortalama O(n) sürede hızlı seçim algoritmasını kullanabilirsiniz; ancak yığın çözümünü doğru biçimde uygulamak ve bir mülakatta açıklamak daha basittir.

import heapq

def k_closest(points, k):
    heap = []  # max-heap via negation
    for x, y in points:
        dist_sq = x*x + y*y
        heapq.heappush(heap, (-dist_sq, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

points = [[1,3], [-2,2], [5,8], [0,1], [-1,-1]]
print(k_closest(points, 2))
# Two closest to origin: [0,1] (dist=1) and [-1,-1] (dist=2)

# Verify by distances:
for x, y in points:
    print(f'({x},{y}): dist^2 = {x*x+y*y}')

İki Yığın: Zaman ve Alan Analizi

Medyan için iki yığın yaklaşımı, her addNum işlemini O(log n) sürede, findMedian işlemini ise O(1) sürede gerçekleştirir. Tüm öğeleri saklamak için gereken alan O(n)'dir. K-yollu birleştirme O(n log k) zaman ve yığın için O(k) alan kullanır. Bu karmaşıklıklar neredeyse en iyisidir: k-yollu birleştirme için karşılaştırmaya dayalı Omega(n log k) alt sınırı kanıtlanabilir; bu da yığın çözümünün asimptotik olarak optimal olduğunu gösterir. Mülakatlarda bu karmaşıklıkları her zaman açıkça belirtin.

# Complexity summary for heap applications:
# Problem               | Time per op  | Space
# ----------------------|--------------|------
# MedianFinder.addNum   | O(log n)     | O(n)
# MedianFinder.find     | O(1)         | -
# Merge k sorted lists  | O(n log k)   | O(k)
# Kth smallest matrix   | O(k log n)   | O(n)
# K closest points      | O(n log k)   | O(k)
# Task scheduler        | O(n log 26)  | O(26)
# Kth largest stream    | O(log k)     | O(k)
# Sliding window median | O(n log k)   | O(k)

print('Heap problems: identify k (heap size) vs n (input size)')

Hızlı Kontrol

Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı sınayın.

Ders Özeti

Bu derste O(log n) ekleme ve O(1) medyan süresi sağlayan iki yığınlı MedianFinder yapısını, O(n log k) zamanda ve O(k) alanda min-yığınla k-yollu birleştirmeyi ve kayan pencere medyanı, en küçük aralık ve başlangıca en yakın k nokta gibi uzantıları öğrendiniz. Sırada graf gösterimlerini ve dolaşma hazırlığını inceleyeceğiz.

Sıkça Sorulan Sorular