Google Question #3
Summary
I was asked a graph problem about finding the fastest favourite city from a source using Dijkstra's algorithm, and we discussed its runtime complexity.
Full Experience
Given are N cities and M roads that travel between the given pair of cities and time it takes to travel that road. Also we are given a list of favourite cities L and a source city S . we have to tell the favourite city which can be reached from source city the fastest(in minimum time)
Solution- Classic Dijkshtra
It was followed by a discussion on runtime complexity and how it was O(V+E log(V))
This went on for a while, since we had a little argument about the complexity of the inner loop.
Then a couple of follow ups
- Early Stoppage conditions
- a fix vertex V to be travelled in the way to favourite city for
- got a little confused and had to take a little help from the interviewer but eventually i told the right solution.
- i made a wrapper function which calls dijkshtra to find dist S-V + dijkshtra to find V- C( favourite city)
Interview Questions (1)
Fastest Favourite City
Given N cities and M roads, each road has a travel time. You are also given a list of favourite cities L and a source city S. Find the favourite city that can be reached from S in the minimum total travel time.