Google Interview Part-3 [On-site]

If you have not read my post Google Interview Part-1 and Google Interview Part-2 then go check it out

Choosing the Interview-Date

I was given a link to a survey form. I was asked to give my available dates. I filled up the survey form. They scheduled the interview on my least preferred date, and this is because they were actively interviewing a large number of candidates. After choosing the date I booked the flight and the hotel by contacting Carlson Wagonlit Travel which is Google?s travel agent, where I had to provide record locator number for verification which was provided to me by the recruiter.

Preparation materials and key points

Below are the preparation materials that I got in the onsite confirmation e-mail :

• Software Engineering interview prep doc
• Career Cup Sample Google Interview Questions
• Hangout on Air: Candidate Coaching Session: Tech Interviewing
• Hangout on Air: Google recruiters share technical interview tips
• Practice/learn new code from prior Code Jam competitions
• Check out sites like topcoder.com, leetcode.com
• Project Euler is a good resource for additional programming questions

Below are the key points that I got in the onsite confirmation e-mail:

• Interviewers will evaluate your technical ability and basic CS knowledge, including algorithms and data structures, as well as critical thinking skills.
• Your interviewer may give you hints to guide you along. A few hints are a normal part of the process and don?t get discouraged if you find your interviewer giving them.
• Be sure to ask clarifying questions to avoid any misunderstanding. In short, restate the interviewer?s question, confirming that you understand the problem, and describe how you plan to solve the problem and why.
• Remember to communicate your thought process to the interviewer while solving the problem. It?s helpful for the interviewer to understand how your mind works when approaching a problem.
• Please use the full code, not pseudocode.
• It is helpful to review the book Programming Interviews Exposed or Cracking the Coding Interview.
• As mentioned above, make sure to utilize sites like topcoder.com. It?s great to practice coding under a time constraint.
• Our engineers are interested in your problem-solving skills and cognitive ability so it?s important to talk through your thought process and reasoning.
• Interviewers expect a good working knowledge of algorithms, data structures, logic problems, problem-solving, and CS fundamentals. They may also ask you about anything on your resume.

Google Coaching Session

Before the onsite interview, Google schedules Google University Tech Coaching Program which is a coaching session on Google Hangouts. In this session, one of the Googler will make you understand the onsite interview process. He will address you the do?s and the don?ts in an onsite process. The candidate can ask the Googler about any doubts or questions he has. Here are some of the key points that I took from the session:

• You can wear anything you want in the Google interview. Just be careful to wear something nice. Wearing formals is not mandatory. All my interviewers were in casuals.
• Use the restroom before the interview, if you use the restroom during an interview then you will lose your precious interview time.
• Always be ready for follow-up questions in the interview.
• Ask for questions.
• Discuss all the approaches before you code.
• Ask for edge cases like empty string or null value.
• Verbally express your thoughts even while coding.
• You don?t have ctrl c + ctrl v in whiteboard coding so leave some space in between.
• Always test your code after you complete.
• Discuss the time complexity and space complexity of the code.

From the session, I learned that Google is not only looking for the best coders but they are looking for the best coders who can express their thoughts while coding.

Overview of the Google interview process

Onsite interview process

The onsite interview has 5 interview rounds. The first two rounds are coding rounds of 45 minutes each. Then there is a lunch interview for 1 hour with a Googler. It?s not an active interview. You can ask any questions you have about working at Google in the lunch interview. Then there are two coding rounds of 45 minutes each

After the interview process

All four interviewers write their feedback. There is no feedback for the lunch interview. All the four interviewers have to write detailed feedback of the interview they had with you. Feedback is typically broken down into four categories (Analytical Ability, Coding, Experience, and Communication) and you are given a score from 1.0 to 4.0 overall, where 2.8 is the threshold of hire vs. no-hire. Interviewer feedback is collated and sent to a hiring committee, which ultimately decides whether to move forward with an offer, reject the candidate. If your average score is below 2.8 then the feedback is not even forwarded to the hiring committee and you receive a rejection. To know more about the interview process at google check out this link: https://www.quora.com/What-is-the-interview-process-like-at-Google-What-are-the-people-like

Preparation for the onsite interview

I had one month to prepare. This time I prepared Google onsite questions on Leetcode from Google Playground which is Leetcode premium feature. I tried to practice medium and hard difficulty level Google onsite questions listed in the Google Playground. I wanted to do a mock interview with an experienced person so I chose https://aonecode.com/ services to have a mock interview with a Google engineer. The service is of 100 bucks. I got pretty positive feedback from the engineer. She told me to practice advanced data structures like segmented tree, Red black tree and practice advance algorithms like Dijkstra, A star to improve my chances of getting hired at Google. I also watched Irfan Baiqus whiteboard coding video series which was very helpful. I mostly focused on solving Leetcode questions. I practiced the following data structures:

