My Interview with Google

While not an original post by far, I’d like to share my experience interviewing with Google. Since Google is constantly changing their interview process, this was conducted in Spring 2019. This is a bit of a ramble so I’ll highlight key points as I go.

The Summoning

Ever since I interviewed for Google back in my college days for an internship, I get calls from them once or twice a year asking if I’m interested in applying. Sometimes I tell them yes, sometimes no, and sometimes “never call me again”. They still call. Unfortunately, this means I can’t help you get a call from their recruiters because I’ve been stuck on their radar for years, whether I want to be or not.

Key Point: If you don’t think you can get a job at Google yet, apply anyway and they will stay in touch with you as your experience starts to match what they need. It’s not creepy: it’s Google.

Anyway, one day I was checking my Gmail inbox and was inspired to go through my spam to see if the filters were too aggressive. Ironically, there was a recruiter email from Google asking to schedule a call. In their defense, it was being forwarded from my college email address (as per history above) so I guess they weren’t flagging themselves so much as my university.

I almost always agree to do a call, mostly because I one day hope to hear they’ve embraced fully remote work. I don’t think this will ever happen. Still, who knows how long I’ll be stuck on their recruiting radar?

During the call I get the usual spiel about what teams are in my area and which offices I can apply for, immigration questions, and when I’d like to interview. Normally, I’ll ask about working from home or flexible hours but this time I had another motive to interview: I was coaching people in technical interviews and figured putting myself in their place would be a good way to help them. See how altruistic I am by making the great sacrifice of interviewing for one of the top tech companies? My motives aside, I figured I’d get them to send me their list of study materials, I’d go over them with my mentees, do a phone screen, and share my notes.

Surprise! You get to skip the phone screen because your friends at Google recommended you. Ugh. I didn’t really want to do the full 6 hours of walking over algorithmic coals but fine Retrospectively, I think I need to find better hobbies than interviewing at tech companies.

Key Point: If you have former classmates or colleagues at Google, their recommendation will not only get you an interview but can also decide whether you get the job. 

“The Usual Spiel”

As mentioned above, recruiters tend to follow a script and Google is no exception. Below are the points covered:

  • Locations of new and existing offices in your area as well as questions about where you would like to work. Key Point: An interview anywhere for Google is good for any location at Google, including any country or continent.
  • A list of teams hiring in your area along with their current projects.
  • New company initiatives around benefits, diversity, etc.
  • What the interview process looks like:
    • (Usually) a phone screen
    • An on-site interview for 6 hours with 5 hours of technical interviews and 1 hour of lunch with a Googler
    • Judgement – tentative offer or rejection
    • Requests for references, preferably internal to Google but also external
    • Selection of a start date
    • Team rotations/team shopping: you spend 1 – 2 weeks on a team to decide whether you want to work with them or not
    • Team selection and assimilation into the Borg
  • Promises to send follow up emails and interview materials

Key Point: I was told after Spring 2019 there would be 4 technical interviews and 1 ‘soft skills’ interview. 

When and What

First Email: Study Materials

The first email sent after the call was to thank me for my interest and provide an impossible amount of material to review. Oh, but don’t worry, this is probably stuff that you already deal with day to day. Right. When was the last time I not only used but implemented a priority queue backed by a min/max heap? Never. This is the same deal with Facebook, Microsoft, and Amazon interviews so I didn’t worry about it too much. It’s just a matter of prioritizing topics against time.

For System Design, this is a great example of prioritization based on time: https://github.com/donnemartin/system-design-primer

How To Prioritize?

If I don’t have much time, I’ll jump right into practice problems and do 50/50 problems and reviewing concepts. If I have some time, I’ll review all data structures and algorithms first then do as many practice problems as possible. With extra time, I will review all operating systems and system design concepts. I almost always skip discrete math and the whole NP-complete business. This time around I had extra time so when I wasn’t doing problems I was reading through system design books.

Key Point: If you feel you cannot achieve “excellence” or “proficiency” in at least the data structures and algorithms concepts, I recommend requesting a follow up in 3 – 6 months to allow for more study time. There’s no harm in failing but if you definitely want the job this time around then set yourself up to be as successful as possible.

The Materials: Copy Pasted From The Email

PREPARING FOR YOUR ON-SITE INTERVIEW

