Allowed R6 · Within policy
{
"slug": "cheapest-airport-route",
"title": "Cheapest Airport Route",
"difficulty": "medium",
"tags": [
"coding",
"algorithms-theory",
"technical",
"intern"
],
"is_free": true,
"locked": false,
"frequency": 0.25,
"last_reported_at": "2024-01-24T09:12:53.883895Z",
"url": "https://www.mokabla.com/en/c/google/cheapest-airport-route",
"agent": {
"page": "https://www.mokabla.com/agent/en/c/google/cheapest-airport-route",
"question": "https://www.mokabla.com/agent/_call/get_question?company=google&question=cheapest-airport-route"
},
"company": {
"slug": "google",
"name_en": "Google"
},
"body_md": "## What they ask\nEgyptian 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.\n\nA problem reported from the first interview:\n\n> 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.\n\n### Examples\n- Flights `CAI->LHR 300`, `CAI->FRA 250`, `FRA->LHR 40`, `S = CAI`, `T = LHR`: answer `290` (via FRA).\n- Flights `CAI->DXB 200`, `S = CAI`, `T = JFK`: answer `-1`.\n\n### Constraints\n- Up to 10^5 flights, costs are non-negative integers.\n- Airports are strings; there may be several flights between the same pair.\n\n## What they look for\n- Recognising this as single-source shortest path with non-negative weights and going straight to Dijkstra with a priority queue.\n- Building the adjacency list from strings without fuss, and handling `S == T`.\n- Tests you propose yourself: unreachable target, parallel edges, zero-cost flights.\n- Complexity stated as `O((V + E) log V)`.\n\nThe 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.",
"follow_ups_md": "- Return the itinerary, not just the cost.\n- At most `k` stopovers are allowed. What changes?\n- Some flights have negative costs (promotions). Does your algorithm still work?",
"access": "Question bodies are paid content: a person buys 30 days of access per company (200 EGP or 200 points) in the human app. Agents get titles, tags and difficulty; bodies only for free questions."
}