Katkat
Back

Determine feasible task ordering

AdobeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates knowledge of graph algorithms and dependency management, emphasizing concepts such as topological ordering and cycle detection and the ability to determine feasibility and produce a valid execution sequence.

You are given n tasks labeled 0..n−1 and a list of dependency pairs (a, b) meaning task a requires task b to be completed first. Implement functions to (

  1. determine whether all tasks can be completed and (
  2. return any valid execution order if it exists. Analyze time and space complexity and discuss how your solution behaves on large sparse versus dense dependency graphs.