GOOGLE STEP: Decoding The Internship Interview
Almost every computer science geek have a dream of working in FAANG and on the top of them is GOOGLE, I’m also one of them. And to fulfill my dreams I applied to GOOGLE’s STEP Internship program in my 2nd year and missed the opportunity not by inches but by a few milimeters. I am going to share my GOOGLE STEP Internship experience and other details in this blog with some tips and learning from my experience. So make sure to read till the end.
About
STEP (Student Training in Engineering Program), formerly known as Engineering Practicum, is a 12-week internship for first and second-year undergraduate students with a passion for computer science. The internship program has a focus of providing development opportunities to students from groups historically underrepresented in tech, through technical training and professional development.
In India, this program focuses on girls in their first or second year of undergraduate studies. But boys can also apply for the abroad campuses of GOOGLE. So, I’d encourage all first and second-year students to give it a shot, at the very least.
I applied for the Google-Sydney.
How To Apply?
You can apply for the program from the Google’s career page. But there would be lesser chances of your application being shortlisted. So it’s better to apply through referrals. I’ll write an article on referrals in detail, but for now you can approach any employee of Google. It would be better if the person know you. Ask him to refer you for the job ID of the STEP internship you want to apply for.
Recruitment Process
Round 0: Resume Screening
So, the very first hurdle is resume screening. I’ve applied through Google’s career page so I feel myself lucky that my resume was shortlisted. But I strongly recommend to go for referrals as this can increase your chances exponentially. You need to have a pretty decent resume with at least 1 or 2 good projects and some technical skills too. Be honest while mentioning the projects and skills in resume, as interviewer will surely discuss about your projects and skills. If you are a competitive coder then mention your ratings from different platforms like CodeChef or CodeForces. It’s the best thing to mention in a resume and will exponentially increase your chance as they always look for problem solving skills in a candidate.
Round 1: Online Coding Test
It might take 25–30 days or more to get a response from Google. If your resume gets shortlisted then you’ll receive a mail from Google which will be having a test link and password for the online coding test.
This round contains 2 coding questions based on mathematics and data structures-algorithms and you need to solve both within 45 minutes. There are some visible as well as hidden test cases. Your solution should pass all the test cases.
So, I’ll discuss both the problems from my Round 1.
Q1. An array arr[] consists of 0 & 1. A FLIP operation one in which you turn 1 to 0 and vice versa. You have to do at most 1 FLIP operation on a sub array. Find maximum number of 1’s you can have after the operation in arr[].
Input:
1
5
1 0 0 1 0
Output:
4
Explanation:
We can perform a flip operation in the range [1,2]
After flip operation array is : 1 1 1 1 0
APPROACH:
- Count number of 1's.
- Change 0’s to 1 and 1’s to -1.
- Using Kadane’s Algorithm find maximum sum of contiguous sub array.
- Final Sum will be count of 1’s + maximum sum.
Time complexity is O(n) for this approach.
Whole code of the solution can be found here.
Q2. Given a number N, find the number of binary strings of length N that contains consecutive 1’s in them.
Input
3
2
5
15
Output
1
19
31171
Explanation
In the above first test case there are 4 strings of length 2, the strings are 00, 01, 10 and 11. Only the string 11 has consecutive 1's.
APPROACH:
After doing some pen and paper work. I observed a pattern that for n, output is equal to [2^n-fib(n+2)]. Where fib() returns the (n+2)th Fibonacci number.
Time Complexity is O(n) for this approach.
Note: It was mandatory to give the solution having time complexity of O(n) or lesser. Whole code of the solution can be found here.
Questions were not straight forward. There were lot of stories revolving around and we need to find the patterns and logic from them. I am writing questions based on those logic and patterns as the stories were too long to remember.
So this was the 1st round. The questions were based on logic, mathematical algorithms, bit manipulation and greedy. Luckily there was no DP or tree question. So, I would rate this round as easy to medium. I took around 10 minutes to solve 1st question, and around 25 minutes to solve the 2nd including the optimizing solution from O(n²) to O(n).
Round 2: Telephonic Interview
I received a mail after 10 day of Round 1, stating that I’ve cleared round 1 and it’s time for the final step towards STEP. This was a telephonic round and I had to code on google docs and not on any IDE so I would strongly recommend to practice writing code on google docs as it is way different then any IDE.
For the first 10 minutes of the interview, I introduced myself to the interviewer followed by a short discussion on my project. As I completed my project just before applying, so every thing was fresh in my mind & I answered all the questions related to that. Although my project was not that great but interviewer was quite impressed just because I was knowing every thing about my project, so here is another tip that go through your project before interview and you should know every thing about your project.
After the project discussion, the real grind started.
She gave me a questions and asked the approach. The questions is:
Q1. Given an integer N, how many structurally unique binary search trees are there that store values 1…N?
On seeing the question I lost a bit of my confidence as I hadn’t practiced tree questions that well although I had enough theoretical knowledge on trees. Interviewer guessed that I’m was not very confident. She was very kind and friendly, she told me to relax and try ad-hoc approach.
So, I started doing some pen and paper work and after writing some test cases, I suddenly observed that it’s a Catalan Number logic. So, I told her that it’s a catalan series and it can be solved in O(n) time complexity using the Catalan formula i.e. (2n)! / ((n + 1)! * n!). She told me that my answer was correct but she asked me to apply recursion approach to it and code it on google docs. I coded the recursive approach. She asked me to optimize it further, so I noticed that recursion was doing a lot of repeated work(by drawing recursion tree) so I applied DP approach and coded the solution.The time complexity of DP approach is O(n²) but she only wanted to test my recursion and DP concept. It took me around 15 minutes to give her a coded solution. She was quite impressed as she did not expect the DP solution from me. The code for all the approaches can be found here.
She gave me another question which goes as :
Q2. Find the smallest window in a string containing all characters of another string
Input: string = “this is a test string”, pattern = “tist”
Output: Minimum window is “t stri”
Explanation: “t stri” contains all the characters of pattern.
After reading the question, asking some clarifications and little bit of pen and paper work I came up with the following brute force approach.
- Generate all sub strings of string1 (“this is a test string”)
- For each sub string, check whether the sub string contains all characters of string2 (“tist”)
- Finally, print the smallest sub string containing all characters of string2.
She told we that it would work perfectly. She asked me to optimize the solution to time complexity of O(n). I tried very hard but could not come up with the solution. After the interview was over, I tried the problem again and came up with optimized approach after some days. Code of the optimized solution can be found here.
So, I was trying hard to optimize the solution but she told me that there is no more time left. She gave me the feedback that I have the potential and a good thinking capability but need to enhance the knowledge of DSA.
I got a mail from Google few days after Round 2 stating that they cannot proceed further with my application and I missed STEP internship at Google in my final round. After reading the mail I had mixed emotions I was sad that I missed the opportunity of working in GOOGLE because of one question, but I was happy as well that I reached in the final round and solved both the questions without any preparation and advanced knowledge of DSA.
My Learning From Whole Process
- Never underestimate yourself.
- Never lie in your resume because in round 2, the interviewer will get first impression of your’s during project discussion and believe me half of the decision will be taken within first 10–15 minutes of the interview.
- Never give up. Keep trying. If you are not able to come up with the solution, ask for hints from interviewer. Believe me they will help you in the best possible way.
- Do not directly jump to solve the questions. Ask doubts, ask for more test cases, ask for constraints.
- Try coding on google docs or any other text editor which do not have the features of IDE.
- Data Structures and Algorithm is the heart of whole process.
- Keep speaking while thinking until the interviewer asks you to keep quiet. Share your thought process with the interviewer.
- Last but not the least and the most important one, if you know the solution of any question which is given to you then show some acting skills and do not directly jump on to the solution. If you do this, then interviewer might change the question and it might get difficult for you.
This is how GOOGLE appeared to me after that mail. I was able to see it but the image was blur. After coming so close, I missed that opportunity. But, I learnt a lot from that experience and I’m in the process of de-blurring this image by working harder and I am confident that one day I’ll see it clearly.
