Matt Haughey's final project for the Code Fellows Foundations intro class

A friend interviewed at Google in early 2003, hoping to get a job as a front-end web developer. The interviewer asked him one of those famous tech startup brain teaser questions, and now that I've completed this class, I can understand they were simply separating applicants that had some sort of traditional computer science background from those that did not (this friend was a musician and web design guy that taught himself javascript). The brain teaser at the job interview was as follows:

You are standing next to an empty 100-story building. You have at your disposal 100 ostrich eggs. Remember that ostrich eggs are very tough to crack, often requiring a hammer in the kitchen. I want you to tell me the process of how you would figure the highest floor of the building you can drop an ostrich egg without breaking in the least steps possible.

At the time, my friend asked me how I would answer it. Not knowing anything about real programming (I was a web designer with a bit of simple server-side scripting experience), I answered that I'd take all 100 eggs, and start walking up the stairs, stopping at floor 1 to drop an egg and wait, then climbing to floor 2 and try again, and so on, until I got the answer. He answered the same way to the interviewer, and didn't get the job.

First, we build a random number generator to give us an answer upfront between 1 and 100 that we will use to compare sorting algorithms. The code is simple and as follows:

var $answer;
$answer = Math.floor(Math.random() * 100) + 1;

Push the button below to pick a random floor number that will serve as the answer of how high you can drop an ostrich egg safely from.

Click to generate a random number between 1-100

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

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:

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.

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 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: **

**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. :)