Reported February 2022
Optivershortest path

Traveling the Graphs

Reported by candidates from Optiver's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.

Get StealthCoderRuns invisibly during the live Optiver OA. Under 2s to a working solution.
Founder's read

Optiver reportedly asked this one in February 2022, and it looks like a plain shortest path problem until you read the error rules. Parse a line of bracketed edges, parse a route request, then return the unique shortest path or an error code. Dijkstra is the easy part. The grind is validation order and the uniqueness check. If you've got an OA invite for this, expect most failed tests to come from E1 versus E2 versus E3 priority, not from the graph search. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment.

The problem

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:
E1: input syntax error.
E2: logical input error: a duplicate undirected edge, a self-edge, an undefined endpoint, a disconnected graph, or more than one shortest route.
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.

Reported by candidates. Source: FastPrep

Pattern and pitfall

The pattern is Dijkstra with path counting. Run it from the start node, track the shortest distance to each node and how many shortest paths reach it. If the destination count is above 1, return E2. Zero-weight edges are allowed, so don't assume positive weights, but Dijkstra still works. The pitfall is order. First validate syntax strictly: exact brackets, single spaces, single uppercase letters, unsigned integers, no stray whitespace. Only then check logic: duplicate undirected edges (B,C equals C,B), self-edges, endpoints in the route that aren't defined, and a disconnected graph across all nodes seen. Only after all that compare distance to the limit for E3. Reconstruct the path with parent pointers. Where this breaks naive solutions is checking connectivity only between start and end, or counting ties incorrectly with zero weights. If you freeze on the parsing, StealthCoder is the hedge during the live OA.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.

If this hits your live OA

You can drill Traveling the Graphs cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made for the candidate who got the OA invite this morning and has 72 hours, not six months.

Get StealthCoder

Related leaked OAs

⏵ The honest play

You've seen the question. Make sure you actually pass Optiver's OA.

Optiver reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.

Traveling the Graphs FAQ

What's the trick in Traveling the Graphs?+

Dijkstra plus a count of shortest paths per node. If the destination has more than one shortest path, it's E2. The rest is strict parsing and checking error priority in the right order: E1, then E2, then E3.

How hard is this one really?+

The algorithm is medium. The difficulty is the spec. Many small rules for syntax and logical errors mean one missed case fails hidden tests. Write the validator first and test each error type separately.

What counts as a disconnected graph here?+

Based on the statement, it's a logical error (E2) when the defined nodes don't form one connected component. Check connectivity across every node mentioned in the edges, not only the start-to-destination path.

How do I handle ties with zero-weight edges?+

Zero weights can create multiple equal-length routes. Count paths during relaxation: on a strictly shorter distance, replace the count. On an equal distance, add counts. Any destination count above 1 means E2.

How do I prepare in 48 hours?+

Write Dijkstra with path counting from memory once. Then write a strict parser using exact checks for brackets, commas, single spaces, and digits. Test with the three examples plus a duplicate edge, a self-edge, and an over-limit route.

Problem reported by candidates from a real Online Assessment. Sourced from a publicly-available candidate-aggregated repository. Not affiliated with Optiver.

OA at Optiver?
Invisible during screen share
Get it