FastPrepDelivery Origins and Reachable Destinations

Delivery Origins and Reachable Destinations

Atlassian logoAtlassian● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

An automated robot factory ships packages along one-way cart routes. Each pair [from, to] in paths is a directed route between two named locations. For this exercise, assume the routes form a directed acyclic graph; the source example is downward-directed but no general cycle policy is stated.

An origin is a location with no incoming route. A destination is a location with no outgoing route. For each origin, find every destination reachable by following one or more routes.

Return one row per origin. Its first string is the origin, followed by its distinct reachable destinations. For this exercise, assume rows are sorted lexicographically by origin and destinations are sorted lexicographically within each row.

For this exercise, assume locations are exactly the endpoints appearing in paths; repeated path pairs are allowed and do not duplicate destinations. Empty input returns an empty list.

Function

deliveryDestinations(paths: String[][]) → String[][]

Examples

Example 1

paths = [["B","K"],["C","K"],["E","L"],["F","G"],["J","M"],["E","F"],["C","G"],["A","B"],["A","C"],["G","H"],["G","I"]]return = [["A","H","I","K"],["E","H","I","L"],["J","M"]]

A reaches H, I and K; E reaches H, I and L; J reaches M. These are the source's unordered results sorted for this interface.

Example 2

paths = [["start","a"],["start","b"],["a","end"],["b","end"]]return = [["start","end"]]

Both branches reach the same sink end, so it appears only once.

Example 3

paths = [["A","B"],["C","D"]]return = [["A","B"],["C","D"]]

Each component has its own origin and destination.

Constraints

  • For this exercise, assume 0 <= paths.length <= 500 and at most 300 distinct locations.
  • Every path has exactly two nonempty location names, and the directed graph is acyclic.
  • For this exercise, assume location names have 1 through 30 case-sensitive ASCII letters or digits.

More Atlassian problems

See Atlassian hiring insights
public String[][] deliveryDestinations(String[][] paths) {
    // Write your code here.
    return new String[0][];
}
paths[["B","K"],["C","K"],["E","L"],["F","G"],["J","M"],["E","F"],["C","G"],["A","B"],["A","C"],["G","H"],["G","I"]]
expected[["A", "H", "I", "K"], ["E", "H", "I", "L"], ["J", "M"]]
Checking account…