Month: February 2014

Interviewing at Google

Yesterday I had two technical interviews for a software engineering internship position at Google. This article is an attempt to motivate people to apply and tell them what to expect. So, here we go.

The first Google engineer called me around 14:30. The connection was not optimal from the interviewers side so instead of a phone interview we had a Google Hangout interview. We shared a Google word document where I should write all my code (yes, a plain and simple Google doc).

The interviewer was nice to talk to, his first question was : “What made you apply at Google ?”. Well, everybody knows that I am an Android geek/enthusiast/dreamer. So that was my answer. Also, interning at Google will give you experience in the field which you can impossible learn in school. Things like for example : scaling of systems, coping with huge datasets, an extremely large codebase, etc. After that we proceeded towards the first question, which was something like this :

Question 1 : Assume you have a sentence represented by a string-object. Write a function (in Java) that will swap all vowels with a vowel at the end of the sentence. So for example : “United States => “Enated Stitus”.

Basically the approach here, is to work with an array of characters and work your way down the sentence using 2 pointers. One pointer points to a vowel on the left half of the string, the other to the right half of the string. If the right pointer is smaller than the left pointer, work is done and you can return the string.

I did OK on this question, had a little bug with my pointers that were incremented in the wrong place. But the interviewer pointed me to it, and I resolved it rather quickly.

Question 2 : Write a class called CollectionsIterator that is capable of iterating over a set of iterators. Make sure this class can hold Iterators of any type.

The interviewer thought this was the difficult question but I found it rather easier than the string traversal. Approach is again, rather easy. Create a class that implements the Iterator<E> interface. Use a field for a current_iterator and a field for the main_iterator. The main_iterator will loop over all the iterators and the current_iterator is the one that is providing the elements of a certain collection in the set of collections. Sounds easy, but tricky when implementing the hasNext() method. In the end, my first solution was perfect and that concluded the end of the first interview.

After a 15 minutes break I got the second interview. This one was by phone and again on a shared Google doc. This interview was not as good as the first one. The question was also more difficult than the first one.

Question 3 : Write a function that has as input a list of strings and will print to stdout strings that are rotational equivalent line per line. So all strings on one line are rotational equivalent.

I struggled the most with this question, due to the fact the interviewer started with the question : “Do you have any experience with rotation ciphers ?”. Sure I do know what they were, but never really implemented one so I didn’t know all the details about them. This threw me off a bit, but in the end you didn’t need to know exactly how they work. Just the notion how a string can be rotated over the alphabet.

So the approach I took for this question was looping over the strings and computing their fingerprint. Basically the fingerprint(String s) function should be a function that returns the same string for every rotational equivalent string. This can be achieved by using the convention that the first character of every string should be ‘a’. So we calculate the distance from the current first char to ‘a’. (only taking into account the chars a->z) and we rotate the whole string over this distance. We then use a HashMap to store a mapping “fingerprint -> set<rotational equivalent strings>”. In the end we write a prettyPrint() method which will iterate over the set and print out one set of rotational equivalent strings per line.

I needed some help, the interviewer for example pointed out to use a fingerprint method. After this I came up with the whole solution. A last question was what I thought was good/bad about my approach. At this point I perfected my code and told why I used some data-structures (like hashmaps and sets).

In the end it was a pleasant experience, much better than interviewing at Facebook. I have a good feeling, but if I don’t make it now , I can’t really be sad as I couldn’t do much more. At least I’m chasing dreams, as everybody should do !

Cheers,

H4