The Complexity Hammer

re: The Complexity Hammer

hiryu — Sun, 04 Apr 2010 13:46:10 GMT

I agree with jonathan opinion about this article Jonathan what you meant by memoization is it suppose to be memorization or something else?

re: The Complexity Hammer

Jonathan — Mon, 22 Mar 2010 03:45:44 GMT

To me, factors that would impact on how well someone goes on a task like this would be:

* problem solving skills

* level of nervousness

The interviewee that has well developed problem solving skills may be helped secondarily by having the confidence to sit back and think about it, and conversely, a nervous interviewee probably won't have that confidence.

I've noticed that "sitting back and thinking about it" can't be done (well) in front of the computer, or at least, not while using the computer, because it seems to bring the thought levels down to details and pixels, not concepts and possibilities.

Also, I came across some brain fitness research (can't recall the link, sorry) which relates to how well they deal with the solution being wrong. Basically, when someone is afraid (read "nervous") or tired, and fails at something, they tend to retry the same or similar solutions - thus getting stuck in a rut. This can be applied to life, and gives me some food for thought - I think it has been picked up by some self-help book authors too.

But also, and slightly off on a tangent, relating more to my previous post, what may also affect the outcome is how well they know the language/tools, and thus how well they can match the problem (or sub-problems) to existing solutions. For example, regarding optimization, because of the way it is written, the lisp solution above is amenable to memoization.

re: The Complexity Hammer

Jonathan — Sun, 21 Mar 2010 11:41:18 GMT

A bit OT, and it's probably unreadable, but it came to me as I read your post. It loops a total of 557 times, but also uses recursion. Perhaps it will stimulate discussion :).

>(defun make-change (&optional (amount 100) (coins (list 25 10 5 1)))

> (when coins

> (if (cdr coins)

> (iter (for i from 0)

> (for remains downfrom amount by (car coins))

> (while (>= remains 0))

> (appending (mapcar (curry #'cons i)

> (make-change remains (cdr coins)))))

> (if (zerop (mod amount (car coins)))

> (list (list (/ amount (car coins))))))))

re: The Complexity Hammer

SteveRowe — Thu, 18 Mar 2010 17:55:49 GMT

@Chad/Rick. Good catch. I'll change it.

re: The Complexity Hammer

Chad — Wed, 17 Mar 2010 18:14:25 GMT

@Rick, the equality test in BetterMakeChange() should be with 100:

if (100 == (quarters*25 + dimes*10 + nickles*5 + pennies)) print…;

re: The Complexity Hammer

Rick — Wed, 17 Mar 2010 14:33:58 GMT

In BetterMakeChange(), the if check only evaluates to true on the first pass through, when the change for a dollar is 0 quarters, 0 dimes, 0 nickels, and 0 pennies.

re: The Complexity Hammer

SteveRowe — Tue, 16 Mar 2010 21:59:29 GMT

As I said at the bottom of the post, this is meant to demonstrate a way of solving problems that is often indicative of a broader pattern. Don't get hung up on the specifics of the implementation. The fact that there are hard coded constants is because it makes reading simple for this example. The penny loop isn't optimized away either and it doesn't abort when the total is too high mid-loop. This is to demonstrate a point, it's not how I would advocate writing such a program.

@Mike, how do you enumerate all ways of making change without a loop?

re: The Complexity Hammer

Maurits [MSFT] — Tue, 16 Mar 2010 21:27:15 GMT

Some free complexity analysis: the stateless example makes the "is the total accurate" comparison (4 + 1) * (10 + 1) * (20 + 1) * (100 + 1) = 116,655 times.

By comparison, the stateful version makes the comparison 6,962 times (I calculated this by incrementing a global every time the comparison was executed. I an not aware of s a way to calculate this elegantly.)

re: The Complexity Hammer

Maurits [MSFT] — Tue, 16 Mar 2010 20:26:31 GMT

> What if we wanted to make change for something other than $1.00?

Well said... and what if you want to make change in a country that uses a 0.20 piece rather than a 0.25 piece? And what if you want to allow half-dollars?

Sometimes solving the general question is easier than solving the easier version:

use strict;

# first argument is a prefix

# second argument is the amount of money to change

# the rest of the arguments are the eligible coins

# these must be unique, > 0, integral, and in descending order

# no return; just prints out the available combinations

sub change($$@);

change("\t", 100, 25, 10, 5, 1);

sub change($$@) {

my $prefix = shift;

my $total = shift;

my @coins = @_;

if (@coins == 0) {

# if the total came to 0 we have a solution

print $prefix, "\n" unless $total;

return;

}

my $coin = shift(@coins);

my $most = int($total / $coin);

for my $count (0 .. $most) {

change(

$prefix . ($count ? " $count * $coin" : ""),

$total - $count * $coin,

@coins

);

}

re: The Complexity Hammer

Chad — Tue, 16 Mar 2010 19:26:29 GMT

Personally, I've had limited success applying rules of thumb like "step back and look for a more elegant solution." It's about as effective as cajoling developers to "Be More Innovative" or "Don't add bugs." We know these things, but they don't tell us how to do these things.

Adding better tools to ones toolbox pays better dividends: Gather data through repeatable experiments. Divide and Conquer. Identify a simpler version of the problem and solve it first.

I'm surprised at the pooh-poohing of state. There are often times when keeping state around makes a problem much simpler to solve, especially for table-driven methods. In all my algorithmic training, I can't remember an instance where having four levels of deeply-nested for-loops was part of an elegant solution. Even if performance isn't an essential requirement for the code, the code seems awfully un-reusable. What if we wanted to make change for something other than $1.00? All those hard-coded (and uncommented) magic numbers would have to be re-calculated in some programmer's head.

I do agree that watching great programmers solve problems is a joy.