Google Java Interview - May 2013

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:
  a0 + a1x + a2x2 + …
  Suppose we have an interface as follows to get the coefficients: a0, a1, a2, etc:

view source

print?

1.class PowerSeries {

2.public:

3.virtual double next();

4.};

You can take the product of two power series:

(a0 + a1x + a2x2 + …) * (b0 + b1x + b2x2 + …)

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

view source

print?

1.class PowerProduct : public PowerSeries {

2.public:

3.PowerProduct(PowerSeries* A, PowerSeries* B);

4.virtual double next();

5.};

• 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)