Ders Programı I ve II
Ders ön koşullarını yönlü bir graf olarak modelleyin ve tüm derslerin tamamlanıp tamamlanamayacağını ve hangi sırayla alınacağını belirlemek için topolojik sıralama kullanın.
Ders Programı I ve II, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. 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.
Problem Genel Bakışı
Ders Programı I (LeetCode 207): n ders ve prerequisites çiftlerinden oluşan bir liste verildiğinde, [a, b] çifti "b, a'dan önce alınmalıdır" anlamına gelir; tüm dersleri tamamlayıp tamamlayamayacağınızı belirleyin. Ders Programı II (LeetCode 210): dersleri alma sırasını döndürün veya bu mümkün değilse boş bir dizi döndürün. Her iki problem de ön koşulların kenar olduğu yönlü bir grafikte topolojik sıralamaya indirgenir.
Grafik Modelleme
Yönlü bir grafik oluşturun: her ön koşul çifti [a, b] için b → a kenarını ekleyin ("b, a'dan önce gelmelidir" demek, b'nin a'ya yönelmesi anlamına gelir). Her ders için giriş derecelerini hesaplayın. Giriş derecesi 0 olan bir dersin ön koşulu yoktur ve hemen alınabilir. Bu problem, ancak ve ancak bu grafikte hiç döngü yoksa çözülebilir (dairesel bağımlılık bulunmamalıdır).
from collections import defaultdict
def build_graph(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for a, b in prerequisites: # b must come before a
graph[b].append(a)
in_degree[a] += 1
return graph, in_degree
graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind) # [0, 1, 1, 2]
print('Graph edges:', dict(graph))Ders Programı I: Kahn Algoritmasıyla Çözüm
Kahn algoritmasını kullanın. İşlenen derslerin sayısı n'ye eşitse tüm dersler tamamlanabilir. Aksi hâlde dairesel bir bağımlılık tamamlanmayı engeller.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
course = queue.popleft()
count += 1
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # FalseDers Programı II: Sırayı Döndürme
Ders Programı I ile aynıdır, ancak dersleri işlerken sıralarını da toplayın. Tüm dersler sıralamaya dâhil edilmişse bu sırayı, aksi hâlde boş bir liste döndürün.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))DFS ile Ders Programı
Bir başka seçenek, döngü algılama için DFS kullanmaktır. Derslerin üç durumu vardır: ziyaret edilmemiş (0), işleniyor (1), tamamlandı (2). DFS sırasında işlenmekte olan bir derse ulaşırsak bir döngü vardır. Bu yaklaşım işlevsel olarak Kahn algoritmasına denktir, ancak özyinelemeli DFS kullanır.
from collections import defaultdict
def canFinish_dfs(numCourses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
# 0=unvisited, 1=in-progress, 2=done
state = [0] * numCourses
def has_cycle(course):
if state[course] == 1: return True # back edge
if state[course] == 2: return False # already cleared
state[course] = 1
for nxt in graph[course]:
if has_cycle(nxt):
return True
state[course] = 2
return False
return not any(has_cycle(i) for i in range(numCourses))
print(canFinish_dfs(2, [[1,0]])) # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # FalseKenarların Yönü Neden Önemlidir
Yaygın bir hata, kenarların yönünü ters çevirmektir: ön koşul [a, b] "b, a'dan önce gelir" anlamına geliyorsa b → a kenarını ekleyin, a → b kenarını değil. Kenarın yönü bağımlılık akışını yansıtmalıdır: ok, önce yapılması gereken şeyden ona bağlı olana doğru yönelir. Yanlış yönde, döngü algılama ve sıralama tersine döner; bu da birden fazla bağımlılığın bulunduğu problemlerde hatalı sonuçlar verir.
Ders Programı III: Açgözlü Varyant
Ders Programı III (LeetCode 630) farklı bir problemdir: derslerin süreleri ve son tarihleri vardır ve alınan derslerin sayısını en üst düzeye çıkarmak istersiniz. Bu problem, maksimum yığınla açgözlü bir şekilde çözülür: her zaman son tarihi en geç olan dersi önce alın; bir ders eklemek onun son tarihini aşarsa, şimdiye kadar alınan en uzun dersi onunla değiştirin (eğer o ders daha uzunsa). Bu, topolojik sıralama değil, açgözlü bir problemidir; bu da problem ifadelerini dikkatle okumanın önemini gösterir.
Yalıtılmış Düğümleri Ele Alma
Ön koşulu ve kendisine bağlı dersi olmayan dersler yalıtılmış düğümlerdir; giriş dereceleri 0'dır ve dışarı çıkan kenarları yoktur. Kahn algoritması bunları doğru şekilde ele alır: hemen kuyruğa eklenir ve işlenirler. Ön koşul listesinde görünmeyenler de dâhil olmak üzere 0'dan n-1'e kadar TÜM düğümlerin giriş derecelerini 0 olarak başlattığınızdan emin olun; aksi hâlde bu düğümler gözden kaçar.
# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict
def findOrder_isolated(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses # initialise ALL nodes
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder_isolated(4, [[1,0]])) # [0,1,2,3] or [2,3,0,1] etc.Paralel Dersleri Tamamlama Süresi
Paralel Dersler II: Ön koşullara uyulması ve dönem başına en fazla k derse izin verilmesi durumunda tüm dersleri almak için gereken en az dönem sayısını bulun. Bu problem, k seçme kısıtı için bit maskesi DP'siyle düzey düzey Kahn işlemesini gerektirir; topolojik sıralamayı bit maskesi DP'siyle birleştiren, oldukça daha zor bir problemdir.
Mülakatta İletişim Stratejisi
Bir mülakatta Ders Programı türü bir problemle karşılaştığınızda: (1) Problemi hemen bir topolojik sıralama / döngü algılama problemi olarak belirleyin. (2) Kenarların hangi yöne işaret ettiğini açıklığa kavuşturarak grafiği modelleyin. (3) Basitlik için Kahn algoritmasını (BFS), aşinalık için DFS'yi seçin. (4) Döngü durumunu açıkça ele alın. (5) O(V+E) zaman karmaşıklığından bahsedin. Bu yapılandırılmış yaklaşım, sistematik problem çözme becerilerinizi gösterir.
Kapsamlı Sınama
Doğruluğu doğrulamak için her iki çözümü de çeşitli girdilerle sınayın. Kahn yaklaşımı, birden fazla geçerli sıralamayı sorunsuz şekilde ele alır; Ders Programı II için yanıt olarak herhangi bir geçerli topolojik sıralama kabul edilir.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(1, [])) # [0]
print(findOrder(2, [[0,1]])) # [1, 0]
print(findOrder(3, [[1,0],[2,1]])) # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]])) # [] cycleHızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: Ders Programı I ve II, ön koşul [a, b] için b → a kenarıyla topolojik sıralamayı kullanır, Ders Programı I yalnızca sıranın uzunluğunun n'ye eşit olup olmadığını denetlerken Ders Programı II sıranın kendisini döndürür ve üç durumlu DFS tabanlı döngü algılama, Kahn algoritmasının BFS yaklaşımına geçerli bir alternatiftir. Sırada, Güçlü Bağlantılı Bileşenler için Kosaraju algoritmasını inceleyeceğiz.
Sıkça Sorulan Sorular
“Ders Programı I ve II” dersi ücretsiz mi?
Evet — “Ders Programı I ve II” 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.
“Ders Programı I ve II” dersinde ne öğreneceğim?
Ders ön koşullarını yönlü bir graf olarak modelleyin ve tüm derslerin tamamlanıp tamamlanamayacağını ve hangi sırayla alınacağını belirlemek için topolojik sıralama kullanın. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
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 3. dersidir.
“Ders Programı I ve II” 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.
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.
Bu kursun tüm dersleri
- Kahn Algoritması: BFS Topolojik Sıralaması
- DFS Sonradan Ziyaretli Topolojik Sıralama
- Ders Programı I ve II
- Kosaraju ile Güçlü Bağlantılı Bileşenler