1. Stacks and Queues
2. Heaps (Don?t ignore this data structure)
3. Hashmaps (Very important data structure)
4. Binary Tree, Binary Search Tree
5. Linked List
6. Double ended queue
7. Tries (Prefix-tree)
8. Segment Tree
9. Graph
10. Disjoint sets

I practiced the following algorithms:

1. Depth First Search
2. Breadth First Search
3. Recursive and iterative pre-order traversal
4. Recursive and iterative post-order traversal
5. Recursive and iterative in-order traversal
6. binary search algorithm on binary search trees and sorted arrays
7. Dijkstra and A-star
8. Merge sort and Quick sort
9. Dynamic Programming, Greedy Algorithms, Recursion

The important part is that you not only know these algorithms and data structures but also understand when and where to apply these algorithms and data structures.

My Strategy for the onsite

• After getting the question I will discuss all the approaches that I have in my mind.
• I will think of all the algorithms that will be useful.
• I will ask for edge cases.
• I will think of all the data structures that will be useful.
• If I do not come up with an optimal solution then I will come up with a Naive solution and code that. While I am coding the solution and explaining it verbally, I will also keep on constantly thinking for a better solution.
• Speed is important.
• Communication is important. I will verbally speak out my thoughts even while coding.
• Even if I find a solution I will constantly think of improving it by pruning, early stop techniques.
• I will write neat and beautiful code.
• In the end, I will test my code manually line by line.
• I will discuss the time complexity and space complexity of my code.

The Day before Onsite

I landed at SFO airport. Checked in the Grand Hotel Sunnyvale. The Hotel was a nice Hotel. Got a welcome letter from Google which made me feel special and made me realize that tomorrow is the big day of which I have always dreamt:

I just relaxed that day. The room had Alexa and I was checking that out, watching TV, relaxing on king sized bed. I was just enjoying the hotel room and was making sure that I am stress-free.

The onsite interview day

I woke up at 8:00 AM. Had a light breakfast. Booked an Uber cab at 9:00 am. There was traffic that day. If you are having google onsite, then try to leave the hotel at least 1 hour before the reporting time. Reached the Google office at 10:00 AM. The feeling was amazing. I was excited and nervous.

Interview Round 1

The interview time was 10:45 AM but my interviewer, let?s say Interviewer-A, picked me up at 10:15 AM. Interviewer-A was a very nice person. We had 30 minutes before the interview starts and Interviewer-A figured out that I was nervous so just to make me comfortable he showed me around. He showed me the bowling alley, Google cafeteria, Sleeping room, dry cleaning, conference rooms. I was very amused by the Google workplace and it motivated me to give my best in the interview. Interviewer-A made me feel comfortable and told me not to be nervous. Before the interview, Interviewer-A asked me if I want water or want to use the restroom. Finally, the interview started in a meeting room. He gave me the question. I can not disclose the questions due to NDA. It was an easy question for me. I discussed my solution and asked him if I could start coding. My solution was the best solution in terms of time complexity. The markers in the room were not working. Interviewer-A ran to get the markers. I wasted 8 minutes while he was getting the marker. Before the interview starts, do check that the markers are working. Interviewer-A got me the markers, and I started writing the code. I realized that whiteboard coding is so tough. I would recommend all of you to do whiteboard coding before you go for your onsite interview. I realized that I was very slow. And at the end of 5 minutes, I had to complete one function and that time Interviewer-A jumped off his seat and asked me never mind completing the code and asked me the time complexity. He was so enthusiastic in asking me the remaining questions and he did all this so that I can answer all the questions he has within the time. My interview ended. Interviewer-A took the pic of the whiteboard and I went back and saw that I could not figure out what did I write on the board, and I was thinking that he?s going to write a feedback based on that pic. If I can not understand what I have written on the board than how can he understand that. I calmed myself and kept in mind to be speedy and to write neatly on the board in the next interview. The 1st round went well but because I ran out of time the Interviewer-A could not ask me follow-up questions.

Interview Round 2

