Determine feasible task ordering
Company: Adobe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
Quick Answer: 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.