Hi, in this post , i would like to share my interview experience for google through the on-campus drive of our college (Tier-1). <3
A bit of background history about myself
(You can skip to the OT and interview questions below) :
I am a CS ungrad student at a Tier 1 college in India. Initially entering college, i wanted to pursue research in CS, as i have a lot of people in my family pursing highers.
I entered the college with high hopes and dreams of exploring this field, and enjoying college life in general.
But all these dreams were crushed after my first semester. My father had been diagnosed with Stage 3 colon cancer. he underwent a surgery during the sem break, which unfortunately was a failure, which meant that he needed to take chemotherapy for the next few months.
Now my college is very far away from my home, and only my parents live in my house. So it was hard to leave them alone when i was returning back to college for my second semester. This was the time when i decided to put peace to my dreams for pursuing research, and started working on my DSA and development skills, as i needed to get a job as soon as possible ( My fellow peeps who have had the unfortunate experience with a cancer patient, they know that money flows down the drain like water during their treatment).
My second semester was spent mostly on DSA preparation on leetcode. I also applied for a Tech Club in our college which focuses on Web development. This club is supposed to be the best club in our college, cause people who get selected for this club usually get a very good intern.
After a few months of hardwork, i made it to the top coding club of our college. By this time , my father's condition had worsened , leading to him taking a second set of an even stronger chemotherapy. So when i got into this club, i assured my father that everything is gonna be alright and that he doesnt have to worry about money at all. As my mom was the only one taking care of him at the time, my selection into this club got her hopes high as well.
Third semester in my college started, and i entered this semester with high motivation to work even hard and get an internship as fast as possible. But, this motivation did not last long.
On 18th of October, 2023, my father unfortunately passed away.
This was devastating for me, especially because i was really close to my father. He was one of those chill dads with whom i could share anything. I had my first drink with him. He used to tease me for not having a girlfriend, so when i got one , he was the first one to know. But yea, his death was a major setback for me. But still, i had to work hard to support my mom, so after a few weeks I resumed my Leetcode grind.
A few months passed, I was still grinding Leetcode, but i was kicked out of the coding club because i wasnt performing optimally. I lost my grandfather in my fourth semseter. Things were just not looking good for me.
My only hope now was to get a good intern in the following semester. But this hope was almost crushed by another disaster. One of my professors decided to fail me in a course in fourth semester. This was a disaster, because if I have an active backlog going into the next semester, I cant sit for most companies for their internship process.
Fifth semester started, and companies started coming in the first week itself, so i could sit for only those companies which did not have "No active backlog" criteria. For reference, I could technically only APPLY for 2 out of the first 8 companies or so.
To my surprise, Google came to our campus without any eligibilty criteria. This was my golden chance. I will explain my interview process below.
Online Test(Offline)
The first round was an online test. There about 5 sets of 2 questions each. You could get any one of the sets. I spent my full time in the first question only, so dont remember the second question. All I know that it was a graph question.
Q: You are given an array of n integers. A good triplet is defined as a set of indices i,j,k such that 0<= i < j < k < n, and they satisfy the follwing conditions -
-> for every index q where i < q < j , A[i] > A[q] and A[j] > A[q].
-> for every index p where j < p < k , A[k] > A[p] and A[k] > A[p].
The distance of a good triplet (i,j,k) is defined as (k-i+1). Among all the good triplets in the array, find the maximum distance.|
(You only have to return the maximum distance, not the triplet ).
LOGIC
Used a monotonic stack to precompute for each index, how far to the right i can expand and how far to the left i can expand.
Now i iterate over the array, and i assume my current index to be the first element of the triplet. Using the precomputation i can find out my second index, and again the third index for the the triple, and hence calculate the distance of my triplet in O(1) time.
There was an edge case which took me a lot of time to figure out, which is also difficult for me to explain on paper. My apologies.
RESULT -> Initally only passed 3 test cases, but i made a submission in the last mintute, which passed all test cases. Got shortlisted for Personal Interviews
PERSONAL INTERVIEW 1
Was greeted with a pretty new Google employee. She was very nice to me. The first 5 mins we spent on introductions (even she introduced herself to me). Then she asked me the follwing question :
Q:
A string is called grouped if all the distinct characters in the string occur together. For example, AAABBBBBCDEE is a grouped string whereas AAABBBACCED is not a grouped string as the character A's do not occur together.
You are given a grouped string s of size n and an integer k. You have to divide the string into groups of size at most k, i.e., the first k characters are part of group 1, then next k characters are part of group 2 and so on. Notice that the last group may contain less than k characters.
A character c is said to be distributed over the groups if it occurs in multiple groups.
For example, given string AABBCCDEE and k = 2. The groups formed are AA, BB, CC, DE and E. As the character E occurs in multiple groups, it is called distributed over the groups. Rest all characters A,B,C and D are not distributed over the groups.
Given a grouped string s and an integer k, output the number of characters which are not distrubuted over the groups.
LOGIC
This wasnt that difficult of a question. But as it was my first interview, i struglled to properly write the code for it.
My method was to maintain two hashmaps, a global hashmap keeping track of the characters i have encountered in the previous gorups, and another for the characters i encounter in the current group.
Then i traverse the groups, and see whether a character has appeared in different groups. Of course, i did a lot of optimizations to this solution during the interview.
i spent about 30 mins fully on this problem, which left me only 15 mins for the second question.
Q:
You are given a binary tree. Each node either contains the value 0 or 1.
An island of 1 is defined as a group of ones surrounded by zeroes or are at the boundary of the tree.
Given the root of such a binary tree, return the number of islands of one.
Example:
0
/ \
1 0
/ \ / \
1 1 1 1This tree has 3 islands of 1 .
LOGIC
I want to see how many ones i can group together. If there are no zeroes in the tree, the answer is 1. But, the presence of zeroes in the tree is splliting any group of ones.
So, from here i see that , a node having value zero will stop any island of one that growing upwards from it's child. else , it will merge with the island of its child and continue it to it's parent.
CODE
bool search( TreeNode* cur, int* result) {
//The function return whether there is an ongrowing island from this node upwards.
if(!cur) return 0;
int c1 = search( cur->left, result);
int c2= search( cur->right, result);
if( cur->value == 0){
// Because value is 0, it will split any island that is ongrowing
*result += c1 + c2;
return 0;
}
//otherwise this node merges with any oncoming island
return 1;
}
int number_of_islands(TreeNode* root){
int result = 0;
if( search(root, &esult){
//Edge case where the root is 1
result += 1;
}
return result;
}RESULT
Even though i took time in the first question, i was able to think, explain and write the solution for the second question in about 12 minutes. I think this is where i impressed the interviewer. The rest few mins of the session were spent in general talks about the company and their workculture (which sounded very exciting).
SHORTLISTED FOR SECOND INTERVIEW
PERSONAL INTERVIEW 2
Got a call for second interview within 5 mins of my first interview. This was later delayed by 30 mins, after which i was greeted with a very friendly interviewer. The first few minutes were spend in introduction (again , the interviewer introduced themselves first, which i really liked), after which the interviewer even gave me a chance to relax for a minute before starting my interview. Then he began the interview.
P.S. ( The questions were given in a story format, which i will not write here. I will just write the core concept the question is asking from us. If you want the story, just reply in the comments.)
Q: (Easy)
Given a binary array of n integers, whose values are either 0 or 1, find the length of the longest subarray that consists of only zeroes.
Example :
0 0 1 0 0 0 1 1 0
Ans = 3 ( 0 0 1 0 0 0 1 1 0 )
LOGIC
Similar to this problem https://leetcode.com/problems/max-consecutive-ones/description/.
Q: (Medium)
Given a binary grid, whose values are either 0 or 1, find out the largest area of adjacent ones.
(Adjacency of two cells is defined by horizontal and vertical cells , not diagonal cells).
Example :
1 0 0 1
1 1 1 1
0 0 1 1
0 0 0 0
Answer = 6
1 0 0 1
1 1 1 1
0 0 1 1
0 0 0 0
LOGIC :
Similar to this problem https://leetcode.com/problems/max-area-of-island/
Q: (Hard)
Given a binary grid whose each cell contains either a one or a zero, return the largest rectangle you can make whose cells are only zeroes.
LOGIC
Similar to this problem https://leetcode.com/problems/maximal-rectangle/description/
RESULT
This round went good, i was able to explain, solve and write the code for every problem in the time frame. Then the last few minutes were again spent on dicussing the work culture at google (again, seemed very exciting).
AFTER A FEW HOURS, I WAS SELECTED FOR AN INTERNSHIP OFFER FROM GOOGLE !!!
INTERVIEW EXPERIENCE
I would like to break this down in points.
-> The interviewers were really nice and approcachable, allowing me to comfortably explain each and every step of my solution.
-> In the whole interview process , not a single questions from dev or CS fundamentals was asked. It was purely DSA prep and a bit of Competitive Programming that helped. This is absolutely not the case for other companies.
-> No questions from my projects in resume, or anything from my resume was asked, which was surprising.
OVERALL LIFE EXPERIENCE
This section is another story telling section, for those who read the first segment about my life.
As you might have read, my life was full of ups and downs. I have a had some amazing memories, and some of the worst experiences.
A few years ago, the younger me never imagined myself in a Tier 1 college and getting an internship offer from Google, nor could he imagine the death of his father.
From almost being suicidal after having a backlog in course and thinking i cannot get an intern...... to writing this post about my achievement with a tear down my eye, I have come a long way.
Through this tough experiences in my life, I have learnt a very important part of life.
HAPPINESS IS A CHOICE
You will never know what life has in store for you. You could have whatever you want tommorow and still be sad and worried about something, or you can have all hopes shattered in life and still be happy. The choice is yours.
My past experiences have changed me as a person. A person, who tries to find peace in everything, who does his work without thinking much about the result. Someone, who appreciated every second that he is alive, knowing fully well that whatver he does , wont really matter when i die someday.
I can have all the riches i want.... I can have the best job i want..... I can be the richest person in the whole. But nothing will bring back the moments i had with my father. NOTHING, i repeat
NOTHING WILL BRING BACK MY FATHER
So, If I cant predict what is going to happen in the furture, what is the point of worrying about it :)
Today's world is filled with a lot of pressure and stress, be it about your job or about your relationships. So, do your work happily and enjoy your life to the fullest. Because at the end, no body will care about how much money you earned, or how much hardwork you did. All that matters is that if you are content with what you do.
To anyone going through tough times (especially because of intern season), I would like you to think about the bigger picture. Does it really matter in the long run? Some days you think that 10th class board are important, next you think 12th boards are important, then JEE/NEET comes, then CGPA in college, then INTERNSHIP, then PLACEMENTS, then JOB SECURITY , the smthg else..... It just goes on.
The point of life is that you are happy, so be happy with what you do and leave the rest to the world :).