Google Question #3

549
Sep 16, 2026

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

  1. Early Stoppage conditions
  2. a fix vertex V to be travelled in the way to favourite city for
  3. got a little confused and had to take a little help from the interviewer but eventually i told the right solution.
  4. i made a wrapper function which calls dijkshtra to find dist S-V + dijkshtra to find V- C( favourite city)
Comments (3)