I have been practicing DSA and Algorithms from a long time(around 3 years) and was wishing for an opportunity from google from long but always my CV used to get rejected but finally in November my wish got fulfilled and a recruiter from Google reached out to me over linked in and contacted me for google rounds.
Although I got rejected, in my Onsite Round 2 still like to share my experience to the community so that it helps others in preparing.
Phone Screen:
It was a DP problem dont remember the exact question but like it was like to find the size of the largest identical binary tree size of a tree , I was able to solve the problem . We have to apply DP memoization to get the result of already computed subtree and I was able to clear this round.
After 2 days recruiter reached out to me and told I am just on border line it was kind of leaning Hire from her and I got proceeded to Onsite rounds and for Onsite I took 1 month time for preparation and in that I solved all the google assessment contests which are there in leetcode + daily and weekly problems + contests + google previous 3 months questions tagged on leetcode and with this prep I was confident that it should be enough but I was wrong!
Onsite Round 1: This happened in Feb 2025, and interviewer asked me this problem:
Please write a function that takes two rhyme schemes, one short and
// one long, and, if possible, extends the short one to make them
// equivalent.
// Examples:
// ABB ABBBA -> ABBBA
// DEE ABBBA -> DEEED
// AAB OORRQQ -> AABBCC (or AABBDD, etc.)
// ABB OORRQQ has no valid extension
there was lot of confusions happened between me and recruiter but there is only one good thing happened and that I was able to successfully code it correct in last moment which saved me and recruiter ended up in giving me "Leaning No Hire"
But still my recruiter was positive as coded my problem correctly and proceeded me to 2nd Round.
Onsite Round 2:
Given an undirected acyclic graph with each nodes having atmost 3 edges.
Given a color list which contains color of each node where color of each node can be Black or White.
You need to find a root such that :
- It is a valid Binary tree
- It forms a alternating pattern like BWBW or WBWB across levels.
In this round I was simply screwed up and grilled like anything as I was not able to get anything near to the optmized solution but somehow coded the brute force solution O(n^2) type to which recruiter was not happy.
There was one more question he first asked me as without colors choose a root with valid binary tree simple , to which after he gave hint i quickly caught that any node with degree <=2 is the answer so quickly coded it , and then he gave this question and to which i coded the brute force one where for each node I applied dfs to find if we have alternating colors or not .But the recruiter wanted O(N) solution in it .
I am still not sure as how this can be done in O(N) , would be great if anyone can please give its solution or any variant of it on leetcode ?
Next Day interviewer called and told that the review is not positive side and it was no hire .
Then my third Round didnt happen. Recruiter asked me to further prepare and asked me to ping after 6 months.
It was overall a very good experience.
Your suggestions and comments will be much appreciated.