Google | Phone Screen | L5 | OCT 2024

Round 1

Questions: There is a map of cities - like a real world country's map. Some cities have roads between them, and it takes a known time to traverse each road.
I'm in city A and have a list of my favorite cities [F1..Fn]. Give an efficient algorithm to decide which of my favorite cities I can get to the fastest.

           +-----+      +-----+      +-----+
   8------>|  A  +-20-->|  B  +-4--->|  E  |
   |       +--+--+      +--^--+      +-----+
   |          5            2
   |          |
+--+--+    +--v--+      +--+--+
|  H  <-2--+  C  +--2-->  G   |
+--+--+    +-----+      +--+--+
   3                       6
   |                       |
+--v--+                 +--v--+
|  F  |                 |  D  |
+-----+                 +-----+

Follow-up Question #1: Another path

I realized I have some business to do in city B.
Give an algorithm that still finds the most quickly reachable favorite city, but on a path that goes through B.

Follow-up Question #2: Shortest path to end

I decided to visit B at the end of my travels (and stay there).
Give an algorithm that finds the shortest path to B that touches any of my favorite cities.