Google Software Engineer Interview Experience — L4 Phone Screen and Three Onsite Coding Rounds

Phone Interview

Given a binary tree representing reporting relationships in a company, where each node represents an employee and its parent represents the employee's direct manager, write an algorithm to find the nearest common manager of a given set of multiple employees. This is a variant of Lowest Common Ancestor.

1. There are K employees in the set and the tree height is H. Optimize the time complexity.
2. If the employee set is very large or queries are frequent, how would you preprocess and optimize?

Onsite Coding 1

Design a data structure for a temperature-monitoring system that supports inserting temperature data in real time and efficiently querying data from the last N days.

1. Implement insert(temperature) to insert a new temperature reading.
2. Implement get_moving_average() to return the moving average of the last N temperature readings.
3. Implement get_max_temp() to return the maximum of the last N temperature readings in O(1) time.

Onsite Coding 2

Given a two-dimensional grid containing a starting point, obstacles, and several delivery points, find the shortest route that starts at the starting point, makes all deliveries, and returns to the starting point.

1. There are few delivery points, N < 10, so dynamic programming or backtracking can be used to solve the Traveling Salesperson Problem (TSP).
2. If the grid is very large, how would you optimize pathfinding to reduce the search space?

Onsite Coding 3

Design a Logger Rate Limiter. Because of network delays, log messages may arrive with timestamps out of order.

1. Implement shouldPrintMessage(timestamp, message). If the same message has not been printed in the past ten seconds, allow it to print and return true; otherwise, return false.
2. Handle out-of-order arrivals, such as a log with timestamp 12 arriving before one with timestamp 10.

Googleyness & Leadership

The behavioral interview mainly assessed teamwork, conflict resolution, and personal growth.

1. Describe a serious disagreement with a product manager over product direction or technical implementation. How did you communicate and reach a consensus?
2. When a project has an urgent deadline and technical debt is seriously hurting development efficiency, how do you balance business delivery with code quality?