This is a non-exhaustive list of topics that may or may not be covered during your interviews. Its intent is to guide your study and preparation.

INTERVIEW PREP BLOGS & VIDEOS

INTERVIEW APPROACH

  • The interviews focus on coding, data structures, algorithms, computer science theory, and systems design (systems design questions normally reserved for applicants with 5+ years of industry experience)

  • Likely additional topics include: hash tables, heaps, binary trees, linked lists, depth-first search, recursion (think CS 101 – concepts that everyone knows but doesn’t always quickly come-to-mind).More information on Algorithms

  • Many questions are open-ended and are deliberately underspecified to see how you engage the problem. Verbalize your thought process as you work to understand, approach, and solve the problem. Interviewers want to see which areas you find most important to the problem’s solution. Think about ways to improve the solution you’ll present. In many cases, the first answer that springs to mind will need refining. Verbalize your initial thoughts to the question. Ask clarifying questions if you don’t understand the problem or need more information. As a rule: efficient solution > brute force solution

  • For in-depth study – 3 highly recommended reads from Sr. Engineers: (1) “Programming Interviews Exposed: Secrets to Landing Your Next Job” (2) “Programming Pearls” and (3) “Cormen/Leiserson/Rivest/Stein: Introduction to Algorithms”

SAMPLE TOPICS

  • Coding: construct / traverse data structures, implement system routines, distill large data sets to single values, transform one data set to another

  • Algorithm Design / Analysis: big-O analysis, sorting and hashing, handling obscenely large amounts of data. Also see topics listed under ‘Coding’

  • System Design: features sets, interfaces, class hierarchies, designing a system under certain constraints, simplicity and robustness, trade-offs

  • Open-Ended Discussion: biggest challenges faced, best/worst designs seen, performance analysis and optimization, testing, ideas for improving existing product

HOW TO SUCCEED

  • We believe in collaboration and sharing ideas. Most importantly, you’ll need more information from the interviewer to analyze & answer the question to its full extent

  • If you don’t understand something or are stuck, please question your interviewer and ask for clarification and/or a hint

  • When asked to provide a solution, first define and frame the problem as you see it

  • If you need to assume something, verbally check it’s a correct assumption

  • Describe how you want to tackle solving each part of the question

  • Always let your interviewer know what you are thinking as they are just as interested in your thought process as the final solution

  • Finally, listen – don’t miss a hint if your interviewer is trying to assist you

TECHNICAL DOMAINS (understanding these concepts is necessary to succeed in a Google Interview)

  • Algorithm Complexity: Understand big-O complexity analysis and Big-O notations (aka – “the run time characteristic of an algorithm.”) Working through practice problems is key

  • Sorting: Know how to sort. Don’t do bubble-sort. Know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical

  • Hashtables: The single most important data structure. Be able to implement one using only arrays in your favorite language with time limitations

  • Trees: Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, and trie-trees. Know at least one type of balanced binary tree, whether it’s a red/black tree, a splay tree or an AVL tree, and know how it’s implemented. Understand tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder

  • Graphs: There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); know each representation and its pros & cons. Know the basic graph traversal algorithms: breadth-first search & depth-first search. Know their computational complexity, their tradeoffs, and how to implement them in real code. Time permitting, study fancier algorithms such as Dijkstra and A*.

  • Other Data Structures: Know as many other data structures and algorithms as possible. Start with the famous classes of NP-complete problems, such as traveling salesman and the knapsack problem. Must recognize them when an interviewer asks you them in disguise. Find out what NP-complete means

  • Mathematics: Some interviewers ask basic discrete math questions. At Google we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. Know the essentials of combinatorics and probability. Be familiar with n-choose-k problems and their ilk – the more the better

  • Operating Systems: Concepts to know: (1) processes, threads and concurrency issues. (2) locks, mutexes, semaphores, and monitors (3) deadlock & livelock and how to avoid them (4) resources processes needs, and thread needs, and how context switching works, and how it’s initiated by the OS and underlying hardware (5) scheduling (6) multi-core: the fundamentals of “modern” concurrency constructs

Second Email: Time and Place

