# Ruining the coding interview

I’m talking at Scala By The Bay on Saturday. Here’s a teaser for my project, taken from the Github page:

When I was interviewing for my current job, I spent a lot of time learning about different data structures and algorithms, and when you’d want to use one over another. You know, standard stuff. It takes log(n) time to insert items into a binary search tree, but then you can search for them in log(n) time. It takes constant time to append an item to an array, but looking for the item then takes linear time. So when you’re deciding whether to use an array or a binary search tree, you have to look at what operations you need to support, and how regularly you’re going to call the different operations, and then you want to choose the data structure which minimizes your cost.

Other problems kind of have this structure too. Here’s a simple dynamic programming question: Given a list of the price of a stock on different days, and the restriction that you have to buy before you sell, choose the pair of dates on which you want to buy and sell to maximize your profit.

The simple implementation is to run over all pairs of dates and choose the pair with the largest price difference. This takes quadratic time. It’s a better idea to loop over the list once, keeping track of the lowest price you’ve seen so far and the best profit opportunity you’ve seen so far. This implementation runs in linear time.

We can look at this in a similar kind of way. Why is the second way faster? You can basically look at it as a way of speeding up the query “What is the lowest price occurring in the first n places in the array?”. This query is worth speeding up, because it takes linear time and we call it a linear number of times.

So the way that you solve algorithms problems is you figure out the operations which need to be called most regularly, and you figure out what to precompute to speed them up.

(Some algorithms problems don’t fit into this structure. This structure only describes the core of the algorithm question in the case where you know how to write a trivial solution to the problem, and the goal of the interview question is to come up with a faster implementation.)

Compilers do all sorts of optimizations which humans don’t want to. For example, if you write something in C like

int mathyThing(int k) {
int total = 0;
int i;

for (i = 0; i < 10; i++) {
total += i * k * 3
}
}


your compiler will notice the repeated k * 3 multiplication and move that outside the loop. The compiler spotted a slow operation and moved it outside a critical loop. There’s that pattern again.

So my project is to make optimizing compilers at a higher level than that: at the level of choosing data structures and algorithms, rather than at the level of choosing where to compute loop invariants. This is obviously a highly ambitious project.

For this presentation I’m just going to be talking about the part of this I’ve implemented. Programmers should be able to use high level data structures like multisets and have a compiler decide what data structures the multisets should be using under the hood. I’m trying to make that happen.

Here’s the only problem. My adventures into automatically generating data structures lead me to a wide variety of complicated data structures, which I find fascinating but I feel very little desire to actually implement. So while I’m interested in the question of what data structures you should use, I’m not actually interested in doing all the hard work which I’d need to do to actually generate usable code. In real life, you’re not allowed to just say “and now you use a heap here”, but in coding interviews you are.

So for now, I’m not trying to improve programming. I just want to ruin the coding interview.

The GitHub project page contains much more detail about what I’m doing and how I’m doing it. I hope to see you at my talk!

# The value of a life

Throughout this essay I ignore flow-through effects, non human animals, and effects on the distant future, even though I don’t discount those in my personal altruistic decisions. Feel free to expand this analysis if you want to include those factors.

Occasionally this essay sounds harsh or uncaring. This is unintentional. I care deeply about the lives of people who suffer from extreme poverty. I am only thinking about this because I care; because in a situation where we don’t have enough resources to help everyone, we need to triage, to figure out who we’re going to help. If your response to hard and upsetting problems is to ignore them, you’re not going to be able to improve things very much.

Obvious disclaimers: I think it’s a dumb idea to kill extremely poor people. Also, well-being varies for reasons other than poverty.

TL; DR: If we’re choosing between spending money on saving lives and reducing poverty, we need to consider how to compare the happiness created by saving a life to the happiness created by increasing the consumption in a society. Differentiating an estimate of happiness as a function of consumption lets you estimate the happiness created by increasing marginal consumption. If you assume happiness is logarithmic in consumption, then the dollar amount at which you’re indifferent between saving a life and increasing total consumption that much increases as consumption * log(consumption). However, this model is really bad at making predictions when the people involved are really poor, so it’s almost completely useless for answering practical questions about saving lives vs improving them in developing countries. I think that my discussion of poverty levels of people affected by AMF and GiveDirectly is kind of useful even for people who find the more theoretical part of this post silly.

Thanks to Claire Zabel, Marie La, Daniel Filan, and others who helped me with this.

