Ders programı II: geçerli bir ders sırası

Problem

Course Schedule ile aynı kurulum: 0..numCourses-1 arası dersler ve {ders, önceAlınması} çiftleri. Bu sefer cevap evet/hayır değil: tüm dersleri ön koşullara uyarak bitiren bir sıra döndür. Birden fazla geçerli sıra varsa herhangi biri kabul edilir. Döngü yüzünden imkansızsa boş dizi döndür.

numCourses = 4, ön koşullar = [{1, 0}, {2, 0}, {3, 1}, {3, 2}]

    0
   / \
  1   2
   \ /
    3

Olası çıktılar: [0, 1, 2, 3] ya da [0, 2, 1, 3]

numCourses = 2, ön koşullar = [{0, 1}, {1, 0}]   -> []
numCourses = 2, ön koşullar = [{0, 1}]           -> [1, 0]

Netleştirme soruları

• Birden fazla geçerli sıra varsa herhangi biri olur mu, yoksa belirli bir sıra (ör. sözlük sırasında en küçük) mı isteniyor? (Herhangi biri. Sözlük sırası istenirse kuyruk yerine min-heap gerekir.)
• İmkansız durumda boş dizi mi, exception mı?
• Kenar yönü: {a, b} "b önce" anlamında mı?
• Ön koşulu hiç olmayan dersler de çıktıda olmalı mı? (Evet, tüm dersler.)

İpuçları

Yaklaşım

Kaba çözüm: Tüm permütasyonları deneyip ön koşullara uyan ilkini bulmak; O(V!·E). Ya da her adımda tüm dersleri tarayıp ön koşulları bitmiş birini seçmek; O(V·(V + E)).

Kahn algoritması (seçilen çözüm): Course Schedule'daki çözümün aynısı; tek fark, kuyruktan çıkan dersi bir sonuç dizisine yazmak. Neden geçerli bir sıra? Bir ders c kuyruğa ancak derecesi 0 olduğunda, yani c'yi bekleten tüm p -> c kenarlarının kaynağı p zaten kuyruktan çıkıp işlendiğinde girer. Dolayısıyla her kenar için p, sonuçta c'den önce yer alır.

DFS post-order: Bir düğümün tüm "sonrasındakiler"i bitince düğümü listeye ekle; liste ters topolojik sıradır, sonda ters çevrilir. Üç renk ile döngü tespiti aynı geçişte yapılır. Kahn'a göre daha az sezgiseldir ve özyinelemelidir; ama sıra üretmenin klasik ders kitabı yoludur.

Sözlük sırasında en küçük sıra istenirse: ArrayDeque yerine PriorityQueue kullanılır; her adımda hazır derslerin en küçüğü seçilir. Zaman O((V + E) log V) olur.

Java çözümü

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public final class CourseScheduleII {

    /** Geçerli bir sıra döner; döngü varsa boş dizi. */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) unlocks.add(new ArrayList<>());
        int[] inDegree = new int[numCourses];
        for (int[] p : prerequisites) {
            unlocks.get(p[1]).add(p[0]);
            inDegree[p[0]]++;
        }

        ArrayDeque<Integer> ready = new ArrayDeque<>();
        for (int c = 0; c < numCourses; c++) {
            if (inDegree[c] == 0) ready.offer(c);
        }

        int[] order = new int[numCourses];
        int taken = 0;
        while (!ready.isEmpty()) {
            int course = ready.poll();
            order[taken++] = course;                      // kuyruktan çıkış sırası = topolojik sıra
            for (int next : unlocks.get(course)) {
                if (--inDegree[next] == 0) ready.offer(next);
            }
        }
        return taken == numCourses ? order : new int[0];
    }
}

Sonucu baştan int[numCourses] olarak açmak, List<Integer>'dan diziye dönüşümü ve kutulamayı ortadan kaldırır. taken sayacı hem yazma indeksi hem de döngü kontrolü olarak iki iş görür.

Karmaşıklık

• Zaman: O(V + E).
• Bellek: O(V + E) komşuluk listesi; O(V) derece dizisi, kuyruk ve sonuç.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Elmas: [0, 1, 2, 3] (bu implementasyonun ürettiği sıra; [0, 2, 1, 3] de geçerli olurdu).
• İki düğümlü döngü: [].
• Tek ders, ön koşul yok: [0].
• Kendine ön koşul: [].
• {0, 1}: [1, 0]; kenar yönünün doğru kurulduğunu gösterir.
• 3.000 rastgele graf: döngüsüz olanlarda çıktının bir permütasyon olduğu ve her {ders, önce} çifti için önce'nin daha erken geldiği doğrulandı; döngülü olanlarda (bağımsız bir "kaynakları tekrar tekrar sil" kaba çözümüyle tespit edildi) boş dizi döndüğü kontrol edildi.

Birden fazla doğru cevap olan problemlerde test, sabit bir beklenen çıktıyla değil geçerlilik kontrolüyle yazılmalıdır. Bunu mülakatta söylemek, test yazma olgunluğunu gösterir.

Mülakatçı için

Genelde Course Schedule'dan hemen sonra takip olarak gelir; Kahn ile çözen aday için birkaç satırlık değişikliktir. Bu yüzden ölçülen şey daha çok netlik ve kenar durumlarıdır: yön, boş dizi, test stratejisi. DFS ile çözen adayda post-order ve ters çevirme adımlarını açıklamasını iste.

İpucu zamanlaması: Course Schedule'ı az önce çözen bir aday ipucuna ihtiyaç duymamalıdır. Bağımsız sorulduysa Course Schedule'ın ipuçlarını kullan. Aday DFS'te pre-order eklerse (düğüme girerken), elmas örneğini ver: 0, 1, 3, 2 çıkabilir ve 3, 2'den önce gelir.

Takip sorusu 1: Sözlük sırasında en küçük geçerli sırayı döndür. Beklenen: PriorityQueue<Integer>; O((V + E) log V).

Takip sorusu 2: Geçerli sıranın tek olup olmadığını söyle. Beklenen: Kahn sırasında kuyrukta herhangi bir anda birden fazla eleman varsa birden fazla sıra vardır; her adımda kuyruk boyutu tam 1 ise sıra tektir (LeetCode 444 benzeri).

Takip sorusu 3: Bu bir veritabanı migration aracı (Flyway/Liquibase benzeri) ve migration'lar arasında bağımlılık var. Neye dikkat edersin? Beklenen: deterministik sıra (aynı girdiye her ortamda aynı sıra, bu yüzden tie-break kuralı), döngüde hatayı hangi migration'ların oluşturduğunu gösteren mesaj, bağımsız migration'ları paralel çalıştırma imkanı (Kahn katmanları).

Benzer problemler

• Course Schedule (LeetCode 207)
• Alien Dictionary (LeetCode 269)
• Sequence Reconstruction (LeetCode 444)
• Sort Items by Groups Respecting Dependencies (LeetCode 1203)
• Minimum Height Trees (LeetCode 310)