Any idiot can drive fast in a straight line

Saturday, May 10, 2003

Let's see, where to begin... First, the interview from a week and a half ago! I can't divulge much information, for two reasons: 1) I haven't gotten a yes or a no from said company. 2) I had to sign an NDA before I could talk to anyone. Let's see how many details I can give away without giving it all away.

First, I was told that I would have anywhere between three and five interviews total. There ended up being a total of six, which I can only interpret as being a hopeful sign. I arrived at the recruiting building (yes, an entire building devoted to recruiting) around 8 AM and didn't end up leaving until around 6 PM. Given a half hour for lunch, that was practically nine and a half hours of interviewing!

Second, the riddles asked were fairly interesting and though I might have heard them all before, I had never solved any of them. The first one wasn't so much a riddle as a generic design question. I was asked how I would design the timing on any given traffic light. I was allowed to request whatever information desired and then I had to come up with some formulas for making the "best" traffic light. The first part of the problem was how to define "best". What makes a good traffic light? I decided it was a combination of two factors: 1) Maximum throughput in all directions. 2) Low traffic jam incidence rate. After figuring out the formula for a single intersection, I had to modify it for a grid of intersections. Then I was asked to "think outside the box" (yes, that phrase was used exactly) and figure out other ways to improve the experience. All in all, a basic design problem.

The second riddle was a programming question, something I didn't expect to encounter since I was interviewing for a management position. Managers don't code! I was given a 2D array and had to figure out the time it would take to sort it. I barely remembered performance numbers for the different sort algorithms, but I remembered that quick sort was O(n log n) (and thankfully was correct). Sorting a 2D array would thus take (O(n log n))^2. The second part to the programming question was how to sort two already sorted linked lists. This was simple, since you just setup two iterators that would move along the two lists, removing the smaller of the two items.

The riddle I had the hardest time with was the cube desk calendar. You have two cubes and you are allowed to put any single digit on any face. With these two cubes, you have to represent every number from 01 to 31. This turned out to not be that difficult when I realized you could mathematically approach this and define restrictions. Some examples of these restrictions are that you need a "1" on each block since you have to represent "11". The same thing for "2" and "22". Eventually, I got to the point where I had six open spots on the cubes but seven numbers to put on the cubes. This is when I realized that you could use "6" to represent a "9" and thus solved the puzzle.

Almost all of the riddle had a mathematic basis. The next riddle started off as a word problem. A man starts at point A on a mountain and walks up to point B in exactly 12 hours. At some time later, he walks down from point B to point A in exactly 12 hours. He does not have a constant rate of ascent or descent. The actual riddle was "Can you prove or disprove the existence of a point P where the man took the same amount of time to reach the same spot on the mountain?" I was having trouble trying to prove this, since it had to be true. Eventually, I was given a hint to use a graph. First I tried plotting time versus distance. That was dumb. Once I plotted time versus location, I showed that the plots must intersect and thus a point P does exist.

The last riddle was one I heard a long, long time ago. I knew the answer, but didn't know how to explain it at first. This was the "Let's Make a Deal" riddle: You have three doors to choose from, 1 with a prize and 2 without. After you choose your door, the host of the show will eliminate one of the doors you did not choose and then ask you to pick again. You can either stick with your original door or choose the remaining door. The question is, do you stay or do you switch and why? I knew you were supposed to switch, but couldn't think off the top of my head why. Finally I realized that your initial chance at winning was only 1 in 3. After the elimination, your chance is at least 2 in 3. Switching is smart.

Ok, that was the first of more updates. I gotta run now though.

Ok, everyone has been bugging the hell out of me to post, so here comes a barrage of updates.