Platinum Partner
java,google

My 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:

    semitree

    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:

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

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:

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:

    paths

    This would be one possible path:

    paths2

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


{{ tag }}, {{tag}},

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}
{{ parent.authors[0].realName || parent.author}}

{{ parent.authors[0].tagline || parent.tagline }}

{{ parent.views }} ViewsClicks
Tweet

{{parent.nComments}}