Google Interview

I had an interview with a Software Engineer from Google last week. It was a mock interview, and I was one of the 5 students selected by Google in the UVic CS department. It was a really nice learning experience, enjoyed every moment of it.

After the initial introduction, there were some technical questions about data structures and algorithms. I was given an interesting problem to solve(on the whiteboard, being Google!). The problem is as follows:

Suppose you are given two words, e.g. bat and cat. Find the shortest path to transform one word into another.

I started the solution with a brute force algorithm, after asking him about getting the whole dictionary as an input. Then we discussed some of the tradeoffs for simplicity and efficiency. During that brainstorming session, I realized a graph would be a much better data structure for this problem. I used Djikstra’s shortest path algorithm, and proceeded to draw a graph with the input word as a root, and the other word as the destination.

It was a much efficient approach, and we both worked it out together, which was a really nice experience, as instead of observing me solving the puzzle, the interviewer worked with me and we both solved it together. Overall, the interview was a success, I did come out of it with better understanding of problem solving and analytical thinking.