The Google Interviews

When I was a college senior I applied for a job at Google. During the in-person interview, the interviewer asked me to find the median of an infinite series of numbers and I just stared at the board, having no idea what to do. Every idea I came up with that was reasonable for a finite series fell flat when faced with an infinite series.

After one more excruciating (but less memorable) interview, they politely showed me out.

So, I was a bit nervous this time around. However, I am pleased to report that I never was at a loss for what to do and all of the questions seemed pretty fair and reasonable. Most of the questions were basically variations on things in Cracking the Coding Interview, so I figured I’d share them. I got a few more creative questions which are not listed below (I don’t want to ruin a anyone’s “personal” question) but they weren’t any harder or easier than the others.

Note: if you’re planning to interview somewhere soon, you might want to save this, do your other prep, and then go through these questions as a mock-interview.

Here’s what I was asked:

• Given this weird tree-like thing:

  

  Find greatest sum on a path from root to leaf (that can only touch one node per level—no going up and down).

  I did a recursive solution that was about six lines long and then she asked me to come up with a way to do it iteratively.

• Consider a power series:

  a₀ + a₁x + a₂x² + …

  Suppose we have an interface as follows to get the coefficients: a₀, a₁, a₂, etc:

  class PowerSeries {
  public:
      virtual double next();
  };
  

  You can take the product of two power series:

  (a₀ + a₁x + a₂x² + …) * (b₀ + b₁x + b₂x² + …)

  Implement next() so it gives you the next coefficient in the product of two power series:

  class PowerProduct : public PowerSeries {
  public:
      PowerProduct(PowerSeries* A, PowerSeries* B);
      virtual double next();
  };
  

• Reverse bytes in an int.

  This was in my last interview of the day, and mental fatigue had reduced me to such a state that I assumed four bits in a byte. I don’t even know where that came from, but that was really embarrassing when I realized it (well after the interview).

• Write a function to find if a set A is subset of a set B, B is a subset of A, the two sets are equal, or none of the above (you are allowed to use set operations like union and intersection).
• Part 2 of the previous question: suppose you are given a list of sets. You wish to filter out any set in the list that are a subset of another set in the list. Use your solution from above to find the smallest possible result list as efficiently as possible.
• Implement atoi (convert a string to an integer).
• Given a string, find the logest substring of only two distinct characters. For example, given “aabacccaba”, you would return “accca”.
• Design a cache.
• Suppose you are on a Cartesian coordinate system. Find all paths from (0,0) to (m,n) that only go through each point once. For example, if you were given m=2, n=2, you’d have the following:

  

  This would be one possible path:

  

  Return the number of possible paths. Then extend for negative coordinates.

• Given two integers, a and b, find the smallest square integer in the range (or return -1, if there is no such square).