For scheduling, you are going to have to take a day off work (if you are currently working). You are asked to provide 3+ days in the next 4 weeks when you can interview. You will get an email confirming the time as one of those days you selected. I usually see 9 am or 10 am start times with 3 pm or 4 pm end times. The email includes instructions on parking, time to arrive, where to arrive, who to ask for, etc. This will vary based on which office you’ve selected for your interview location but read the whole email. The location I went to had a very strange parking situation so I needed to show up 30 min early. Finally, upon confirmation of the date, you need to file a formal application with Google using one of their tools.

Key Point: Read the whole interview confirmation email.

Interview Day

Key Point: Bring what makes you comfortable. As below, I like having physical pen and paper to take notes during the interviews.

As they say in the email, wear what you are comfortable with. Bring whatever you think you might need. I recommend bringing a notebook and a pen. I like to write down the names of my interviewers, which team they worked on, how long they’ve worked at Google, and notes on the questions they asked. I also bring chocolate and Tylenol because interviews are stressful.

Why write down that information? One or more of your interviewers might be a future teammate. Also, if you are not extended an offer, you can keep the questions to understand where your gaps are. Finally, if all your interviewers have been at the company 2 years or less, maybe that’s something you want to ask your recruiter about – what happens to employees after 2 years?

Things you might not expect:

  • Interview rooms can be really hot, like “I hope they don’t notice how much I’m sweating” hot or cold enough to feel like you’re directly in the path of the industrial air conditioner
  • You’re not going to be in the same room all day so make sure you don’t bring so much stuff that you’ll be uncomfortable carrying it around from room to room
  • You’ll be waiting for up to 30 mins from the scheduled “start time” of your interview – bring something to read or do
  • You will be given the opportunity to code on a computer or whiteboard. You can choose what you’re most comfortable with at each interview.

Impressions and Amenities

DISCLAIMER: I have pre-existing negative feelings about large tech companies. Have your salt at the ready.

The good things about Google corporate offices are fairly well known: free food, gyms, nap nooks, laundry, commuting cars/buses, etc. I found all my interviewers easy to talk to. In past Google interview, there were a few “hard to deal with” interviewers and I was happy not repeating that experience. The amenities were clearly well kept and organized.

The negatives are similar to other large tech companies (Amazon, Facebook, and sometimes Microsoft). All these things are what I heard from my interviewers:

  • There are too many people in the offices so you need to come in earlier and earlier to find parking
  • You have to avoid the cafeterias during lunch time because of how crowded they are
  • Organizations are constantly being moved under new leaders and moved to new buildings, sometimes in other cities
  • The offices are being shifted around to support the high populations so often that you always get lost

A few additional things stood out. First, there was a nap nook. Nap nooks are meant as small rooms or enclosures where you could take a nap during work. I’m used to seeing them as very small rooms about the size of a walk-in closet with a light, maybe a recliner or a cot, and enough room for prayer mats. This is similar to what I encountered:

via-we-heart-it_rect540 alcove bed
Credit to http://concordgreen.blogspot.com/2010/12/in-praise-of-bed-alcoves.html

Kudos for making the decor look, ah, “homey” but this makes me just a little bit uncomfortable. Can you imagine sitting next to your manager on that couch for a quick chat? Ew.

The second thing that stood out was how one interviewer described the difference between this location and Mountain View.

People here are a lot more interested in work-life balance and family rather than getting work done quickly.

I see. I guess it’s good that I’m not applying to work in Mountain View. Or maybe I want to burn out like a supernova: a high energy, crazy-bright star, with a short life on its way to complete destruction. But a rich supernova.

Coding Questions

As a friendly reminder, our interview questions are confidential, so please keep things under wraps.

~Google

I won’t tell you the questions but I will share the areas you would need to study to answer them.

Question 1: Card Game

  • Object-oriented design
  • Multi-dimensional arrays
  • Randomness
  • Multi-threaded access to shared objects (I used the word “semaphore” at some point)

Question 2: Merge K Lists

  • Greedy algorithms
  • The merge k lists problem – this wasn’t the question but I really kicked myself for skipping it during my practice after this interview

Question 3: Empire Building Board Game

  • Binary trees
  • Graph search
  • Linked Lists vs. Arrays

Question 4: I Heard You Like Trees

Question 5: Design a Cache

  • This was actually the question

The Result

