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.

Continue reading Do you think outside the box? ...

What's with this blogging stuff?

I have never really given blogging the respect I now think it deserves. Why would one blog in the first place, and more importantly, who cares?

Ironically enough, I found the answer in another blog. I wish that I could share it with you, but it's part of the internal blogging system at amazon.com. The very fact that amazon.com has an internal blog is what made me take blogging more seriously in the first place. I now feel that blogging is a great way to serialize one's thoughts. I think that it is tragic that many of us have great ideas and frames of thought that go unrecorded and then forgotten in time. Be honest, you've had some good ideas. You've had some intriguing random questions that would have made excellent discussion topics, but now they're gone. Lost forever. Will blogging solve this problem? Oh hell no. I'll still lose my train of thought, and *poof*, everything will be gone forever. However, the sheer convenience of a universally ( or is that internet-ally ) accessible system of recording and filing your thoughts certainly increases the odds that you will actually do it. Heck, maybe a few people will read your blog and help you develop some cockamamie thought into a well developed idea.

That brings me to my second reason for blogging: Writing. Writing is good. All I write all day is code. mmmmmmmmmm code. After some time writing computer code and attending meetings in which the presenter has provided barebones slides, my writing level has decreased dramatically. I can't believe what people write on their powerpoint slides these days. For example: "Need know reason for revenue decrease" What kind of English is that? Would it have been terribly hard to change it to sound more elegant? Are we becoming so preoccupied with efficiency that we are willing to sacrifice the more elegant and CORRECT aspects of the language? Aye, that's the topic of another blog. Let's hope that I can craft some reasonably well written entries. Besides that point, writing is also beneficial for another reason: it helps you evaluate and analyze all the branches in your thought tree. Your brain (well, maybe not your brain, but mine for sure) has a pathetically small amount of organized short term memory. Whenever I'm trying to solve a problem, there are always multiple paths to the solution. The problem is that there are too many points for me to forget what I was doing: "Well, I could do A or B or C... if I do A, then that leads to a1 and a2... oh but a2 is bad. Ok, what if I do C.. that leads to c1 and c2... but c2 sounds familiar ... did I think of this before.. was it while I was evaluating A? Is it similar to the a1 idea??? oh man... was there a B in there somewhere.... bah, let's do C" At least when I'm writing, I can write A, B, C, and then evaluate each branch as I see fit, with 100% "recollection" of all the intermediate ideas. That's good for Johnny. Not for you, the reader. In fact, why are you still reading this paragraph? You should have skimmed to something better by now.. go go, go away!


Still here? Thanks!
That brings me to my final point about blogging. There are so many topics on which I know so little, but just enough to get me into trouble. That's where you come in. It is not a responsibility of the reader to respond to my blogs. I mean, the fact that you are here reading my drivel is quite flattering. What really excites me, however, is the prospect that perhaps something I say will encourage you to offer your knowledge and/or opinion, and then I may learn. I mean, I don't know squat about... say, the true effect Open Source software will have on my future as a programmer. If I say something like "it will kill most of the paid programming jobs, because people are getting things for free!", I'm sure that those who understand the forces of the world of software will have something to say about that idiotic statement. (or is it idiotic? hmmm in some small way, that statement is a fear of mine... but again, I digress)

At this point I would have loved to present my Citizen Kane-esque Declaration of Principles, but quite frankly I don't want to force myself to conform to some set of rules that I thought were a good idea at some earlier time. This is a random stream of thoughts coming out of my brain, which, while fairly well educated, is subject to the various emotional influences that are just part of being a human.

Continue reading What's with this blogging stuff? ...