Blog - Google interview, on-site

Apparently my first interview went well, because today I had my on-site interviews at Google Moscow! I was interviewed by five different employees, including one from Zürich. Their video conferencing setup is quite nice :)

The office is as you would expect, with the obligatory Wii, Google pillows, gadgets everywhere and free food and drinks. They don't have their own restaurant though.

Most of the interview questions were about relatively simple algorithms, but the catch was always in getting the algorithm complexity as low as possible. Take e.g. the following assignment.

Suppose you have a type x[] and type y. type can be anything for which addition (+) and comparison (<, ==, >) are defined. Let's take integer to make things a bit simpler. Also, x[] can possibly contain tens or even hundreds of millions of items. (We're talking Google here ;)

Now write the following function:

int[] findSum(int x[], int y);

The function should return int i and int j, for which x[i]+x[j] == y. Try it out :) (And then read on.)

Now suppose int x[] is sorted. How does that help you? What's the smallest complexity your function can have, worst, average and best case?

I admittedly had some difficulty with this one. I tried hash maps first, which yields O(n*log(n)). With some help of the interviewer I got to O(n), as follows (pseudo-C):

int[] findSum(int x[], int y)
{
    int i = 0, j = x.size()-1;
    while (i != j)
    {
        if (x[i]+x[j] == y)
        { return { i, j }; }
        else if (x[i]+x[j] < y)
        { j--; }
        else if (x[i]+x[j] > y)
        { i++; }
    }
    return NULL;
}

Of course only after the interviews were over I realized that this could be brought down to best case O(log(n)). Chances are that e.g. x[i]+x[j] < y will hold for a long time. Instead of j--, we could have j-=2, j-=4, and so on. When e.g. j-=16 yields x[i]+x[j] > y we should cancel the j-=16, and start again with j--, j-=2 etc. Of course this takes a bit more code, but given best case O(log(n)) and such a big data set, it's more than worth it.

Another nice assignment was writing a function that given an int i prints all the possible legal combinations of parentheses. E.g.:

1. ()
2. (()), ()()
3. ((())), (()()), (())(), ()(()), ()()()

There were also some questions on how I would implement a service like Google Maps. You have to take into account the fact that e.g. Moscow maps will be requested way more than some mountain in the Ural.

All in all the questions were interesting and challenging, just like I expected :) Again I'll be hearing from the recruiter, so last time fingers crossed :)