Sort Tables by Foreign Key Order
Difficulty: Medium · Topics: Graph, Topological Sort, Database · Acceptance: 25.0% of 4 submissions
Difficulty: Medium | Tags: Graph, Topological Sort, Database
Description
Given a list of database tables with their foreign key relationships, return an ordered list where parent tables come before child tables. This determines the correct insertion order.
Implement:
sortTablesByFK(tables) → String[]
Examples
Example 1:
Input:
tables = [
{name: "orders", fk: ["users", "products"]},
{name: "users", fk: []},
{name: "products", fk: ["categories"]},
{name: "categories", fk: []}
]
Output: ["categories", "users", "products", "orders"]
or ["users", "categories", "products", "orders"]
(any valid topological order)
Example 2:
Input:
tables = [
{name: "comments", fk: ["posts", "users"]},
{name: "posts", fk: ["users"]},
{name: "users", fk: []}
]
Output: ["users", "posts", "comments"]
Example 3 — Circular dependency:
Input:
tables = [
{name: "A", fk: ["B"]},
{name: "B", fk: ["A"]}
]
Output: Error — "Circular dependency detected"
Constraints
1 <= tables.length <= 1000- No self-referencing foreign keys.
- If a circular dependency exists, throw an error.
- Multiple valid orderings may exist — any is acceptable.
Hints
Hint 1
This is a classic topological sort problem. Build a directed graph where an edge from A → B means "B depends on A".
Hint 2
Use Kahn's algorithm (BFS with in-degree tracking) or DFS-based topological sort.
---
## Validation