FastPrepTraveling the Graphs

Traveling the Graphs

Optiver logoOptiver● HardFULLTIMEOA
Learn

Problem statement

Parse an undirected weighted graph and one route request.

  • edgeLine contains one or more edge tokens [A,B,5], separated by exactly one space.
  • routeLine has the form A->D,10: start node, destination node, and maximum allowed travel time.
  • Node names are single uppercase letters, and weights and the limit are unsigned decimal integers.

Return the unique shortest route as uppercase node names joined by -> when its total distance is at most the limit.

Otherwise return the first applicable error by priority:

  1. E1: input syntax error.
  2. E2: logical input error: a duplicate undirected edge, a self-edge, an undefined endpoint, a disconnected graph, or more than one shortest route.
  3. E3: the unique shortest route exceeds the allowed travel time.

Function

travelingTheGraphs(edgeLine: String, routeLine: String) → String

Examples

Example 1

edgeLine = "[A,B,3] [B,C,5] [C,D,2]"routeLine = "A->D,10"return = "A->B->C->D"

The only route from A to D has total distance 10, exactly the limit.

Example 2

edgeLine = "[A,B,3] [A,C,7] [C,D,2] [B,C,5]"routeLine = "A->D,10"return = "A->C->D"

A->C->D has distance 9, shorter than the alternative through B.

Example 3

edgeLine = "[A,B,5] [A,C,2] [B,C,4] [B,D,6] [C,B,7]"routeLine = "A->C,10"return = "E2"

[C,B,7] duplicates the already defined undirected edge [B,C,4].

Constraints

  • Every node is one of A through Z.
  • 0 <= edgeWeight, maximumTravelTime <= 10^9
  • The edge line contains at most 325 tokens.
  • No leading, trailing, or repeated whitespace is valid.

More Optiver problems

See Optiver hiring insights
public String travelingTheGraphs(String edgeLine, String routeLine) {
  // write your code here
}
edgeLine"[A,B,3] [B,C,5] [C,D,2]"
routeLine"A->D,10"
expected"A->B->C->D"
Checking account…