Interviewed Apr 2009 in Dublin, County Dublin (took 4+ weeks) Applied online, after which it took about a month for Google to get back to me regarding interviews. First interview with recruiter who did a background check after which she informed me of two additional interviews: th... [More]

I interviewed at Google for a full-time Software Engineering position after graduation. As I informed the recruiter that I had a pending offer already, they skipped the initial interview and brought me in for a full-day interview. I met with 5 engineers: two 45 minute interviews, an hour ... [More]

Question: Binary Search Tree Validity Write a function to determine whether a given binary tree of distinct integers is a valid binary search tree. Assume that each node contains a pointer to its left child, a pointer to its right child, and an integer, but not a pointer to its parent. You ... [More]

You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in orde... [More]

Question: Substring Write a program to determine whether an input string x is a substring of another input string y. (For example, "bat" is a substring of "abate", but not of "beat".) You may use any language you like. Sample Answer (in C++): bool hasS... [More]

Question: Deck Shuffling Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely. In other words, given a deck of cards, how can you shuffle them such that any permutation of cards is equally likely? Good a... [More]

Classic Question #4: Reversing the words in a string Write a function to reverse the order of words in a string in place. Answer: Reverse the string by swapping the first character with the last character, the second character with the second‐to‐last character, and so on. Then, go through ... [More]

Classic Question #1: Coin Puzzle You have 8 coins which are all the same weight, except for one which is slightly heavier than the others (you don't know which coin is heavier). You also have an old‐style balance, which allows you to weigh two piles of coins to see which one is heavie... [More]