As of writing this post, I do not have the result of the interview and I suspect I won’t for another few weeks. Google is infamous for long deliberation on candidates. I’ll update this post with the result when it makes it to me.

System Design Interviews

As I network through tech I frequently hear newcomers ask how to answer system design questions. I’ll try to clear that up in this post.

Why am I being asked to design a parking lot?

If you’re comfortable writing code and work on multi-component projects, then you might be familiar with maximizing reuse without high coupling. In an interview, they will test this with an object oriented design questions. In a service-oriented world, we are now being asked to do this with systems.

These concepts are inconsistently taught across all programs. Unlike a for loop, interviewers can’t always expect a candidate to be familiar with systems and services. Unfortunately, the interviewers are given a checklist and if it contains system design, they ask it. More bad news: the recruiters aren’t told what’s on the list. As a result, you and your interviewer have different ideas about what’s going to be asked.

How To Learn This

Question and Answer Format

Question

Questions will be phrased as: “design a system to XYZ”, “design a pre-existing software system”, “draw the architecture for XYZ”. Examples:

  • Existing software: Uber, Lyft, Facebook Messenger, Amazon retail website, Google Search, DNS, Expedia, Docker, GitHub, WordPress, any website you can think of.
  • Interview problems: Parking garage, generic search engine, inventory management system, hotel guest management system, log aggregation

Anything can come up here depending on how prepared or creative the interviewer is.

Boxes and Lines

The answer is going to be boxes and lines.

Boxes_and_Lines

Approaching the Question

Clarifying Questions and Requirements

If you’ve done any preparation or any interviews, you will know you need to ask clarifying questions and get the requirements. Treat your unimplemented solution as a black box and try to describe the inputs and the outputs. Take Twitter for example:

  • Are tweets text only?
  • How will customers get data out of the system? Browser, phone, REST API?
  • Can a customer send one tweet at a time or many?
  • Do users have accounts or is this anonymous?
  • Is user following enabled?
  • Are there multiple feeds or one giant aggregated feed of tweets?

You might be thinking “Do you even know how Twitter works?” If you are, good. You need to make sure you and the interviewer are on the same page. You can’t come up with a design that has every current Twitter feature so make sure to scope it down to a few specific features. Saying “I’m going to implement user accounts, tweeting text only, and retrieving messages without the follower system as my first round” is extremely helpful. The interviewer will know that you are aware that there are more features and are choosing to defer than rather than forgetting them. This also makes the problem easier. If you don’t specify which aspects you are implementing, you and your interviewer will have different ideas about a good answer.

Note: These interviews are 45 to 60 min. It’s better to start small and then discuss enlarging the scope with the interviewer than the other way around.

Always identify the data.

The data tells you a lot about the design. What data is being sent? What data is being stored? Does the data need to be sorted? How quickly does the data need to be available? This provides another way to get requirements. Example:

  • How will data be searched? Maybe we start with hashtag search only.
  • Can anyone see all tweets or are some tweets restricted viewing? We can start with all public.
  • When we search for tweets, do we return all of them that match or only the top 100 most recent? Let’s do all of them at first for simplicity.

The Boxes

What are the boxes? Don’t be thrifty on the boxes. Boxes are more easily grouped than separated. You can do a “discovery” style and follow a single piece of data through the system.

For example, a customer hits the “Tweet” button from their browser. This goes to some server, the TweetManager. The tweet needs to be stored and show up in the user’s page and the global feed (as per requirements of no custom feeds). The tweet also needs to be searched later by hashtags (as per requirement of hashtag search only). This tells us we need a place to store the whole tweet, TweetStore. We might also need to store user information that can reference their tweets, UserStore and maybe UserManager. Somewhere else, we need to support hashtag searches, SearchTagManager and/or HashTagStore. Finally, we can throw in notifications for fun and have  NotificationManager. Here’s what that looks like:

Twitlines

  1. The user tweets and the tweet is sent to the TweetManager (here we assume that the user is logged in and is who their cookies or headers say they are).
  2. The TweetManager stores the Tweet in the TweetStore. At this point it is linked to the user that posted it.
  3. The TweetManager sends the hashtags in the tweet along with a reference to the tweet in the TweetStore.
  4. The HashtagManager adds the tweet reference to the list of all tweets related to that hashtag in the hashtag store (this creates a link to the tweet store).
  5. The TweetManager sends a completed message to the notifier which then shows everyone logged in that a new tweet has been posted.

