Elliott C. Back: Internet & Technology

There’s way to much space in my schedule this semester for my liking–I should take another class I think, but I’m already at 20 credits. Take a look for yourself:

I guess to fill the space and light load I’ll try the following:

• 1) Getting As in all my classes
• 2) Mastering above and beyond the level of Chinese offered in class
• 3) Pushing out a new blog layout and level of blog innovation (soon)
• 4) Achieving 72,000+ yearly income from blog advertising
• 5) Spending time with my girlfriend

I think I’ve settled on my Spring courses:

English 406 satisfies my remaining Arts III course, while the two English course satisfy my remaining specialization in English. Asian Studies and Chinese 102 are for fun, while Math 335 will serve as a replacement for COMS 381. You may view the actual schedule and layout on schedulizer.com if you so wish!

It’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 n² 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.