The Google Resume (15 page)

Develop a Rule or Equation

When you get a problem, see if you can work through examples. Try to formulate any rules or equations that you discover along the way as specifically as possible.

• Example:
  You have 100 lockers. Someone starts off by opening every locker. Then they close every second locker. Then they open every fourth,
  etc.
  At the end of 100 operations, which lockers will be open?
  
• Rule #1: The
  x
  th locker is toggled on the
  y
  th operation if
  x
  is divisible by
  y.
  
• Rule #2: The
  x
  th locker is open at the end of 100 operations if it has an odd number of factors.
  
• Solution: If you play with some examples, you’ll find that almost all numbers have an even number of factors. This is because if a number
  n
  is divisible by
  x
  , it’s also divisible by n/x (sort of like the complement). For example, since 12 is divisible by 3, it must also be divisible by 12/3 (or 4). Thus, the list of factors that a number has can almost always be “paired off.” Factors (35) = {1 and 12, 2 and 6, 3 and 4}. The only way that you could wind up with an odd number of factors is if a number is a perfect square: Factors (36) = {1 and 36, 2 and 18, 3 and 12, 4 and 9, 6 and 6}. Therefore, the number of open lockers equals the number of perfect squares. There are 10 perfect squares less than 100: 1
  1
  , 2
  2
  , . . . , 10
  10
  .
  

Simplify the problem

Sometimes simplifying a problem or solving the problem for a specific case can help illustrate a general trend.

• Example:
  A bunch of people are on an island and, one night, some are given magical hats. These hats are magical because they can’t see their own hat, but they can see everyone else’s. To remove a hat, one must take a swim at exactly midnight (and there are severe penalties to taking a hatless swim). How long does it take the people to remove the hats?
  Note:
  They know that at least one person has a hat, but they don’t know how many.
  
• Simplification:
  What if only one person had a hat?
  In this case, the hat wearer would see no one else with a hat, and know it must be him. He would go for a midnight swim.
  What two people (let’s call them A and B) had hats?
  A and B know that there could be either one or two hats out there, but don’t know which. They know, however, if there’s only one hat, it’ll be removed at midnight. When day 2 comes, they must conclude that there are two hats. They know they have the second one, and they both take a swim at midnight.
  What if three people have hats?
  A, B, and C recognize that there are two possibilities: two hats and three hats. When two nights pass and everyone still has a hat, they all know that there are three hats and they all go for a swim.
  
• Solution: Extending this out, we can see that if there are
  c
  hats, it takes
  c
  nights for them all to be removed. All hats are removed simultaneously. From the very first day, each person knows that there are only two possibilities:
  c
  hats and (
  c − 1
  ) hats. If there were (
  c − 1
  ) hats, they would be removed on the (
  c − 1
  )th night. The hats are not removed, and so all the hat wearers conclude that there are
  c
  th hats on the night.
  

Examples

• You have 10 bottles of pills. Nine bottles are filled with pills of 1.0 grams, but one has pills of 1.1 grams. With only one use of a scale, how would you figure out which bottle has the heavier pills?
  Note:
  The scale gives an exact measurement.
  
• Five coworkers decide that they’d like to compute their average salary. How can they do this without telling anyone their salary?
  
• There is a building of 100 floors. If an egg drops from the
  n
  th floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given two eggs. Would you find
  n
  while minimizing the total number of drops?
  
• You have a three-gallon jug and a five-gallon jug and an unlimited supply of water. How do you use these to get exactly four gallons of water?
  
• There is an 8 × 8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominoes, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?
  

Answering the Tough Questions

Sometimes, the toughest questions are the ones we already know and don’t want to answer. Maybe it’s a layoff, maybe it’s a pattern of job hopping, or maybe it’s a sudden career switch. No matter how much we don’t want to get these questions, we must be prepared for them. Practice your story for this, both to yourself out loud and to your friends. Does it appear honest and credible? Are you prepared for any follow-up questions that your interviewer might ask?

