MediumCoding

Course Schedule IV

Asked at

Groww

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Build directed prerequisite edges.
02Choose closure strategy from n and query count.
03Propagate prerequisite sets in topological order.
04Answer each query from the closure.
05Discuss cycles according to the contract.

Reference answer

Because many prerequisite queries must be answered, preprocess reachability instead of running DFS per query. For a DAG, topologically process courses while maintaining for each course the set of its prerequisites. For edge u to v, union prereq[u] and u into prereq[v]; bitsets make this efficient for moderate n. Then query (a,b) is true when a belongs to prereq[b]. Floyd-Warshall is an alternative O(n cubed) closure when n is small and implementation simplicity matters. Be clear about edge direction: u prerequisite of v means u -> v. If cycles are possible, clarify whether they are invalid input or require general reachability. Bitset/topological preprocessing is roughly O((n+e)*n/wordSize) with O(n squared) storage, followed by O(1) queries.

Then expect these follow-ups

When would Floyd-Warshall be preferable?
Tests: follow-up reasoning
How would you handle a new prerequisite edge online?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question