Status: New grad
Position: Software Engineer, New Graduate
Location: Mountain View, CA
Date: October 17, 2019
My entire experience with Google this year was amazing. I felt very supported by all of my recruiters throughout the entire process. Even after getting rejected, my recruiter was very empathatic when she told me about it over the phone which made me feel slightly less horrible about it lol.
Preparation:
I completed around 80 Leetcode problems (mostly medium and easy only a handful of hard problems), problems from CTCI while mixing in some archived Google Kickstart questions from time to time. I’m thinking of competing in some programming competitions since they sound fun and participating will likely help improve my algorithmic thinking for the next time that I apply.
Recruitment and coding challenge:
The process began when a recruiter sent me an email to inquire about my interest in exploring full time opportunities (I applied for the SWE internship and was denied so they have my info). After spending some time to prepare, I was sent the online assessment. After the online assessment, I was able to skip the first round phone interviews and go straight onsite (I think this is due primarily to competing offer deadlines from Slack + Microsoft).
Onsite:
Round 1 [Technical 45 min]:
Given a word of length n, and n six-sided dice with a character in each side, find out if this word is constructible by the set of given dice
I first started off trying to come up with a greedy solution, but I caught myself going down the wrong path and realized this wouldn’t work. I mentioned that we can just use a brute force/backtracking approach, and the interview nudged me to go in this direction. I created a dice class which used an unordered_set in C++ to represent the characters that can be used with the dice. I eventually wrote the backtracking solution which I said was O(n!) [please correct me if I’m wrong]. I definitely should’ve spent some time trying to improve upon this solution.
Round 2 [Behavioral/Googliness Inteview 30 min]:
I was asked about times where I had to work under pressure/a short time period. I was also asked to explain a time when I was working on a project and people had conflicting viewpoints and how I handled it. I was also asked about some things about my previous internship experiences and things of that nature. Pretty standard behavioral questions.
Round 3 [Technical 45 min]:
I was asked a variant of this problem (https://leetcode.com/discuss/interview-question/340230/google-onsite-implement-logger) except that it was framed as requests instead of processes. In the way the problem was explained to me, you can’t print out the log for a request started at time i unless:
- It has finished being processed
- All requests with starting times less than i have finished being processed.
Because of this formulation, I began thinking of it as a dependency problem. I started overcomplicating the problem and confusing myself which lead me to take longer than I probably should have. In order to use this idea of dependency, I thought to use a linked list which in a way can be thought of as a dependency graph. Upon each request, I created a pointer to a struct which contained request id, start and end time. I used a doubly linked list (to efficiently put new requests at the back of the list) and an unordered_map which mapped ID’s to a struct pointer (to efficiently access and update fields in the struct). My logic to print out elements was to iterate from the head of the linked list and print out all requests that have been completed. I think I was incorrect in assuming that the Logger would be called in order such that the list will be inherently sorted based on start time [i.e I assumed calling start() at time 1 and calling start() at time 2 would mean that you called start(id1, 1) followed by start(id2, 2) instead of something like start(id1, 2) at time 1 followed by start(id2, 1) at time 2]; I did not ask the interviewer about this. My advice to others, make sure to ask clarifying questions!
Lunch Break :
Had a lunch break with a Google engineer. I wanted to temporarily forget the fact that I was interviewing at Google to relieve some stress and just have a normal conversation with a human being. This person was very nice and down-to-earth so we talked a lot about each other’s background, interests outside of software engineering, and other things. They also took me on a tour of the office which was great.
Round 4 [Technical 45 Min]:
We started a bit late because of a room conflict. The first 5-10 minutes started off with the interviewer asking me to elaborate on my previous projects. They then asked to discuss common ways to represent graphs and I talked about the adjacency matrix and adjacency list representations and discussed their tradeoffs (probably not as in depth as I know, but when under pressure, it is harder for me to remember and relay all the information that I know. To get used to this, do plenty of mock interviews!. I did a handful, but probably not enough). Then my question was along the lines of:
Given a large directed graph with nodes that are labeled with particular colors (e.g green, red, blue etc…) and a source node, find out if there is a path from the source node to a green node where the path contains only blue nodes.
My approach was to use DFS and check the color of the nodes along the path. If I found a node that wasn’t blue or green, I’d short circuit the DFS down that particular path since it would no longer be considered valid. Then if I found a green node, I’d stop searching and return true. I also had to be careful to consider cycles in the graph.
Round 5 [Technical 45 Min]:
This problem involved storing a large string using a tree data structure where substrings are stored at the leaf nodes. I was first told to design the data structure and class that would support this. I thought of something very similar to a segment tree. I used a binary tree and I proposed to store the range of indices in each node (e.g root contains indices [0, n), subtree rooted at left child contains indices [0, n/2], subtree rooted at right child contains indices [n/2+1, n) etc…). To access the substring, you’d traverse the tree to the leaf nodes which contains the actual substring specified by the range of the node. After this, I was then told to implement a method to access a particular index in the string which was doing a tree traversal. As a follow up, I was told to implement a method to delete a substring given a range of values which was pretty difficult so I was given some hints on how to change some things to better support this operation, and I was halfway through implementing it when I ran out of time.
Reflection:
When I finished, I felt pretty good about my interviews. I thought that I was able to solve all problems and all interviewers seemed satisfied with my solutions. I felt great about my chances of getting an offer. Until a week later, I received the call from my recruiter saying that I didn’t get the offer. Of course, I was devestated as Google was my dream job and I was somewhat surprised that I was rejected. But after taking the time to think about everything and write this out, it makes sense why they may have rejected me, and there are things that I could’ve done better.
Advice:
Keep practicing and don’t give up! I honestly felt like giving up after getting rejected AGAIN from Google. It was even more dissappointing having many friends, family, Google engineers and recruiters on my side and letting them down. But after spending a few hours to get over it, I’ve become even more motivated to get in at some point in the future. I’m a firm believer than many of the best lessons in life are learned through failure. Some of my key takeaways from this experience:
- Make sure to ask clarifying questions . It is obvious that this is crucial for fully understanding the problem and getting the correct solution. Yet, not everyone does it (even myself when I know that I should do it). Practice doing this in mock interviews to make it second nature.
- Do plenty of mock interviews . If you become very anxious and your brain shuts down when you’re nervous like me, do lots of mock interviews with friends, family, or on pramp. Make an effort to highlight and improve your weaknesses.
- Challenge youself with difficult problems . Once you have a solid grasp of the fundamentals, challenge yourself with difficult problems. While many of you may disagree, my point of view is that it doesn’t hurt to be overprepared if you have the time. Because there is so much inconsistency and probability invovled with the interview process and the kind of problems you are asked, I’d rather be safe than sorry. I also find the most beneficial problems are the problems that challenge me intellectually.
- Don’t rely on memorizing solutions . I was trying to do this for a while, but it doesn’t always work especially if you’re like me and forget things when you’re nervous. It’s better to just work hard to understand things fundamentally and pick up on the patterns on how to solve different types of problems.
- Carefully look over your code and run test cases on small input and edge cases . This is crucial for finding bugs. Don’t just assume that everything is going to work. It’s annoying having to do it, but make sure to practice doing this in your mock interviews so that it becomes second nature.
I wish the best of luck to all of you on your interviews! Also, remember that there are many great companies out there besides the FAANG companies. Wherever you end up, you will learn and grow as a person and engineer so approach it with an open mind and make the best of the opportunity that you have :).