Elliott C. Back: Internet & Technology

I blogged earlier about SNL’s Chronic of Narnia rap, but now there’s a T-Shirt image [??]:

“You can call me Aaron Burr by the way I’m dropping HAMILTONS”

According to Wired, our favorite softcore pornographer Jimmy Wales has been editing his own wikipedia biography. I say, “but of course!” Is it a surprise that people will protect their own descriptions from the harsh light of impartial reality:

Public edit logs reveal that Wales has changed his own Wikipedia bio 18 times, deleting phrases describing former Wikipedia employee Larry Sanger as a co-founder of the site.

Wales has also repeatedly revised the description of a search site he founded called Bomis, which included a section with adult photos called “Bomis Babes.”

We all want to look good, but information will be free. As Blake Ross predicts:

George W. Bush will be the latest to come under fire for editing his own Wikipedia biography. Although Wikipedia will have implemented the most sophisticated algorithms to deter this kind of behavior, Bush will be caught because he will change all instances of “George” to “I”.

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.