The next interviewer, let?s say Interviewer-B came in the room. The Interviewer-A passed on the feedback sheet to the Interviewer-B. Interviewer-B asked me to give an introduction about myself. Then he gave me a question to solve, the question was related to traversal in a 2D matrix. I gave him my approach. He asked me if I can think of a better approach. I gave him an O(1) approach. He told me to code my approach. I quickly coded the solution and tested my code. This time I knew I had to write neatly and quickly and I did that. He asked me a follow-up question to the same problem to which I gave him an O(n) solution. I quickly wrote the code. Now he asked me another follow-up question to the same problem. I discussed my approach but he was not sure if it was correct and I was confident that my approach will work. I saw the time and I had 15 minutes left, so I told him that let me quickly code the solution that I discussed and simultaneously I will explain you the working of my solution and explain you the correctness of my approach. I quickly coded my solution and before I could optimize the solution, the time was up. Interviewer-B took the pic of the whiteboard and passed the feedback sheet to the lunch interviewer, let?s call him Interviewer-C. This time I saw the whiteboard and I could make out what I have written.

Lunch Interview

This is a much-needed interview. I was pretty much exhausted by the first two rounds because I was constantly speaking. The Interviewer-C took me to one of the Google Cafe to have lunch. The place was very crowded. Everyone had come to have lunch. I kept in mind that I have two more interviews to go so I can not eat heavy that will make me feel dizzy so I only ate salad with tofu and some fried potatoes. Interviewer-C was very boring. I asked him ?how does he feel working at Google? and he told me ?It feels the same as working at any other place?. There was no conversation from Interviewer-C?s side. I was the one who was making efforts for the conversation to continue. After lunch, he showed me the campus and then he dropped me to the next interview room.

Interview Round 4

A young girl was my next interviewer, let?s call her Interviewer-D. Interviewer-D was very shy and spoke very softly. She came and did not ask for an introduction and just said I have a question for you. Interviewer-D gave me a question. The question was related to DFS and BFS. I quickly told her my approach to the problem. I started coding and coded my solution in 5 minutes. I also tested my solution to the input she gave. She pointed out that my solution will go on an infinite loop if there was a cycle in the input. So, I quickly fixed my code and I also used pruning to optimize my solution. She gave me a follow-up question to which I quickly gave an O(1) solution. She did not tell me to code it because it was a minor change in the code. We still had 20 minutes left so she asked me a new question. This question was related to the binary search algorithm. I quickly told her all the possible solutions and binary-search will work best with a time complexity of O(log(n)). She agreed to my solution and told me to code it. I quickly coded the solution. She took the pic of the board. We still had 5 minutes left, so I asked her how long she is working for Google and what is her role at Google.

Interview Round 5

By this time I was completely exhausted. I was also excited because I nailed my last interview. I was not intimidated by a single question in all the rounds, practicing on Leetcode did help me. The next interview came in, let?s call him Interviewer-E. Interviewer-E looked like a very senior person. He gave me a problem to solve. I discussed my approach and Interviewer-E told me to go ahead and code it. I coded the solution very quickly. Interviewer-E gave me a test case to test my code and my code was wrong because I misinterpreted the question. Interviewer-E again explained the question. I quickly coded my solution and this time it was right. My solution was an O(n) solution. Interviewer-E gave me a follow-up question. I discussed my approach to the follow-up question and Interviewer-E told me to code it. I quickly coded the solution with a time complexity of O(n). Interviewer-E asked me to optimize my solution. I could not think of any optimization. So I wrote a few test cases that I could think of and their output on the board. I was looking for a common pattern that could help me optimize the current solution. It took me 15 minutes to find the pattern and I finally cracked it. I told him my approach to which Interviewer-E agreed and then asked him how much time is left. Interviewer-E told me you have 5 minutes to code your approach. So I quickly started to code the solution but I could not complete it in 5 minutes. Interviewer-E stopped me, I felt bad that I could not complete it and then Interviewer-E told me ?at least you were able to figure out how to optimize it.? Interviewer-E dropped me out of the building.

After the interview

When I came out of the building I was very proud of myself. That day I realized that anyone who works hard can crack Google?s interview, although I was rejected by the hiring committee. I just want to tell all of you out there that if I can do it then you can do it too. If Google is your dream company then work hard on your algorithmic and data structure skills and I am sure you will get a job at Google. I won?t discuss my rejection story because I think it is very discouraging and by this post, I do not want to discourage anyone. I just want to encourage all of you to work hard for your dream company and you will get it. All my travel expenses and food expenses were reimbursed by Google.

Thanks for reading. If you enjoyed this article, feel free to hit that clap button ? to help others find it. (Do you know that you can clap more than once? Try it and see for yourself!)