We also have Login and ‘A’ which is searching by hashtag.

Note: This is a simplified example. I would strongly discourage using this answer in an interview because it doesn’t scale, has high latency, and will likely result in data inconsistency.

Hey, Where Are My Tables?

You may be tempted to say one of your boxes will be a SQL database and start describing your schema in detail. Don’t. Don’t do this unless the interviewer asks you to go into details. If you focus on details, you won’t have time to answer the whole question. However, having them at the ready doesn’t hurt in follow up questions.

Grouping

It turns out I have 3 storage boxes and 3 service boxes. Do they all need to be separate or can some be together? There are many driving factors for doing this:

  • Minimize coupling: you should minimize lines between two boxes for a single “trip” through the system
  • Follow the K.I.S.S. rule: you should not have to fan out to turn one tweet into 5 calls to other boxes
  • Asynchronous vs. Synchronous: know which lines need to be blocking and which can be done asynchronously. In some systems, the different types of calls go to different boxes (not always).

A simple grouping might be all the logic in one box and all the data in another:

Group

Scalability

Scalability is challenging. In these questions, you can either predict how to scale the system or you can do this exercise repeatedly:

  1. A significant political event is happening. A few key individuals are sending out tweets through the event. Everyone on the planet is trying to search for tweets with the event hashtag at the same time.
  2. Identify what will break first and how it will break. If it breaks, does it break only the overloaded part of the system or other parts too? In this case, the hashtag manager can actually be scaled to tolerate the number of requests. However, the data store (no matter what store you use) will be in trouble.
  3. Discuss or draw a way to solve this. The most common answers to this are asynchronous communication with queuesreplicas, and some form of sharding.

Often you need to do one or two examples to show you understand what scaling is and how to alter a system to support more traffic.

New Features

You’re feeling great because you drew boxes and lines. You came up with your own scaling answers before the interviewer asked. Then the interviewer throws a giant wrench into your answer: I want you to implement followers, identity verification, and malicious account detection.

If you only have 5 minutes left, feel free to verbally explain while waving your hands at your diagram. Throw a quick machine learning trained fraud box and a service that requests identity verification through a third party vendor. Usually when these features are requested near the end of the interview it isn’t about implementing them but about discussing how you can grow your solution. If you can’t discuss the solution, it might look like you copied it from a book.

Follow Up Questions

  • Why is this data here and who can access it?
  • How long does it take to complete one customer request?
  • Why are these two components separate or together?
  • Can you make this more generic or into a platform? How would you covert this into a Software as a Service product?

I Did All The Right Things And All I Got Was This T-Shirt

I’ve had too many interviews where the interviewer was stubborn, critical, condescending, dismissive, and basically an asshole. It’s almost impossible to succeed in these cases unless you fit their mold perfectly and even then it’s not a guarantee. Here are some signs that it might not be your answer that’s at fault:

  • Your interviewer is flipping between high level criteria and specific technologies (i.e. we need a customer service but please use AWS lambda)
  • Your interviewer is telling you where to draw your lines without explaining why
  • Your interviewer is repeatedly cutting you off when you try to ask clarifying questions and replies with “just implement it the way it is”
  • Your interviewer says “uhhh” a lot and doesn’t seem to know where he or she is going with the question
  • Your interviewer changes the question halfway through: did I say architecture? I meant library
  • You were incorrectly leveled by your recruiter (surprise!) and you feel deeply in over your head.

Leveling?

All companies put their applicants into buckets that are highly variable but sort of follow this structure:

  • 0 to 2 years of experience: entry level
  • 2 to 5 years of experience: mid level
  • 5+ years of experience: senior level
  • 12+ years of experience: principle or CTO level

Highly variable by company, geographic area, job role, and how the recruiter feels that day.

I think it’s unreasonable to ask an entry level applicant a design question because they may or may not have encountered them. If an applicant is on a border of experience levels, they may ask this question to see which bucket they fit in. Finally, as above, recruiters and interviewers don’t talk.

In Conclusion

Just don’t draw a single box with a SQL database schema as your answer. Good luck!