Google Question #3

Posted
16 Sept 2026
134 reads

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.

How it went

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)

Questions asked (1)

  1. 01

    Fastest Favourite City

    Data Structures & Algorithms

    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.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!