Hilarious spoof by SNL on the Republicans:

# Month: February 2009

# Trivial subset sum problem

I was asked in a telephone interview how to find out if there are two numbers in

a list that sum to a certain value. I did an O(N^2) algorithm, then refined it to an O(n lg n) algorithm. Unfortunately, there’s an O(n) algorithm which I didn’t think of on the phone but came up with after the fact:

def somePair(values, Z): """ Given a list of numbers and value Z, are there any pair of numbers such that X+Y = Z? This does this in O(N) time looking at each value, val, and checking if Z-val is already in a lookup table. """ lookup = set() # Store the values for val in values: diff = Z - val if diff in lookup: return True else: lookup.add(val) return False if __name__ == '__main__': assert somePair([], 4) == False assert somePair([4], 4) == False assert somePair([1,2,3,4], 1) == False assert somePair([1,2,3,4], 2) == False assert somePair([-8, 12], 4) assert somePair([1,2,3,4], 3) assert somePair([1,2,3,4, 4], 3) assert somePair([1,2,3,4], 4)

# Stimulus and the Economy

This chart from the Fed shows how far below capacity the economy currently expressed as a percentage of total capacity.

It’s the counter argument to the proposition that the stimulus is just going to crowd out private investment. Businesses have cut back on production because of reduced demand which further reduces demand.

# If bankers were…

From The Salt Lake Tribune:

# Job losses as a percent of peak

Ah, here’s the version normalized to the peak employment level before recession a started. From calculatedriskblog.com:

# TED and Saturn

I watched this TED talk on the Cassini probe to Saturn.

You can grab images here. It’s a great collection especially for setting as backgrounds. Here’s one from Nov 2007:

or this one from Oct 2007:

# Job losses and consumer spending

Is the past prelude? Here’s a comparison of job losses in all the post-WW2 recessions. Note how bad the slope is for the current recession. Be careful though, these are absolute numbers and not relative to population.

And here is the change in consumer spending over the past 50 years smoothed to six months — meaning some bad months have gotten smoothed over with the surrounding better months. Is this really the only the second time it’s gone negative in five decades? And that first time was only barely negative.