Cheapest Airport Route

What they ask

Egyptian candidates for Google's engineering internships (STEP and the regular SWE internship) interview remotely from Egypt with engineers in other offices, typically Europe or the US. The Cairo office itself is mostly non-engineering, so the loop is the global one: two back-to-back 45-minute technical video interviews with a 15-minute break, each with a different engineer. One of the two often opens with a warm-up, "what project are you most proud of?", for about five minutes, then the coding problem.

A problem reported from the first interview:

You are given flights between airports. Each flight has a source, a destination, and a cost. Compute the minimum total cost to travel from airport S to airport T. Return -1 if T is unreachable.

Examples

• Flights CAI->LHR 300, CAI->FRA 250, FRA->LHR 40, S = CAI, T = LHR: answer 290 (via FRA).
• Flights CAI->DXB 200, S = CAI, T = JFK: answer -1.

Constraints

• Up to 10^5 flights, costs are non-negative integers.
• Airports are strings; there may be several flights between the same pair.

What they look for

• Recognising this as single-source shortest path with non-negative weights and going straight to Dijkstra with a priority queue.
• Building the adjacency list from strings without fuss, and handling S == T.
• Tests you propose yourself: unreachable target, parallel edges, zero-cost flights.
• Complexity stated as O((V + E) log V).

The interviewers run your code mentally against edge cases, so narrate as you type in the shared document. Applications for these programs open in the autumn and decisions can take until March.