Combine topological sort with level grouping: tables at the same level have no dependencies on each other and can be processed in parallel. Level 0 = no parents; Level 1 = depends only on level 0; etc.
Synthesized.io schedules each level in parallel, then awaits before moving to the next — a 5× speedup on wide schemas with many independent tables.
Setup (folded above the editor — click + to view): data class FK(val child: String, val parent: String), plus main() with the test cases.
data class FK(val child: String, val parent: String)
//sampleStart
fun buildLevels(tables: List<String>, fks: List<FK>): List<List<String>> {
// Combine topological sort with level grouping.
// Tables at the same level have no dependencies on each other
// and can be processed in parallel.
// Level 0: tables with no dependencies
// Level 1: tables depending only on level 0
// etc.
TODO()
}
//sampleEnd
fun main() {
// Test 1: Linear chain
val r1 = buildLevels(listOf("a","b","c"), listOf(FK("b","a"), FK("c","b")))
check(r1 == listOf(listOf("a"), listOf("b"), listOf("c"))) { "FAIL: linear chain. Got: $r1" }
println("✅ Test 1: Linear — $r1")
// Test 2: Two roots
val r2 = buildLevels(listOf("a","b","c"), listOf(FK("c","a"), FK("c","b")))
check(r2.size == 2) { "FAIL: 2 levels" }
check(r2[0].toSet() == setOf("a","b")) { "FAIL: a,b at level 0" }
check(r2[1] == listOf("c")) { "FAIL: c at level 1" }
println("✅ Test 2: Two roots — $r2")
// Test 3: Diamond
val r3 = buildLevels(
listOf("a","b","c","d"),
listOf(FK("b","a"), FK("c","a"), FK("d","b"), FK("d","c"))
)
check(r3.size == 3) { "FAIL: 3 levels for diamond" }
check(r3[0] == listOf("a")) { "FAIL: a at level 0" }
check(r3[1].toSet() == setOf("b","c")) { "FAIL: b,c at level 1" }
check(r3[2] == listOf("d")) { "FAIL: d at level 2" }
println("✅ Test 3: Diamond — $r3")
// Test 4: No dependencies
val r4 = buildLevels(listOf("x","y","z"), emptyList())
check(r4.size == 1) { "FAIL: all at level 0" }
check(r4[0].toSet() == setOf("x","y","z")) { "FAIL: all together" }
println("✅ Test 4: No deps — $r4")
println("\n🎉 ALL TESTS PASSED!")
}
Hint
Run Kahn's algorithm one level at a time: collect every table currently at in-degree 0, that's the level. Then decrement the in-degree of all their children — the new zero-degree set is the next level. Repeat until empty.
Solution
fun buildLevels(tables: List<String>, fks: List<FK>): List<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 levels = mutableListOf<List<String>>()
var current = inDegree.filterValues { it == 0 }.keys.toList()
while (current.isNotEmpty()) {
levels.add(current)
val next = mutableListOf<String>()
for (t in current) {
for (child in children[t].orEmpty()) {
inDegree[child] = inDegree[child]!! - 1
if (inDegree[child] == 0) next.add(child)
}
}
current = next
}
return levels
}