Interview Workshop

I was on a "Google Interview Workshop" they gave at my university. They say the convertion rate went up a lot since they begun to do that. Many more students who do this workshop also get a internship at Google compared to those who do not.

So in the beginning they were again just trolling about how greate Google is as a employer, like they do on each and every such occasion, I've heard that now for the third time and yeah ...

But anyhow, then they talked about the offices in Europe who does what where and how the communication works internally and stuff like that, this was quite interesting.

The last thing, and what did take the longest time, was that the engineer who was there too showed us a couple of technical example questions and one of them we had to solve together. The question was something like this:

Write a function which takes a sentence as a string and reverses the order of the words.

So "The weather is just fine" would become "fine just is weather The".

So I jumped in with my ruby skills and proposed:

"The weather is just fine".split(" ").reverse.join(" ")

But it should not be that easy, the point was not to use any build in functions and not to use additional memory, except for one character, which he said was unavoidable. So even if your string was 3 GB big and your machine had only 4 GB RAM it should still be possible to reverse the sentence.

We were 6 people and it took us at least 40 minutes to come up with a solution in C, which would only use this one character of extra memory but otherwise reverse the words in the sentence in linear time:

#include <stdio.h>

void reverse_string(char *s, char *e)
{
    while (s < e)
    {
        char c = *s;
        *s = *e;
        *e = c;
        
        s++;
        e--;
    }
}

void reverse_sentence(char *i)
{
    char *start = i;
  
    while (*i != '\0')
    {
        char *s = i, *e = i;

        while (*e != ' ' && *e != '\0')
            e++;
        
        char *end = e - 1;
        reverse_string(s, end);
    
        i = ++e;
    }

    char *end = i - 2;
    reverse_string(start, end);
}

int main()
{
    char sentence[] = "The weather is just fine\0";
    reverse_sentence(sentence);
    
    printf("%s\n", sentence);
}

So what we basically do is to go through the string, reverse each word on its own on the way and then at the end we reverse the whole string and that way get all words reversed.

The weather is just fine
ehT weather is just fine
ehT rehtaew is just fine
ehT rehtaew si just fine
ehT rehtaew si tsuj fine
ehT rehtaew si tsuj enif
fine just is weather The

That way we don't need to measure the length of the string in advance or anything, it just works out nicely with very little code. He also said that we should really communicate all assumptions we would make so the interviewer can hear what we have been thinking about and how we came up with the solution, so we did that during the coding session. Just regular stuff like that we assume that all the characters are ASCII and that as whitespace we only take into account spaces and so on.

When we had finished, he said that it was a really nice solution but during a real interview it should take us not more then ten minutes to do it.

I felt quite dumb during this whole thing, even though I came up with some parts of the solution and found some bugs the other guys introduced. But then it seemed that I was not alone with this feeling, everybody failed in some way so it wasn't that bad for every each of us :D.

At the end the engineer said that we all had quite good problem solving skills but really have to improve our coding skills before we even think of applying for an internship at Google.

But who knows, nothing is impossible!