Skip to content
Get started

Valid orders for a small build

Seven build tasks A-G have dependencies (X→Y means X must finish before Y starts):

A→B, B→C, D→E, E→F, A→E, C→G, F→G.

Tasks run one at a time. How many valid orders (topological sorts) are there?

Show hints (2)+
  1. Is there a task that must always come last?
  2. Two chains of 3 interleave in (63)\binom{6}{3} ways; which of those break A→E?

Answer

Reveal answer →

16

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions