## 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*_{0}+ a_{1}x + a_{2}x^{2}+ …Suppose we have an interface as follows to get the coefficients: a

_{0}, a_{1}, a_{2}, etc:class PowerSeries { public: virtual double next(); };

You can take the product of two power series:

*(a*_{0}+ a_{1}x + a_{2}x^{2}+ …) * (b_{0}+ b_{1}x + b_{2}x^{2}+ …)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).