Sometimes it’s useful to be able to put a value on a human life. To use a crass metaphor, these days human lives go for about $3400 if you want to buy them from AMF. That’s the seller’s price. I’m interested in calculating the maximum price at which we should be interested in buying human lives. One way of defining this “buyer’s price” of a human life is the maximum price at which we as a society would rather save someone’s life than just keep the money. People are happier when they have higher consumption. If I could save the life of one American, but reduce American GDP by 10%, I’m pretty sure that would overall not be a good trade. So we need to have a way of comparing the damage done by reducing the consumption of an economy by some amount of money to the damage done by someone in the economy dying. ## Logarithmic happiness It’s pretty common to approximate happiness as linear in the logarithm of income, which I’m going to equivocate with consumption for the rest of this post. Consumption just means “the total value of all the things you consume in a given year”. Average happiness in a population where everyone has consumption $c$ can be written as: average happiness = $\log c + k$ where $c$ is consumption and $k$ is a constant that tells us about the consumption level at which a life is so meagre and deprived that it isn’t worth living, and also tells us how rapidly happiness increases relative to wealth. If people have a life expectancy of $t$ years, then we have the total happiness-years of a person as $t \log c + t k$. Anyway, back to the math. The derivative of this function with respect to consumption is $\frac{1}{y}$. So if we reduce the size of an entire economy by some small amount $\Delta c$ evenly spread across the whole population of n people, then the reduction in happiness per person is: $\Delta \text{happiness per person} = \frac{\Delta c}{c n}$ but there are $n$ people, so the total reduction in happiness is: $\Delta \text{total happiness} = \frac{n \Delta c}{n c} = \frac{\Delta c}c$. So if we have the option to spend $\Delta c$ to save a life, we should be indifferent to doing so if the total reduction of happiness caused by reducing the total consumption by $\Delta c$ would be the same as the happiness of a given person: $t (\log c + k) = \frac{\Delta c}{c}$ We can solve this for $\Delta c$: $\Delta c = c t (\log c + k)$ Now we can substitute the value that we end up choosing for $k$ below to figure out that America should be willing to spend up to about$10 million to save an American baby. You can see the calculation here.

That’s all the math. Now, let’s spend two thousand words trying to figure out precisely how much fun it is to be extremely poor!

## Thinking theoretically about $k$

The biggest judgement call in this essay is that $k$ constant. The consumption at which a life has 0 value according to the above formula is $10^{-k}$. So if you think that life isn’t worth living if you’re consuming less than $1000 a year, then you think $k$ is -3. That’s the literal meaning of $k$. However, it seems plausible to me that our log model breaks down when people are incredibly poor. So I think we should use two different strategies to think about $k$. Firstly, we should think about it assuming the model is correct, looking for the level of consumption at which life seems to not be worth living. Secondly, we should try ignoring its literal meaning and just trying to directly estimate it by looking at happiness variation across relatively small consumption variations. This should hopefully provide a good estimate over the kind of range we’re interested in. Imagine we decided that living on$100,000 a year is twice as much fun as living on $10,000 a year. This would mean that $log 100000 + k$ is twice as much as $log 10000 + k$. So $k$ would be -3. If we thought poverty was not as bad as that, then maybe we’d be saying that living on$1,000 a year is half as good as $10,000. In that case, $k$ would be -2. I think that the first of those is probably truer, so this is another argument for estimating $k$ as about -3. Maybe we should be concerned by this, because more than a billion humans have less than$1000 annual consumption. I have a few thoughts on this. To start with, it seems plausible that the purchasing power parity adjustment I’m using isn’t powerful enough. It’s cheap to have a place to sleep in rural Malawi, much more than it is in America. If there were a Malawian rural town within commuting distance of my office in SoMa, I’d be ecstatic to pay $200 a month to live in a thatch-roofed hut there. (I’m not kidding: I lived on an air mattress on the floor of my office for six months last year.) There are lots of really cheap goods available to Malawians, like thatched roof huts and really cheap shitty rice, which are unavailable to me but make it much more easy to live cheaply. To some extent, I’m willing to buy that living in SF counts as bonus consumption, because I’m closer to fun things, but mostly I just live here so that I can work here, which feels more like an employment-related expenditure than consumption to me. So maybe I don’t buy that as someone with an annual consumption of$30k, I’m really getting 40 times the consumption in my life as the average resident of Malawi.

The book Poor Economics tells the story (starting on page 20) of this extremely poor Indonesian guy called Pak Solhin. He used to live on $2 USD PPP a day, until he lost his job, after which he lived like this: Pak Solhin himself survived on about 9 pounds of subsidized rice he got every week from the government and on fish that he caught from the edge of a lake (he could not swim). His brother fed him once in a while. In the week before we last spoke with him, he had had two meals a day for four days, and just one for the other three. That life is being classified as significantly less than$2 PPP a day, which I don’t think includes the benefits of free rice, his brother’s food, or fishing in the river.

