The Google Resume (16 page)

This approach, which I’ve seen far too many times, seems somewhat like throwing Scrabble letters across the room, hoping they’ll spell a word when they land. Sure, it
could
happen—but it still wouldn’t make you a good speller.

Algorithm Questions: Five Ways to Create an Algorithm

There’s no surefire approach to solving a tricky algorithm problem, but the following approaches can be useful. Keep in mind that the more problems you practice, the easier it will be to identify which approach to use.

Also, remember that the five approaches can be “mixed and matched.” That is, once you’ve applied “Simplify and Generalize,” you may want to implement Pattern Matching next.

Approach 1: Examplify

We start with Examplify, since it’s probably the most well-known (though not by name). Examplify simply means to write out specific examples of the problem and see if you can figure out a general rule.

Example:
Given a time, calculate the angle between the hour and minute hands on a clock.

Start with an example like 3:27. We can draw a picture of a clock by selecting where the 3-hour hand is and where the 27-minute hand is. Note that the hour hand moves continuously, not in a discrete jump when the time changes.

By playing around with examples, we can develop a rule:

• Minute angle (from 12 o’clock): 360 × minutes / 60
  
• Hour angle (from 12 o’clock): 360 × (hour % 12) / 12 + 360 × (minutes / 60) × (1 / 12)
  
• Angle between hour and minute: (hour angle − minute angle) % 360
  

By simple arithmetic, this reduces to 30 × hours – 5.5 × minutes.

Approach 2: Pattern Matching

Pattern matching means to relate a problem to similar ones, and figure out if you can modify the solution to solve the new problem. This is one reason why practicing lots of problems is important; the more problems you do, the better you get.

Example:
A sorted array has been rotated so that the elements might appear in the order 3 4 5 6 7 1 2. How would you find the minimum element?

This question is most similar to the following two well-known problems:

• Find the minimum element in an unsorted array.
  
• Find a specific element in an array (e.g., binary search).
  

Finding the minimum element in an unsorted array isn’t a particularly interesting algorithm (you could just iterate through all the elements), nor does it use the information provided (that the array is sorted). It’s unlikely to be useful here.

However, binary search is very applicable. You know that the array is sorted but rotated. So it must proceed in an increasing order, then reset and increase again. The minimum element is the “reset” point.

If you compare the first and middle elements (3 and 6), you know that the range is still increasing. This means that the reset point must be after the 6 (or 3 is the minimum element and the array was never rotated). We can continue to apply the lessons from binary search to pinpoint this reset point, by looking for ranges where LEFT > RIGHT. That is, for a particular point, if LEFT < RIGHT, then the range does not contain the reset. If LEFT > RIGHT, then it does.

Approach 3: Simplify and Generalize

In Simplify and Generalize, we change constraints (data type, size, etc.) to simplify the problem, and then try to solve the simplified problem. Once you have an algorithm for the “simplified” problem, you can generalize the problem back to its original form. Can you apply the new lessons?

Example:
A ransom note can be formed by cutting words out of a magazine to form a new sentence. How would you figure out if a ransom note (string) can be formed from a given magazine (string)?

We can simplify the problem as follows: instead of solving the problem with words, solve it with characters. That is, imagine we are cutting characters out of a magazine to form a ransom note.

We can solve the simplified ransom note problem with characters by simply creating an array and counting the characters. Each spot in the array corresponds to one letter. First, we count the number of times each character in the ransom note appears, and then we go through the magazine to see if we have all of those characters.

When we generalize the algorithm, we do a very similar thing. This time, rather than creating an array with character counts, we create a hash table. Each word maps to the number of times the word appears.

Approach 4: Base Case and Build

Base Case and Build suggests that we solve the algorithm first for a base case (e.g., just one element). Then, try to solve it for elements one and two, assuming that you have the answer for element one. Then, try to solve it for elements one, two, and three, assuming that you have the answer to elements one and two.

You will notice that Base Case and Build algorithms often lead to natural recursive algorithms.

Example:
Design an algorithm to print all permutations of a string. For simplicity, assume all characters are unique.

Consider the following string: abcdefg

