Google SDE On campus
Summary
I recently completed an on-campus SDE interview process at Google, which involved three rigorous technical rounds. The interviews focused on my problem-solving skills across data structures, algorithms, and a behavioral assessment.
Full Experience
First Round
The first round kicked off with a challenging algorithmic problem. I was presented with a scenario involving N passengers, each with a specific weight and value, and a ship with a maximum capacity C. My task was to determine the maximum total value of passengers that could be boarded without exceeding the ship's capacity. Initially, all passengers had the same value, which simplified the problem. However, a follow-up quickly introduced the complexity where values could differ for each passenger, pushing me towards a knapsack-type solution.
Following the technical problem, the interviewer transitioned to a behavioral question: 'Tell me about a time when you were leading a project and had a conflict of opinion with your teammate?' I shared an experience detailing how I navigated such a situation, focusing on communication and collaboration.
Second Round
The second round was heavily focused on graph theory. The interviewer described a graph problem where I was given a source node, a destination node, and a 'corrupted' node. The initial task was to determine if it was possible to reach the destination from the source, avoiding the corrupted node. This was followed by a series of progressively complex follow-ups.
The first follow-up required me to return an array of minimum distances from the source node to all other reachable nodes. Then, the problem introduced a 'virality' concept: nodes within a certain distance ('virality distance') from any corrupted node would also become corrupted. I had to re-evaluate reachability under this new condition. The final and most challenging follow-up extended this 'virality' concept to include multiple corrupted nodes, further complicating the pathfinding logic.
Third Round
The final round presented a dynamic programming or combinatorial problem. I was given the total number of houses, along with the predefined colors for the first and last houses. The colors could range from 1 to K. The core task was to calculate the number of unique ways to paint the remaining n-2 houses, adhering to the constraint that no two adjacent houses could share the same color. This round tested my ability to formulate a recursive solution with memoization or a bottom-up DP approach.
Interview Questions (6)
was there a time when you were leading a project and had conflict of opinion with your teammate?
A graph, source node, destination node, corrupted node will be given. Return whether you can reach the destination node from the source node.
Return array of minimum distances from the source node to all other nodes.
There will be a variable virality, nodes which are in range of virality distance from corrupted nodes will also be corrupted. Now return the same.
There can be multiple corrupted nodes. Now return the same.
number of houses, color of first house, color of last house will be given. Colors can be in the range of [1,K]. Number of combinations you can paint the other n-2 houses such that no two adjacent houses will have the same color.