Google 2026 New Grad R1: Nearest Taxi Distances and Dynamic Taxi Updates

Role: Software Engineer, New Grad
Result: Passed R1
Report time: January 2026

Coding: distance to the nearest taxi

A matrix contains several taxis. For every cell, return its shortest distance to any taxi.

The candidate recognized the Rotten Oranges pattern and used multi-source BFS from all taxi cells.

Follow-ups asked:

1. Could DFS be used instead? The candidate explained that BFS is the natural choice for unweighted shortest distances.
2. How would the system handle taxis randomly coming online or going offline?

For dynamic updates, the candidate proposed computing distances from each taxi and storing per-cell candidates in a heap. Adding a taxi would add records; removing one would invalidate its records. After the interview, they suggested also maintaining a dictionary of online taxis and using lazy deletion.

Practice: Distance to the Nearest Taxi in a Grid

The technical round finished in about 30 minutes, followed by 15 minutes of conversation. The dynamic follow-up was discussed verbally rather than fully implemented.

Behavioral interview

After two reschedules, the candidate completed a behavioral round covering:

• A complex project and conflict between teammates
• Helping another person
• Having more work than could be handled and choosing priorities
• Learning something recently
• Giving feedback and handling the reaction
• Responding when one person takes credit for the whole team