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
    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)
News · Politics

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.


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.
Job losses
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.
Consumer Spending


The White House fights back

Barack Obama has an op-ed in the Washington Post
starts to fight back at the short sighted, self-serving views that the Republicans have been using the past two weeks.
The Action Americans Need:

In recent days, there have been misguided criticisms of this plan that echo the failed theories that helped lead us into this crisis — the notion that tax cuts alone will solve all our problems; that we can meet our enormous tests with half-steps and piecemeal measures; that we can ignore fundamental challenges such as energy independence and the high cost of health care and still expect our economy and our country to thrive.
I reject these theories, and so did the American people when they went to the polls in November and voted resoundingly for change. They know that we have tried it those ways for too long. And because we have, our health-care costs still rise faster than inflation. Our dependence on foreign oil still threatens our economy and our security. Our children still study in schools that put them at a disadvantage. We’ve seen the tragic consequences when our bridges crumble and our levees fail.

I particularly liked the modest identification at the end of the article:

The writer is president of the United States.