Google Interview Experience – Graph Problem (June 2025)
- Posted
- 1 Jul 2025
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)
- 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.