Do you think outside the box?

When I worked as a co-op for Royal & SunAlliance, I had the priviledge of reading through the resumes of those that would replace me. One thing that popped up soo annyingly often was the fact that many people wrote the same old tag-line: "Outside the box thinker". Apparently this was supposed to grab my attention like some grand marquee "Hire this person - here is our saviour! S/he thinks OUTSIDE THE BOX!" Wow, am I trapped in a box? Are mimes the only ones who comprehend the existance of the box, and are actually trying to escape it?

When conducting interviews, I never brought up the box line, simply because I knew that this would lead me into some tangental discussion that would only eat up valuable time that I could put to better use. After all, putting that dumb catchphrase on your resume doesn't really indicate that you are unskilled. I then unwisely spent parts of the next few years just droning on and on about what a stupid line it was, when I should have been coming up with some sort of acid test to evaluate if a person really does think "outside the box". In my opinion, don't waste valuable real estate on your resume writing this junk. If you really do think outside the box, it will come through in the interview as a (possibly) pleasant experience for the interviewer, when you answer the questions that s/he has set up for you. Writing that line on your resume will only challenge the interviewer to come up with some horribly contrived example of how you actually think. More on that later, I promise.

Defining the box is where I always gave up on the problem. What defines "the box" in which most of us unenlightened fellows think? It seems that "the box" is a nice little expression given to the tendency of regular folk to narrow the parameters of a problem in obvious and uncreative ways. I wish I could describe it better than that, but that's the impression I get. Maybe I'm wrong and you should go do something else with your time. Perhaps you have a better definition that you would care to share.


OK, so you've decided to write "I think outside the box" on your resume. Fine. If you think it got you that interview that I didn't get (grumble grumble), then you know something I don't.

Here are some horribly contrived acid tests I found that will come up. My solutions are at the end of this blog entry. I don't know if they are the solutions, but they are correct.

Technical. (stolen from a site with Microsoft interview questions)

Suppose you have an array of N+1 integers. The integers are in random order, but you know each of the integers is between 1 and N (inclusive). In addition, each number appears only once in the array, except for one number, x, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

The best solution I could describe finds the integer in O(n) time and O(1) space. I'm assuming that by "If you used auxiliary storage" they mean more than a variable or two. I can't really conceive of a solution that doesn't require at least one variable, such as a for loop index.

Nontechnical

Three people come into a hotel and ask for a room. The concierge says "Sure, that'll be $30 for the night". Each person then hands over a $10 bill. The concierge goes to give the money to the manager, which then says "No, the special this week is $25, go give $5 back." On the way back to the front desk, the concierge tries to decide how to give $5 to three people when there is no change in the drawer, so he decides to pocket $2, and gives $1 back to each person.

Now, if each of the people paid $9, and 9x3 = $27, plus the $2 in the concierge's pocket 27+2 = 29. Where's the other dollar?

Given the pattern of nine dots (in 2-dimensional space), connect all nine dots with four straight, connected line segments. In other words, if you print out the puzzle: connect all the dots with four straight lines and without lifting your pencil.

x  x  x

x  x  x

x  x  x

Solution can be found at the end.

---

Find x.
If you're like most of the programmers I know (including myself), then you probably tried desperately to solve the problem in a way that can easily be extended to solve a more general problem of this nature, such as "You have an array with N unique email addresses ...". So you reduced the problem to "find the repeat in the array", but couldn't conform to the O(n) time thing. That's ok, you are a great programmer. If I was the boss, I'd take that solution, and probably ask you to turn it into a C++ template or Java 1.5 generic or . Buuut you didn't exactly answer the question, so The Donald will fire you. Tough luck. Let's see what happened.
The box: You thought in computer code, didn't you? Ahh, that's alright, I won't tell anybody. You saw the word "array" and started thinking of array munging algorithms. S'ok. Let's try to think outside the box. (*sigh*) Well, what are we dealing with besides an array? Numbers... well, integers... hmmm a set of integers... a set of consecutive integers! This brings us into the other space of the problem. Let's use math to solve the computer problem! There are quite a few mathematical ideas around sets, so let's see if we can use one. The mathematical sum of a series of N consecutive integers beginning at the number a is (N*(N+a) ) /2. So in our case, the sum of the numbers 1 to 1000 is 500500. In the array, however, one and only one number is repeated, so if we sum up all the numbers in the array, we'll get 500500+x. Simply subtracting the sum of the numbers in the array from the sum of the first N numbers in the series gives us our answer. Let's try this in Perl:

use List::Util qw(sum);

sub findRepeat{
 my $n = (scalar @_) - 1; # to get the N
 return sum(@_) - ($n *($n + 1))/2;
}

Granted, this solution only works for this exact problem, but isn't that the point?

---

Where's the other dollar?
Another example of misdirection.
Each paid $9 for a total of $27. That's $25 for the room plus $2 in the concierge's pocket. Each guest has $1 in his/her pocket, for a grand total of $30.

---

Can you connect all the dots?
This one is great because it actually defines the box! =) Get out of the box!
I'll use my best ASCII art to show the solution:

|\   /
x x x
|  X
x x x
|/   x-x-x-

Ok, maybe not my *best* ASCII art, but I hope you get the idea.