Efficient Coding Challenge | Dataford Interview Questions

Unity's asset build pipeline must process assets only after all of their dependencies have been built. Given n assets and dependency relationships, count the number of valid complete build orders.

Asset a must be built before asset b for every pair [a, b] in prerequisites. Return the count modulo 1_000_000_007. If the dependencies contain a cycle, no valid order exists, so return 0.

Formal Specification

Implement count_build_orders(n, prerequisites).

n is an integer representing assets labeled 0 through n - 1.
prerequisites is a list of two-element integer lists, where [a, b] means asset a must precede asset b.
Return an integer containing the number of valid permutations of all n assets, modulo 1_000_000_007.

Constraints

1 <= n <= 20
0 <= prerequisites.length <= n * (n - 1)
Asset IDs are integers from 0 through n - 1
Each dependency contains two distinct asset IDs
Each dependency pair appears at most once
Return the result modulo 1_000_000_007

Function Signature

def count_build_orders(n, prerequisites):

Your question is Efficient Coding Challenge. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem