←ENG-DSA-020Database Migration Runner (Graph DFS)
00:00
🐍 Python Idle
Mode:Web

Database Migration Runner (Graph DFS)

CompaniesShopify, Airbnb
Est. Time~35 min
LevelMid
GraphsDFSTopological Sort
🚨 P0 Incident
ShopifyAirbnb

Shopify's ORM migration system runs hundreds of database migration scripts on deploy. A migration can depend on another (e.g., "AddOrderIndex" needs "CreateOrdersTable" to run first). A developer accidentally created a circular dependency, causing the migration runner to deadlock. The system must detect cycles before starting any migrations.

📥 Assigned to:You — Mid Engineer
Your Task

Our ORM runs database migration scripts. A script can require another script to run first (e.g., `AddUsersTable` depends on `EnableUUIDExtension`). Determine if all scripts can execute successfully, or if there is a circular dependency dead-locking the system.

⏱ Time: O(V + E)💾 Space: O(V)
Example 1
Input:  scripts=3, deps=[(1,0),(2,1)]
Output: True
Example 2
Input:  scripts=2, deps=[(1,0),(0,1)]
Output: False
🔒 +3 hidden test cases — revealed on Submit
Hints
Loading editor…
Test Output
▶ Run Code to test against examples · Submit to judge all 5 test cases
EngPrep — Real Engineering. Real Interviews.