Tech Interviewing Decoded – A Day at Google

I haven’t been in many technical interviews, so when I got an email from Google asking if I’d like to sign up for a seminar they were hosting about tech interviews, I jumped at the chance!

The email was sent out to all CS and Engineering students at a few different Bay Area schools. Out of all respondents, they chose about 200 students to take part in the seminar. I was lucky enough to be one of them.

On a Friday morning, I drove out to the new Google campus – Tech Corners in Sunnyvale. There was a surprising amount of “Expectant Mother Parking”, but I was able to find a spot. There were six, brand new, shiny buildings on the campus, each with their respective number emblazoned on the side.

I walked to the meeting building where they allowed us all to register and gave us a lanyard with a nifty name tag.

TechInterview

The first thing on the schedule was a demonstration of an interview. Two Google employees ran trough a technical interview involving writing code to solve a given problem on a whiteboard.

They gave great advice on how to attack this kind of problem:

  • Vocalize your thought process. Even if you’re stuck and just searching for a possible solution, say out loud what you’re thinking of. It will give the interviewer some indication of how you approach problems.
  • Ask lots of clarifying questions. For example, if you’re given a problem involving a set of data, ask if you need to worry about sets so large they could overflow a structure.
  • Give an example case and solution to make sure you understand the question.
  • Create an algorithm that works, then worry about making it efficient. Even if the algorithm you create solves the problem in exponential time, it’s better than not solving the problem at all.
  • Show your knowledge of Object-Oriented concepts. If the problem lends itself to it, feel free to design a class that helps you solve the problem. Referencing design patterns can also help!

For their example problem, the interviewee was given this:

For a random grid of sequential integers, find the longest sequence of adjacent, sequential numbers.

Now, before even touching the whiteboard, the interviewee asked a few clarifying questions:

  1. Can I assume the grid is square? Yes.
  2. Will a simple two-dimensional array of int types fit the data? For now, let’s assume yes.

Next, the interviewee drew up an example on the board:

example

He asked, “So, in this scenario, my algorithm would return 3 because the longest sequence of adjacent numbers is ‘7, 8, 9’?” The interviewer confirmed this.

Great! So with just a couple questions and a quick example case, you understand the problem much better than before and you’re sure that you and the interviewer are on the same page.

Now, it was time to begin writing some code on the whiteboard. He started with this algorithm:

[snippet id=”5″]

The entire time he was writing this code, he was explaining why he was doing each step. Often, he would get down a few lines, then realize he needed an extra variable at the top. That’s fine! That’s how most programmers operate. If you forget something, don’t sweat it, just acknowledge you forgot something and add it in.

Another important thing is that he broke out most of the work from the main loop. It doesn’t all have to be in one function! It’s good practice to keep functions short and to the point, so breaking out the actual calculation was a good move and made things more legible. Often, if the interviewer can see you know where the algorithm is going, they’ll cut you some slack on the tedious writing. This code is incomplete – there’s no base case for the recursion, and all the directions aren’t implemented, but the guy knew how he was going to finish up and was able to explain it.

When he finished this algorithm, the interviewer asked, “Okay, it looks like this would work. What’s it’s runtime efficiency for an n by n grid?”

Instead of just blurting an answer, the interviewee talked through it… “Well, it checks each node in the grid once, so that’s n times n operations right there… then each check could potentially check n adjacent nodes… so the final worst-case time-complexity would be O(n3). So, this algorithm might be okay for small data sets, but would get extremely inefficient for large data sets. Hmmm…. it seems like we could improve this algorithm. We should only need to visit every node once… do we¬† have time to refactor this?”

The interviewer said that would be fine, and he went about writing a new algorithm, again, explaining each step along the way:

[snippet id=”6″]

Now, this algorithm falls back onto a class to represent each coordinate in the grid sequentially. So, basically, it’s creating an array of classes of size n. Starting at 1, coordinates[i] represents the coordinates in the grid where the value is i. The basic idea is that the programmer can then check if the next object in the array has coordinates that differ by 1, indicating it’s adjacent in the grid. Notice that again he abstracted away the hard work – this time he didn’t even write the code that does comparison! With this style of algorithm, you have to initially load the numbers into the coordinate array, then go through that array checking for the longest sequence, so it will run in linear time instead of cubic!

Neither of the algorithms he wrote would work in all cases, but that was acknowledged. He said things like, “I’ll do a test case later to check for off-by-one errors and the like”. That way, the interviewer knew he was thinking about those issues, but just wanted to get the algorithm down first.

That was all for the technical interview demonstration, but there was a short Q&A session afterwards. I think the best question was, “what do you do if you are completely stuck and don’t know how to approach a problem.”

One of the engineers said, “Just keep thinking aloud. If you talk with the interviewer about what you’re thinking about, they will be more likely to steer you in the right direction. Also, if they give you a hint… take it! They’re not trying to trick you.”

After the interview, there was a panel discussion with some more engineers fielding questions about how to get a job at Google or a tech job in general. There were many questions, but the main points I found useful were as follows:

  • Study for your interviews! One of the engineers didn’t study, was rejected, then tried again at a later time (prepared), and got the position. Don’t just go through books looking at algorithms you might be asked about. Actually write code on a whiteboard! The physical act of doing it is a really important part of practicing.
  • They love seeing that you’ve written technical papers and/or have open source experience. Having something other than your degree to show you’re passionate in CS is really important.
  • People skills are paramount. Being able to express your ideas to other engineers and delegate work effectively makes you a very desirable candidate. This goes back to the whiteboard interview – if you can express your ideas clearly, it will help in the end!
  • Tell people what you want. If you’re interested in a software development position and they have you working systems administration, speak up! Let your employer know what you want to do, and more often than not they’ll be willing to help you out. A motivated employee is a productive employee.
  • Tech companies love generalists. If you can write high quality programs, understand networking tasks, have experience with several different operating systems and tools, and are able to adapt and solve problems outside the exact scope of your job, that means you are a valuable employee.

There were more discussions and panel talks, but they were more focused on resume preparation and GPA-related stuff. Essentially, put your GPA on your resume if you’re sending it to Google.

That’s about it for my day at Google! Let me know what you think about the whiteboard interview process or other tech interviewing situations in the comments section below!

Leave a Reply