Google Software Engineer Interview Experience — Phone Screen, Googlyness, and Two Graph-Heavy Onsite Rounds

Phone Interview

Given an n x m matrix, the start is (n-1, 0) and the end is (n-1, m-1). The allowed moves are up-right, right, and down-right. Count the total number of paths to the end.

1. Follow-up 1: There are some checkpoints in the matrix. Count the total number of paths that visit all of the checkpoints.
2. Follow-up 2: The checkpoints must be visited in order. Given that every move changes the column (so each column can contain at most one checkpoint), count the paths and optimize the space complexity.

Googlyness Round

1. What would you do if someone took credit for your work? How would you handle that conflict?
2. When you have multiple tasks with different priorities, how do you manage your time and coordinate day to day?

Onsite Round 1

Given an undirected, unweighted graph. Alice is at one node and needs to reach a target node. Find Alice's shortest path to the target.

1. Follow-up 1: Find all the nodes that could appear on some shortest path.
2. Follow-up 2: Bob is at another node. Alice picks one of the shortest paths and starts moving, and Bob starts moving at the same time. Determine whether Alice can reach the target safely without being caught by Bob.

Onsite Round 2

Given a list of logs in this format:

timestamp, userA connects to userB
timestamp, userB connects to userC

You are also given the total number of users. Find the earliest timestamp at which all users are connected to each other.

1. Follow-up 1: Find a timestamp after which the maximum distance (path length) between any two users is at most k, and all users are already connected.
2. Follow-up 2: The logs now also include removing a friend, in this format:

timestamp, userB unfriends userC

Find the timestamp at which all users are connected.