Google Interview Experience – Graph Problem (June 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.
Full Experience
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.
Interview Questions (1)
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.