• Case “a” ⇒ {a}
  
• Case “ab” ⇒ {ab, ba}
  
• Case “abc” ⇒ ?
  

This is the first “interesting” case. If we had the answer to P(“ab”), how could we generate P(“abc”)? Well, the additional letter is “c,” so we can just stick c in at every possible point. That is:

• merge(c, ab) ⇒ cab, acb, abc
  
• merge(c, ba) ⇒ cba, bca, bac
  

We can use a recursive algorithm to solve this problem. First, generate all permutations of a string by “chopping off” the last character and generating all permutations of s[1 . . . n-1]. Then, insert s[n] into every location of the string.

Approach 5: Data Structure Brainstorm

The Data Structure Brainstorm approach admittedly feels somewhat hacky, but it often works. In this approach, we simply run through a list of data structures and try to apply each one. This approach works because many algorithms are quite straightforward once we find the right data structure.

Example:
Numbers are randomly generated and stored into an (expanding) array. How would you keep track of the median?

Data Structure Brainstorm:

• Linked list? Probably not—linked lists tend not to do very well with accessing and sorting numbers.
  
• Array? Maybe, but you already have an array. Could you somehow keep the elements sorted? That’s probably expensive. Let’s hold off on this and return to it if it’s needed.
  
• Binary tree? This is possible, since binary trees do fairly well with ordering. In fact, if the binary search tree is perfectly balanced, the top might be the median. But, be careful—if there’s an even number of elements, the median is actually the average of the middle two elements. The middle two elements can’t both be at the top. This is probably a workable algorithm, but let’s come back to it.
  
• Heap? A heap is really good at basic ordering and keeping track of max and mins. This is actually interesting—if you had two heaps, you could keep track of the biggest half and the smallest half of the elements. The biggest half is kept in a min heap, such that the smallest element in the biggest half is at the root. The smallest half is kept in a max heap, such that the biggest element of the smallest half is at the root. Now, with these data structures, you have the potential median elements at the roots. If the heaps are no longer the same size, you can quickly “rebalance” the heaps by popping an element off the one heap and pushing it onto the other.
  

Note that the more problems you do, the more developed your instinct on which data structure to apply will be. Hash tables, trees, tries, and heaps are some of the best data structures to solve problems.

Object-Oriented Design

Object-oriented design (OOD) questions come in two flavors: OOD for a piece of software and OOD for a real-world object. Despite the seemingly huge difference between these topics, they’re approached much the same way:

Remember that object-oriented design questions require a lot of communication with your interviewer about how flexible your design should be and how to balance certain trade-offs. There is no “right” answer to an object-oriented design question.

Scalability Questions

When I interviewed at Google, I didn’t know a thing about large systems. Sure, I’d taken a distributed computing course where we studied election algorithms and whatnot, but that had nothing to do with what I was asked. Sort a million numbers? Design a web crawler? Yikes!

I fumbled my way through the problem, and I realized I could do this just fine. Once I forgot that I had no idea what I was doing, I learned that I actually understood the primary complexities of large amounts of data and dealing with multiple systems at once.

All I needed to do was take things step by step. Imagine, for instance, that we’re designing a hypothetical system X for millions of items (users, files, etc.):

Testing Interviews

Testers have many names: tester, software design engineer in test, software test engineer, quality assurance, and hey-you-over-there-why-doesn’t-this-work. These titles can mean slightly different things depending on the company.

Whatever you call them, testers have a raw deal; not only do they have to master the coding questions, but they also must master testing questions. They must practice coding, algorithms, and data structures on top of the all usual testing problems. If you’re a tester, do yourself a favor and make sure to practice coding—it’s an excellent way to set yourself apart.

True testing questions usually fall into one of three categories:

Testing a Real-World Object

What does testing paper clips and pens have to do with testing Office or Gmail? Perhaps not a ton, but your interviewer certainly thinks they do. Your interviewer is using this question to test your ability to deal with ambiguity, to understand your ability to think about the expected and unexpected behavior, and, as always, to test your ability to structure and communicate your thoughts.

Let’s work through this recommended approach for an example problem: test a pen.