The biggest mistake you can make in this question is brushing off the question. Your interviewer may not press you for your answer, but she won’t be impressed.

Whatever you’re trying to hide, be honest and don’t assign too much blame away. Admit your mistake, and focus on what you’ve learned and how you’ve grown since then. This sort of answer will show maturity and honesty, while leaving your response on an honest note.

Layoffs

If you were let go during a round of layoffs, you’re in a better position than many. However, even these routine layoffs might raise a red flag: some people are usually kept—why weren’t you?

The important thing is to stress evidence that you were performing well:

• “The recession hit my company really hard. I was able to survive three rounds of layoffs, but the fourth one included me, too. Frankly, I can’t really blame my company: my role is about client service, and there weren’t many clients left.”
  
• “My firm laid off about 25 percent of its workforce, and it hit the mobile division the hardest. My manager fought hard for me, but given the new direction of the company, it just didn’t make sense.”
  

Being Fired

Interviewers know that there are two sides of the story. If you claim it’s not your fault that you got fired, they’ll just dig elsewhere and discover the truth eventually. It’s better if it comes from you.

Accept the blame, and show what you’ve learned from it:

• “My company had expectations of working upwards of 70 hours per week. I had a new baby at home, and I couldn’t do more than 40 or 50 hours. I held on longer than I should have, but it taught me a valuable lesson about setting mutual expectations up front.”
  
• “I was fired because I was no longer very productive. The truth was that I wasn’t excited about the job, which made me lose focus at work. The bright side is that it caused me to shift my career toward my true passion—technology—and I’m really excited about the new direction for my career.”
  

Offer a crisp and concise answer. Don’t play the blame game. Don’t bad-mouth your former employer. And don’t lie.

Unemployment

If you’ve been unemployed for an extended period of time, interviewers may want to know what you have done during your time off. “Looking for a job” is probably not a complete answer. How many hours a day could you have really spent doing that?

The best answer involves accomplishing something or brushing up on new skills. I recall one man I interviewed who had a seven-year gap (!) in his career. He explained to me that he had taken time off to raise his two young children. Once they started preschool, he spent his day writing a few games and small pieces of software. This candidate spun what was initially a red flag—an extended career gap—into a big plus. Many of us write software for pay, but writing software for fun shows a unique passion for the field. He was hired.

If you’re currently unemployed, find something to do that’s productive. Can you help out your friend’s start-up? Can you take some classes at a community college? Unemployment is an excellent time to beef up your résumé.

Your Questions Answered

Barrier to Entry

It’s a Numbers Game

The Great Unknown

Additional Resources

Please visit
www.careercup.com
for additional interview questions and resources.

If you’re applying for a software development position, you’ve got a special set of skills to prepare. Yes, you’ll be asked to code. No, you don’t get a computer—just a whiteboard, or sometimes just a sheet of paper. Whiteboard and interviewing coding requires a special set of skills. Even the best coders can get nailed on coding questions.

A software development interview consists of about 15 minutes of discussion, which usually includes some questions about your résumé and/or offers you a chance to ask the interviewer questions. The bulk of the interview is spent on coding and algorithm questions.

Coding questions can be very quick, but will often take up the full interview time. You’re not expected to be a flawless coder. Most questions are tricky enough that even the best candidates make a few mistakes.

How They Differ: Microsoft, Google, Amazon, and Apple

I can’t tell you what each company will ask—after all, each interviewer basically does whatever he or she wants. However, certain companies have trends.

• Google
  tends to emphasize questions on scalability more than other companies (for instance, “Design a web crawler”). Questions on bit manipulation are also quite common.
  
• Amazon
  loves object-oriented design questions—I mean really
  loves
  , in a high-school-crush-you-just-can’t-get-over sort of way. They just can’t stop asking them. If you’re going to interview at Amazon, make sure you study these problems. And, since Amazon is a web-based company, you’ll also want to prepare for scalability questions.
  