I’m not trying to trivialize extreme poverty here: that life sounds pretty shit, and I’m incredibly glad I don’t have it. But I don’t think it’s entirely sensible to call that “living on $1 a day”. On the other hand, I get the benefits of a lot of government spending which Malawians don’t: I have subsidized public transport, and reasonably good police, and good roads, and so on. Here’s another fact about consumption levels and happiness. Under most natural circumstances, if you consume extremely small amounts (like$1 a year), then you aren’t extremely sad, you just die from hunger or exposure. In fact, the consumption levels at which my happiness function predicts your life isn’t worth living is actually pretty close to where I’d imagine that you’d die from hunger if we were really adjusting for PPP correctly. This is either incredibly interesting or a surprising coincidence. I am interested in hearing speculation about this.

The variability of consumption also plays into this. If it costs you a dollar a day to not die of hunger, then if your monthly consumption has a standard deviation of 50c per day, I suspect you’d die in a few months. So even if the lowest survivable level of poverty is bad enough that your life is barely worth living, perhaps not many people will live at that level of poverty for long.

My co-blogger Marie points out that another way of estimating this would be to look at the mortal risks people take when they are starving. We could look at situations where people had a choice between remaining in a place suffering from famine, or doing something extremely dangerous to escape. She points out the example of post-war Vietnam, where the South Vietnamese who tried to escape faced about a 50% chance of death and tried to escape anyway, partially because they were so enormously hungry. One particularly good way of estimating this would be to look at neighboring regions where escaping is roughly as risky but the levels of famine were different, and comparing the rates at which people tried to escape. There would obviously be a million confounders here, like how unpleasant the regime was or how much people expected the situation to improve, but we might get some useful data regardless.

That’s all been trying to estimate $k$ by looking at happiness at the lowest end: how about if we try to estimate it by looking at how much a 10% change in consumption changes happiness in a nation? This has fewer philosophical issues, so I’m not going to discuss them. This way of indirectly estimating $k$ is closer to how we’re going to estimate it in the next section.

You also might be interested in looking up the paper which had happiness as a function of consumption within particular poor countries, then trying to solve for $k$ within that much smaller and easier to measure range. However, this requires making a judgement call about how to translate the descriptions of happiness into real numbers. Depending on your feelings, this judgement call might be worse or better than what I did.

## Numerically estimating $k$

Here’s a few data points to use to estimate $k$:

• A few weeks ago I was talking to this dude who grew up in poverty in Mexico and illegally immigrated to America when he was 12. We chatted about his previous quality of life for a while: not getting enough food, only getting one pair of shoes a year, and so on. My impression is that his life in Mexico seemed about half as worth living as his life here is. From his description of his quality of life, and my understanding of Mexican poverty, I would guess he was living on maybe $4000 a year. I wish that I’d thought to ask him for a numeric statement of how much better his life here was, but I didn’t think of this. Next time. • Slate Star Codex did a survey trying to calculate the relative quality of life in different situations. Respondents thought that Ethiopian life is 50% as good as American life, and Chinese life was 85% as good. I’m a lot more averse to poverty than SSC readers, apparently. From these we get an average estimate of $k$ as about -2.2. This number is low enough that nations with average consumption PPP less than $10^{2.2} = 158$ are classified to have a negative quality of life. I think this is stupid. I removed the China data point because I think that the people answering the Slate Star Codex survey overestimated how rich China is. I vaguely recall the survey implying that you lived in a city in China or something, as opposed to living in rural China as 50% of Chinese actually do. Overall, I think that this model of happiness as logarithmic in consumption is good but gives bad results for extremely poor countries, because we are underestimating the consumption of extremely poor people. ## Application to global poverty charities One interpretation of these numbers is “the price at which we are indifferent to decreasing total consumption by that much to save a single life”. Another interpretation, though, is “the price at which saving a single life is better value for money than just increasing consumption by that much”. This is really important, because as philanthropists we have the option of doing both of these things, most obviously through GiveDirectly and AMF. Let’s quickly review the levels of poverty of the people affected by these programs: AMF operates mostly in Malawi and the DRC. Bednet distribution is slightly cheaper in Malawi. Malawi has a GDP PPP per capita of about$226. Apparently, this is pretty unevenly distributed. So the people saved by AMF, who I think mostly live in rural areas (from looking up regions listed here), are probably poorer than average for Malawians. (AMF’s distributors seem to find that most of the houses they look at need LLINs (Excel file), so we don’t need to worry about saving unusually poor people among rural Malawians.)

