← All tasks Task 1 of 12 unsolved

1. Topological Sort of FK Graph

Graph Kahn's Algorithm ~25 min

Given database tables and foreign key relationships, return tables in loading order (parents before children). If a cycle exists, throw IllegalStateException.

This is how Synthesized.io determines the order to process tables during data masking and subsetting — you can't insert child rows until parent rows exist.

Setup (folded above the editor — click + to view): data class FK(val child: String, val parent: String), plus main() with the test cases.

Tests this task must pass

Basic FK chain — 5 tables, departments → users → orders → order_items plus products → order_items; verify parent-before-child for every edge.
No dependencies — 3 isolated tables, any permutation valid as long as all are present.
Cycle detection — a → b → c → a must throw IllegalStateException.
Diamond dependency — a → {b, c} → d; a first, d last, b and c in either order.
Self-reference is a cycle — FK("employees","employees") must throw.

data class FK(val child: String, val parent: String) //sampleStart fun topologicalSort(tables: List<String>, fks: List<FK>): List<String> { // Kahn's algorithm: BFS with in-degree counting // 1. Count in-degree for each table (how many parents it depends on) // 2. Start with tables that have 0 in-degree (no dependencies) // 3. Process table, decrement children's in-degree // 4. If not all tables processed → cycle exists TODO() } //sampleEnd fun main() { // Test 1: Basic FK chain val r1 = topologicalSort( listOf("order_items", "orders", "users", "products", "departments"), listOf(FK("users","departments"), FK("orders","users"), FK("order_items","orders"), FK("order_items","products")) ) check(r1.indexOf("departments") < r1.indexOf("users")) { "FAIL: departments before users" } check(r1.indexOf("users") < r1.indexOf("orders")) { "FAIL: users before orders" } check(r1.indexOf("orders") < r1.indexOf("order_items")) { "FAIL: orders before order_items" } check(r1.indexOf("products") < r1.indexOf("order_items")) { "FAIL: products before order_items" } check(r1.size == 5) { "FAIL: all 5 tables present" } println("✅ Test 1 passed: Basic FK chain") // Test 2: No dependencies val r2 = topologicalSort(listOf("a", "b", "c"), emptyList()) check(r2.size == 3 && r2.containsAll(listOf("a","b","c"))) { "FAIL: all tables present" } println("✅ Test 2 passed: No dependencies") // Test 3: Cycle detection try { topologicalSort(listOf("a","b","c"), listOf(FK("a","b"), FK("b","c"), FK("c","a"))) check(false) { "FAIL: should have thrown on cycle" } } catch (e: IllegalStateException) { println("✅ Test 3 passed: Cycle detected") } // Test 4: Diamond dependency val r4 = topologicalSort( listOf("d","b","c","a"), listOf(FK("b","a"), FK("c","a"), FK("d","b"), FK("d","c")) ) check(r4.indexOf("a") < r4.indexOf("b")) { "FAIL: a before b" } check(r4.indexOf("a") < r4.indexOf("c")) { "FAIL: a before c" } check(r4.indexOf("b") < r4.indexOf("d")) { "FAIL: b before d" } check(r4.indexOf("c") < r4.indexOf("d")) { "FAIL: c before d" } println("✅ Test 4 passed: Diamond dependency") // Test 5: Self-reference = cycle try { topologicalSort(listOf("employees"), listOf(FK("employees","employees"))) check(false) { "FAIL: self-reference should be cycle" } } catch (e: IllegalStateException) { println("✅ Test 5 passed: Self-reference cycle") } println("\n🎉 ALL TESTS PASSED!") }

