Sharing my recent interview experience for a Google SWE-III role in India. Recruiter reached out to me through email and after clearing recruiter screening moved to DSA screening. I was given 3 wks to prepare.
The process had 2 screening rounds (1 DSA + 1 Googliness), which were elimination rounds to move forward to the 2 onsite rounds (both DSA).
Round 1 - DSA Screening
1. Given an undirected, acyclic, connected graph where each node has at most 3 edges, find a node which, when made the root, converts the graph into a binary tree.
Follow-up: Given an undirected, connected, acyclic graph where each node has at most 3 edges, and each node is colored either Black or White, find a root such that:
- The graph becomes a binary tree.
- The tree alternates in color across layers (e.g., Depth 0: White, Depth 1: Black, Depth 2: White, etc.).
- Either White or Black can be the starting color.
Interviewer expectation: Solve the follow-up without using BFS traversal in O(N).
Round 2 - Googliness Screening
Some of the questions I remember:
-
Have you ever given critical feedback to someone? How did they take it? What was the situation?
-
Give an example of a challenging technical problem you faced recently. How did you solve it, and what was the result?
-
How would you handle people who disagree with the majority decision on a non-work-related matter?
-
Tell me about a time when your manager set reasonable demands.
Follow-up: Describe a situation with unreasonable demands. -
Describe a situation where you had a disagreement with a colleague or manager. How did you resolve the conflict, and what was the outcome?
-
Describe a situation where you helped an underperforming team member improve.
I prepared for the Googliness round using this post, and most of the questions were already covered there.
Timeline: I heard back from the recruiter after ~3 weeks that I was moving to the onsite rounds and was given one week to prepare.
Round 3 - DSA (Onsite)
Given a large M × N grid containing multiple disconnected islands surrounded by ocean, and an API:
countLakes(island, coordinates)
where coordinates is a point belonging to the given island, return the number of lakes within that particular island.
1 = Land
0 = Water/Ocean
A lake is a water region completely enclosed by land. Water connected to the ocean should not be counted. There can be multiple lakes within an island, and there can be multiple disconnected islands in the grid. Assume there is ocean outside the grid as well.
Example:
0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0
0 1 0 1 0 1 0 0
0 1 1 1 0 1 1 0
0 0 0 0 0 0 0 0
Here there are 2 disconnected islands.
If coordinates belongs to the first island, countLakes() should return 1, since that island has one enclosed lake.
Note: The problem was initially quite lengthy and ambiguous. After asking clarifying questions, it essentially boiled down to a DFS-based solution.
Round 4 - DSA (Onsite)
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].
Given the startTime, endTime, and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time ranges.
Question: Maximum Profit in Job Scheduling
I initially discussed why a greedy approach would not work and then arrived at a recursive take/not-take approach with memoization. With a hint, I optimized the search for the next compatible job using binary search.
Interviewer expectation: O(N log N) solution.
The onsite rounds were conducted back-to-back on the same day.
I haven't heard back from the recruiter yet regarding the final outcome, so waiting to see how it goes.
Sharing this in case it helps anyone preparing for an interview. Good luck to everyone preparing! 🚀
