Code Fellows Final

We'll now create a building in CSS using some simple drawing commands to represent our answer. The following building is floors high

Creating an array

Next, we create an array representing the total floors in the building, displayed in a random shuffled order to make the sorting algorithms do their work on unpredictable data.

for (var a=[],i=0;i < $answer;++i) a[i]=i;

function shuffle(array) {
  var tmp, current, top = array.length;
  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }
  return array;
}

a = shuffle(a);

console.log(a)

And here is what the array looks like shuffled up:

Sorting the arrays

Next, we will sort the arrays, using a purposely inefficient method and compare it to an efficient method, counting the number of iterations required to sort the previously created array for the random number of floors calculated at the start of this exercise.

Bubble sort

The bubble sort represents our inefficient method, where every time we sort our random array by ascending number, we need to compare the first number in the array against every other one before deciding if it is lower, then repeating this. The code is as follows:

// bubble sort the array to count comparisons/swaps

var sort = function (list) {
 
    var comparisons = 0,
        swaps = 0,
        endIndex = 0,
        len = list.length - 1;
 
    for (var i = 0; i < len; i++) {
 
        for (var j = 0, swapping, endIndex = len - i; j < endIndex; j++) {
            comparisons++;
 
            if (list[j] > list[j + 1]) {
         
                swapping = list[j];
 
                list[j] = list[j + 1];
                list[j + 1] = swapping;
 
                swaps++;
            };
        };
    }
 
    console.log("--Bubble Sort--");
    console.log("Comparisons: " + comparisons);
    console.log("Swaps: " + swaps);
    console.log("Total steps " + (comparisons+swaps));
                 
    return list;

};

// bubble sort the randomized array of length $answer
sort(a);

The bubble sort function above counts both comparision steps as well as swapping steps and I've combined them to come up with a value for the total steps to finish.

Total steps required of a bubble sort of items:

Merge Sort

Merge sort uses more of a divide-and-conquer method to split groups in the array and quickly compare them for sorting or determine they are already sorted. It takes a lot less steps to accomplish the same re-ordering of the array. The code is as follows:

// create merge sort of our array

var comparisons = 0,
  swaps = 0; 
function mergeSort(arr) {
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);
 
 
    return merge(mergeSort(left), mergeSort(right));

}
 
function merge(left, right)
{
    var result = [];
 
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
            swaps++;
        } else {
            result.push(right.shift());
        }
        comparisons++
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}

// merge sort our array 
console.log(mergeSort(b));

console.log("--Merge Sort--");
console.log("Comparisons: " + comparisons);
console.log("Swaps: " + swaps);
console.log("Total steps " + (comparisons+swaps));

The Merge sort method includes a counter inside the function to split things up as well as the function to check if one is bigger than the other.

Total steps required of a merge sort of items:

Conclusions

The answer to the interview question is not to try every floor until you arrive at an answer. That's too inefficient, taking too many steps and taking too long to complete. The correct answer the interviewer was looking for was to approach the problem in an efficient manner, by going halfway up the building and dropping an egg off the 50th floor to instantly remove half the possibilities. If it broke, you'd go down to the 25th floor, and then the 12th, and so on until you arrived at the answer in just a few steps.

Every time you use Google for search, you are dealing with potentially billions of items that must be sorted instantly on almost any search query, and getting to an answer efficiently is of prime importance for them to operate at the scale they do.

Total steps required to sort items
bubble sort:
merge sort:

The merge sort method is more efficient with our array, on the order of about 1/10 as many steps as the bubble sort, or close to one magnitude of efficiency on the higher number of levels. The bubble sort represents the slow, methodical, inefficient sorting of climbing every floor, while the merge sort cuts the array in half, and half again, and so on until arriving at the answer.

My friend did eventually end up with a job at Google later that same year working on Blogger and the next year he went on to implement the web interface for Gmail and helped invent Google Reader. I'd argue that tricky brain teasers might not be the best possible way to interview programmers when a talented guy like my friend failed the first time around. :)