import java.util.*; class FK { final String child, parent; FK(String child, String parent) { this.child = child; this.parent = parent; } } public class Main { //sampleStart static List<String> topologicalSort(List<String> tables, List<FK> fks) { // Kahn's algorithm: BFS with in-degree counting // 1. Count in-degree for each table (how many parents it depends on) // 2. Start with tables that have 0 in-degree (no dependencies) // 3. Process table, decrement children's in-degree // 4. If not all tables processed → cycle exists throw new UnsupportedOperationException("TODO"); } //sampleEnd static void check(boolean cond, String msg) { if (!cond) throw new IllegalStateException(msg); } public static void main(String[] args) { // Test 1: Basic FK chain var r1 = topologicalSort( List.of("order_items", "orders", "users", "products", "departments"), List.of(new FK("users","departments"), new FK("orders","users"), new FK("order_items","orders"), new FK("order_items","products")) ); check(r1.indexOf("departments") < r1.indexOf("users"), "FAIL: departments before users"); check(r1.indexOf("users") < r1.indexOf("orders"), "FAIL: users before orders"); check(r1.indexOf("orders") < r1.indexOf("order_items"), "FAIL: orders before order_items"); check(r1.indexOf("products") < r1.indexOf("order_items"), "FAIL: products before order_items"); check(r1.size() == 5, "FAIL: all 5 tables present"); System.out.println("✅ Test 1 passed: Basic FK chain"); // Test 2: No dependencies var r2 = topologicalSort(List.of("a", "b", "c"), List.of()); check(r2.size() == 3 && r2.containsAll(List.of("a","b","c")), "FAIL: all tables present"); System.out.println("✅ Test 2 passed: No dependencies"); // Test 3: Cycle detection try { topologicalSort(List.of("a","b","c"), List.of(new FK("a","b"), new FK("b","c"), new FK("c","a"))); check(false, "FAIL: should have thrown on cycle"); } catch (IllegalStateException e) { System.out.println("✅ Test 3 passed: Cycle detected"); } // Test 4: Diamond dependency var r4 = topologicalSort( List.of("d","b","c","a"), List.of(new FK("b","a"), new FK("c","a"), new FK("d","b"), new FK("d","c")) ); check(r4.indexOf("a") < r4.indexOf("b"), "FAIL: a before b"); check(r4.indexOf("a") < r4.indexOf("c"), "FAIL: a before c"); check(r4.indexOf("b") < r4.indexOf("d"), "FAIL: b before d"); check(r4.indexOf("c") < r4.indexOf("d"), "FAIL: c before d"); System.out.println("✅ Test 4 passed: Diamond dependency"); // Test 5: Self-reference = cycle try { topologicalSort(List.of("employees"), List.of(new FK("employees","employees"))); check(false, "FAIL: self-reference should be cycle"); } catch (IllegalStateException e) { System.out.println("✅ Test 5 passed: Self-reference cycle"); } System.out.println("\n🎉 ALL TESTS PASSED!"); } }

Kotlin solution

fun topologicalSort(tables: List<String>, fks: List<FK>): List<String> {
    val inDegree = tables.associateWith { 0 }.toMutableMap()
    val children = mutableMapOf<String, MutableList<String>>()
    for (fk in fks) {
        inDegree[fk.child] = (inDegree[fk.child] ?: 0) + 1
        children.getOrPut(fk.parent) { mutableListOf() }.add(fk.child)
    }
    val queue = ArrayDeque<String>()
    for ((table, deg) in inDegree) if (deg == 0) queue.add(table)
    val result = mutableListOf<String>()
    while (queue.isNotEmpty()) {
        val table = queue.removeFirst()
        result.add(table)
        for (child in children[table].orEmpty()) {
            inDegree[child] = inDegree[child]!! - 1
            if (inDegree[child] == 0) queue.add(child)
        }
    }
    if (result.size != tables.size)
        throw IllegalStateException("Cycle detected: ${tables - result.toSet()}")
    return result
}

Java solution

static List<String> topologicalSort(List<String> tables, List<FK> fks) {
    Map<String, Integer> inDegree = new HashMap<>();
    for (String t : tables) inDegree.put(t, 0);
    Map<String, List<String>> children = new HashMap<>();
    for (FK fk : fks) {
        inDegree.merge(fk.child, 1, Integer::sum);
        children.computeIfAbsent(fk.parent, k -> new ArrayList<>()).add(fk.child);
    }
    Deque<String> queue = new ArrayDeque<>();
    for (var e : inDegree.entrySet()) if (e.getValue() == 0) queue.add(e.getKey());
    List<String> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        String t = queue.removeFirst();
        result.add(t);
        for (String c : children.getOrDefault(t, List.of())) {
            int d = inDegree.get(c) - 1;
            inDegree.put(c, d);
            if (d == 0) queue.add(c);
        }
    }
    if (result.size() != tables.size())
        throw new IllegalStateException("Cycle detected");
    return result;
}

← Previous Next: Email Masking →