Efficient Coding Challenge

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Efficient Coding Challenge. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output