FastPrepResolve Task Dependencies
Problems/Resolve Task Dependencies

Resolve Task Dependencies

Amazon logoAmazon● HardFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: This practice version is about an 88% match to the available interview report. Mandatory and weighted optional dependencies, returning an order when the graph is acyclic, removing the cheapest optional dependency that resolves a cycle, and returning an empty result for an unresolvable mandatory cycle come directly from the report. Edge orientation, tie-breaking, the exact interpretation of multiple cycles, output ordering, the callable interface, examples, and numeric limits were not shown, so those execution details are defined below.

There are n tasks numbered from 0 through n - 1. A dependency [u, v] means task u must be completed before task v.

The array mandatory contains dependencies that cannot be removed. Each row [u, v, cost] in optional contains a removable dependency u -> v and its cost.

  • If the graph containing every dependency is acyclic, return its lexicographically smallest topological order without removing anything.
  • If it is cyclic, consider removing exactly one optional dependency. Among the optional dependencies whose removal makes the entire graph acyclic, remove the one with the smallest cost. If costs tie, remove the one appearing earlier in optional. Return the lexicographically smallest topological order of the resulting graph.
  • If no single optional dependency can make the graph acyclic, return an empty array.

Function

resolveTaskOrder(n: int, mandatory: int[][], optional: int[][]) → int[]

Examples

Example 1

n = 4mandatory = [[0,1],[2,3]]optional = [[1,2,7]]return = [0,1,2,3]

All dependencies are already acyclic, so none is removed. The only valid order is [0,1,2,3].

Example 2

n = 3mandatory = [[0,1]]optional = [[1,2,5],[2,0,2]]return = [0,1,2]

The dependencies form the cycle 0 -> 1 -> 2 -> 0. Removing 2 -> 0 costs 2, which is cheaper than removing 1 -> 2.

Example 3

n = 2mandatory = [[0,1],[1,0]]optional = []return = []

The mandatory dependencies form a cycle, and there is no optional dependency that can be removed.

Constraints

  • 1 <= n <= 500
  • 0 <= mandatory.length, optional.length
  • mandatory.length + optional.length <= 2000
  • Every dependency endpoint is in [0, n - 1], and no dependency is repeated.
  • 0 <= cost <= 1000000000

More Amazon problems

  • Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
See Amazon hiring insights
Saved
class Solution {
    public int[] resolveTaskOrder(int n, int[][] mandatory, int[][] optional) {
      // write your code here
    }

}
Checking account…