Google Interview Experience – Graph Problem (June 2025)

Posted
1 Jul 2025
476 reads

Summary

I participated in a Google screening round in June 2025, lasting 45 minutes, where I was presented with a graph problem. My approach involved Dijkstra’s algorithm to precompute shortest paths and then binary search for queries, but I received no feedback post-interview despite follow-ups.

How it went

Status: Screening Round
Duration: 45 minutes (5 mins intro + 15 mins explanation + 25 mins coding)

[IMP] Final Thoughts
I gave my best during the interview. The problem was interesting and implementation-heavy under time constraints, but I felt confident in my approach and communication.

However, despite following up 3–4 times, I never received any feedback — neither a rejection nor a selection.
Honestly, this part was disappointing.
As candidates, we invest a lot of time preparing and genuinely care about the process, so some form of closure would go a long way.

Questions asked (1)

  1. 01

    Graph: Max Cities on Shortest Path within Time Limit

    Data Structures & Algorithms

    There are N cities in a town, and some of them are connected with roads. Each road takes a certain number of hours to travel. You're given the road network as a list of edges:

    edges = [ [u, v, h], ... ]
    Where:

    • u and v are city indices.
    • h is the time in hours to travel between u and v.

    You are also given:

    • A source city s.
    • A list of queries. Each query has:
    • A destination city d
    • A time limit H (in hours)

    Goal
    For each query (d, H), find the maximum number of cities you can visit on the shortest path from s to d within H hours.

    Example:
    Let's say:

    source = 2
    One of the shortest paths to destination = 10 is:
    2 → 4 → 9 → 12 → 15 → 18 → 10, and the shortest distance is 50 hours.
    You can precompute something like:

    cities_visited_by_time = [2, 4, 9, 12, 15, 18]
    This means:

    City 1 is reached at 2nd hour,
    City 2 at 4th hour,
    ...
    For a query with H = 14, you can do a binary search (lower/upper bound) on cities_visited_by_time to find how many cities are visited within 14 hours.

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!