• Microsoft
  is all over the map, which is to be expected since it has a pretty diverse set of projects. Its interviewers tend to ask more questions about C and C++. If you don’t list the languages on your résumé, you have nothing to fear. However, if you do list these languages, you’ll want to make sure that you’re comfortable coding in them. Additionally, Microsoft tends to emphasize testing and design skills more in developers than other companies do, so be prepared for these questions.
  
• Apple
  wants to know that you’re as die-hard an Apple fan as the other people in the cult—I mean, company. Make sure you understand Apple’s products, especially those of the team you are interviewing with. What would you improve about the product? Remember that Apple has a lot of smart people who haven’t yet done what you’re suggesting. Think about why they haven’t.
  

How to Prepare

When it comes to practicing interview questions, quality matters more than quantity. There are literally thousands of sample interview questions online for companies like Google, Microsoft, and Amazon—don’t try to memorize the answers. It’s impossible and won’t help you anyway!

The Five-Step Approach to Effective Preparation

Take your time solving problems, and try the following approach in practicing questions:

You can find thousands of coding interview questions on
CareerCup.com
that candidates have gotten from companies like Google, Microsoft, Amazon, and other major tech companies.

What If I Hear a Question I Know?

In offering thousands of sample interview questions on
CareerCup.com
and in my other book,
Cracking the Coding Interview
, my goal is not to help you memorize questions and then regurgitate answers in an interview. Interviewers want to see how you approach problems, so spitting out pre-prepared solutions won’t do you much good.

If you get a question you’ve heard before, tell your interviewer! It’s not only the
right
thing to do; it’s also the smart thing. If you try to hide it and pretend to fumble through the answer, your interviewer will probably be suspicious—and lying (or hiding the truth) is perhaps the worst thing you could do in an interview.

However, if you are honest and say that you’ve heard the question before, you’ll win major bonus points. Interviewers care about honesty, even if there’s usually no way to directly test it.

“Must Know” Topics

Most interviewers won’t ask you about specific algorithms for binary tree balancing or other complex algorithms. Frankly, they probably don’t remember these algorithms either. (Yes, that means you can put down the CLRS algorithms book.)

You’re usually expected to know only the basics. Here’s a list of the absolute must-know topics:

This is not, of course, an all-inclusive list. Questions may be asked on areas outside of these topics. This is merely a “must know” list.

For each of the topics, make sure you understand how to implement/use them, and (where applicable) the space and time complexity.

Practice implementing the data structures and algorithms. You might be asked to implement them directly, or you might be asked to implement a modification of them. Either way, the more comfortable you are with the implementations, the better.

Memory Usage

As you’re reviewing data structures, remember to practice computing the memory usage of a data structure or an algorithm. Your interviewer might directly ask you much memory something takes, or you might need to compute this yourself if your problem involves large amounts of data.

• Data structures.
  Don’t forget to include the pointers to other data. For example, a doubly linked list that holds 1,000 integers will often use about 12KB of memory (4 bytes for the data, 4 bytes for the previous pointer, and 4 bytes for the next pointer). This means that making a singly linked list into a doubly linked list can dramatically increase memory usage.
  
• Algorithms.
  A recursive algorithm often takes up dramatically more space than an iterative algorithm. Consider, for example, an algorithm to compute the
  j
  th to last element of a singly linked list. An approach that uses an array to sort each element may be no better than a recursive algorithm—both use O(n) memory! (The best solution involves using two pointers, where one starts off
  j
  spaces ahead.)
  

Many candidates think of their algorithms on only one dimension—time—but it’s important to consider the space complexity as well. We must often make a trade-off between time and space, and sometimes, we
do
sacrifice time efficiency to reduce memory usage.

Coding Questions

Interviews are supposed to be difficult. If you don’t get every—or any—answer immediately, that’s OK! In fact, in my experience, maybe only 10 people out of the 150+ that I’ve interviewed have gotten the algorithm right instantly, and all but one of them made later mistakes on the coding.

So when you get a hard question, don’t panic. Just start talking aloud about how you would solve it.