Kenyans who receive GiveDirectly grants have a median nominal consumption of $0.55 per day. (I use median instead of mean because I suspect that log(consumption) is more normally distributed than consumption; this is suggested by the mean being higher than the median.) The nominal-to-PPP conversion for Kenya seems to be about 2.18 (from comparing nominal and PPP GDP estimates), so that’s yearly consumption of about$408. This is almost twice Malawi’s mean consumption, and as I said above the Malawians saved by AMF are probably poorer than above. Obviously, these numbers are so bad that they’re almost useless. The Malawian consumption estimates here try to include sustenance farming, but it’s really hard to get that right. According to the table on page 24 of this report, Malawi’s proportion of undernourished people is 23.1% while Kenya’s is 30.4%. (Undernourished means that you are below the “minimum level of dietary energy consumption”.) These numbers kinda look like they fit with my hypothesis that GiveDirectly recipients have pretty similar levels of consumption to Malawians saved through AMF.

We’ve got a plethora of extra factors in this particular case. To start with, maybe there are flow-through effects of cash transfers which case them to increase consumption more. Also, bednets have other positive effects than saving lives, like preventing developmental impairments from malaria that limit lifetime earning potential, preventing malaria death in the above-5 year old age group (which isn’t counted) and prevention of other mosquito-borne illnesses. And having a marginal human might increase the consumption of other people in their society in some situations, but I don’t know which situations that is. Also, GiveDirectly might save lives as well, by giving people money to buy things like medicine and medical care and better food, or indirectly by allowing people to get e.g. metal roofs and thus having better hygiene in their houses.

I think that my formula is totally useless for answering the question of how much we should be willing to spend per life saved by AMF if our alternative is giving to GiveDirectly, because it’s so sensitive to changes in my $k$, and estimating $c$ is also really hard for super poor people. However, I did get some feeling about it from doing the research into poverty in Malawi and Kenya I did to write this discussion section. The people whose lives you save by giving to AMF seem to be pretty intensely impoverished. If 30% of Malawians are undernourished in general, and people saved by AMF are unusually poor, I suspect that probably a majority of the lives saved there are undernourished. That means that these people feel hungry all the time. I have a lot of sympathy for the perspective that those lives sound perhaps not worth living, in which case making them better is the better option. I also think it’s pretty plausible that these lives are actually pretty okay.

GiveWell has obviously thought about how to compare saving lives to increasing consumption, but AFAICT they haven’t considered it this explicitly. In 2012 they said that they suspected AMF was a much better deal than GiveDirectly. However, GiveWell hasn’t tried to quantify the value of increasing consumption vs saving lives like I have here. They probably haven’t tried because it turns out that when you do, you get shit results, as I did above.

Carl Shulman has also written about happiness as log of consumption and GiveDirectly before.

If I donated to global poverty causes, I really don’t know which of these I’d give to.

## Conclusion

The value of saving a life increases linearithmicly with consumption. This is neat. I am pretty sure this is correct, and I’m really happy to have a principled derivation for it.

I think my equation for the value of saving a life is quite good for richer countries where it’s easier to measure consumption. Maybe one day, we will have ended global poverty, and the $\Delta c = c t (\log c + k)$ equation will be actually useful when we’re trying to decide whether a particular hovercar safety measure is worth it.

# Bible Study Survey

In the coffee shop, a lady approaches.

“Do you have a few minutes to help me with a survey about religion?” She’s non-threatening and wrinkled and somehow I don’t feel like escaping with using my usual, “I don’t want to talk to people right now” line. I say sure, and she seats herself across from me, introducing herself as Angel. She spins around a tablet showing a picture of the world, burning.

“What do you think of when you see this picture?”

“Global warming?”

“So, do you think the world will end because of global warming?”

“If you mean end by all humans dying–” She nods. “Then no, but I think humans will end themselves unintentionally before too long anyway.” Heh. “We already came really close with bombs once! And we’re developing new technology so quickly, so it could be bioterrorism, nanotechnology, artificial intelligence, or stuff we haven’t thought of.”

Angel’s face remains neutral. “Do you think it makes sense for religious people to believe the world will end?”

“If they take the… stuff… seriously, then sure?”

“But have you considered that the Bible isn’t literal, and this is a misinterpretation, and really the Bible is a collection of parables?”

“Yeah, like, I actually just think people wrote it and it’s definitely not the literal history of the world and what morals should be.” This isn’t anything like a survey, but it’s free of conversion attempts and vaguely information seeking. I wait for another question, but apparently, Angel doesn’t have more questions for me. I have one for her. “I’m curious. What was this survey about?”

“We’re making a new Bible Study group to help fix misconceptions like thinking the Bible is literal and that the Bible says the world will end.”

“Cool! Well, I think the world will end anyway, but I guess I’m unusual. Thanks, Angel.”

Happy to help.