t’s been almost a year since I had my interview for a summer internship at Amazon.com, but the memory is still fresh in my mind. I went in fairly tense, excepting a Microsoft-attack-style of interviewing, but I was pleasantly surprised to be greeted by a nonchalant employee with his feet up the table chewing on a pen. Over the rim of his framed glasses, he introduced himself and asked me to have a seat, which I did.
Little did I know that the first guy was actually one of a bar-raiser. Since the term is public knowledge, it can’t hurt to say that a bar-raiser is an Amazon interviewer dedicated to hiring only the best of the best candidates. A bar-raiser’s job is to go for those candidates that are somehow more special than even a “good” one.
We engaged in a little chit chat about my resume and life at Cornell before launching into the interesting part of the interview, which was the coding question. It was a basic one involving a special case of the subset sum problem (which is NP complete in the general case). It went like this:
Given an array of integers or other numbers (reals, doubles, etc), tell us if any two of the numbers in the array sum up to another given number.
There’s an n2 solution in which you compute all the possible pairs of numbers and then add them together to test the termination condition. Obviously, this is less than ideal. However, it is well known that integers can be sorted in O(n) time, where n is the number of integers to sort. Therefore, I proposed this additional precondition:
Allow the list of integers to be sorted in natural order before calling this method
The algorithm then is quite simple: keep an index at the far left side, and the far right side. If the indices become equal, or cross, we’ve failed to find a pair that works. To try to exhaustively find a matching pair, we try adding the numbers at our indices. If the sum too big, we decrement the right index. If the sum is too small, we increment the left index. If the sum is equal to what we’re looking for, we can return true. Pseudocode resembling Java might look like this:
public boolean inArr(int [] arr, int sought) {
int left = 0;
int right = arr.length - 1;
while(left < right) {
int test = arr[left] + arr[right] - sought;
if(test > 0) {
right--;
} else if(test < 0) {
left++;
} else {
return true;
}
}
return false;
}
Other questions would all be basic algorithms and OOP ones that simply want to establish that you can write decent code, think on your feet, and love what you’re doing.