And, remember: you’re not done until the interviewer says that you’re done! What I mean here is that when you come up with an algorithm, start thinking about the problems accompanying it. When you write code, start trying to find bugs. If you’re anything like the other 110 candidates that I’ve interviewed, you probably made some mistakes.

Let’s go into each of these in more detail.

Step 1: Ask Questions

Technical problems are more ambiguous than they might appear, so make sure to ask questions to resolve anything that might be unclear or ambiguous. You may eventually wind up with a very different—or much easier—problem than you had initially thought. In fact, many interviewers (especially at Microsoft) will specifically test to see if you ask good questions.

Good questions might be things like: What are the data types? How much data is there? What assumptions do you need to solve the problem? Who is the user?

Example: “Design an Algorithm to Sort a List”

• Question:
  What sort of list? An array? A linked list?
  

  Answer:
  An array.
  

• Question:
  What does the array hold? Numbers? Characters? Strings?
  

  Answer:
  Numbers.
  

• Question:
  And are the numbers integers?
  

  Answer:
  Yes.
  

• Question:
  Where did the numbers come from? Are they IDs? Values of something?
  

  Answer:
  They are the ages of customers.
  

• Question:
  And how many customers are there?
  

  Answer:
  About a million.
  

We now have a pretty different problem: sort an array containing a million integers between 0 and 130 (I don’t think people are living past age 130, are they?). How do we solve this? Just create an array with 130 elements and count the number of ages at each value.

Step 2: Design an Algorithm

Designing an algorithm can be tough, but our five approaches to algorithms can help you out. While you’re designing your algorithm, don’t forget to think about:

• What are the space and time complexities?
  
• What happens if there is a lot of data?
  
• Does your design cause other issues? (i.e., if you’re creating a modified version of a binary search tree, did your design impact the time for insert/find/delete?)
  
• If there are other issues, did you make the right trade-offs?
  
• If they gave you specific data (e.g., mentioned that the data is ages, or in sorted order), have you leveraged that information? There’s probably a reason that you’re given it.
  

Step 3: Pseudo-Code

Writing pseudo-code first can help you outline your thoughts clearly and reduce the number of mistakes you commit. But make sure to tell your interviewer that you’re writing pseudo-code first and that you’ll follow it up with “real” code. Many candidates will write pseudo-code in order to “escape” writing real code, and you certainly don’t want to be confused with those candidates.

Step 4: Code

You don’t need to rush through your code; in fact, this will most likely hurt you. Just go at a nice, slow methodical pace and remember this advice:

• Use data structures generously.
  Where relevant, use a good data structure or define your own. For example, if you’re asked a problem involving finding the minimum age for a group of people, consider defining a data structure to represent a Person. This shows your interviewer that you care about good object-oriented design.
  
• Don’t crowd your code.
  Many candidates will start writing their code in the middle of the whiteboard. This is fine for the first few lines. But whiteboards aren’t that big. Pretty soon they wind up with arrows all over the board directing the interviewer to the next line of code. We’d never hold it against a candidate, but it’s still distracting for everyone.
  

Step 5: Test

Yes, you need to test your code! Consider testing for:

• Extreme cases: 0, negative, null, maximums,
  etc.
  
• User error: What happens if the user passes in null or a negative value?
  
• General cases: Test the normal case.
  

If the algorithm is complicated or highly numerical (bit shifting, arithmetic, etc.), consider testing while you’re writing the code rather than just at the end.

When you find a mistake (which you will), relax. Almost no one writes bug-free code; what’s important is how you react to it. Point out the mistake, and carefully analyze why the bug is occurring. Is it really just when you pass in 0, or does it happen in other cases, too?

I remember one candidate who was implementing a binary search tree method getSize(). When he realized that his method returned “3” on a two-element tree, he quickly appended a “+ 1” to the return statement. Maybe he thought I wouldn’t notice. A few moments later, he discovered his algorithm branched left in one case instead of right. So he flipped the left and right. Pretty soon, his code was so littered with little changes that it was unrecognizable; he had to start over from scratch.