As part of a scheduling system, we need to be able to determine the order to execute dependent tasks after parsing their definitions.
Tasks are identified by a lowercase word. Dependencies between tasks are denoted using a => b where a is a task that is dependent on b.
When a task has a dependency on one or more other tasks, those tasks must be executed first. If a task has no dependencies it is executed in the order that it has been declared. If a cyclic dependency is used, the system must detect it as an error and not enter an invalid state.
We estimate that there will never be more than 50 tasks at a time.
tasks : []
dependencies: []
result: []
tasks: [a,b]
dependencies: []
result: [a,b]
tasks: [a,b]
dependencies: [a => b]
result: [b,a]
tasks: [a,b,c,d]
dependencies: [a => b,c => d]
result: [b,a,d,c]
tasks: [a,b,c]
dependencies: [a => b,b => c]
result: [c,b,a]
tasks: [a,b,c,d]
dependencies: [a => b,b => c,c => a]
result: Error - this is a cyclic dependency
- Implement a solution in the language of your choice and prove that it meets the acceptance criteria.
- The supplied solution must compile (if required) and run on Windows 7.
- Submit your solutions by emailing a zip file to your agency no later than 09:00am on Thursday 15th August 2013.