Not Your Grandmother's Textbook Exercise
cacm.acm.org
cacm.acm.org
Lol. If it’s not the most important statistic to Mary Jones, I can see why a programmer might do this.
> Mary Jones in the Accounting Department tells you that she has a file of personnel records [2022 update: an Excel sheet] and asks you to develop a program to compute the median age of the personnel in the file.
I’ll probably add option (e) if it’s Excel: Mary Jones, you can learn and do this yourself. Just Google it or something.
Has been in Excel since 2007.
FR: '[...] d'objets de mettre ensemble. Vous voyez que si on regarde la moyenne ou la médiane, la moyenne c'est quand une distribution est comme ça, on peut faire une moyenne, quand elle est comme ça on n'a pas [...] pour faire une moyenne, on fait, le, le, le, la barre qui sépare à moitié les uns les autres. Et donc [...]'
There's a short phrase I can't quite catch at about 9s... which literally translates as 'we don't have [...] to do a mean', so I'm inferring that he means 'you can't calculate a mean' from context (previous clause 'on peut faire une moyenne' => 'we can do a mean' => 'we can calculate a mean').
HN's guidelines recommend to assume the best.
1. If data is multimodal (wiggly line), the median isn’t a great measure of central tendency either.
2. Perfectly normally distributed data will have the same mean and median.
I agree people have jumped on this as evidence the guy doesn’t understand when he probably does, but what he says is a long way from the truth.
(and also to ask about the range of the data!)
Background context here:
- https://www.theguardian.com/politics/2020/oct/05/how-excel-m...
In the same way people take their cars to mechanics when they can do the job themselves, or call triple A for a flat tire when the spare and jack are in the trunk, or reach for the phone instead of a plunger when the toilet backs up, people don't lack the specific skillset, they lack the openness to problems being solvable. They are in perpetual search of answers, not solutions.
They don't want to learn to fish, they don't want to expend energy on process. They want someone else to do it. It's not laziness, it's not incompetence, and it's not entitlement. They are just of a mindset they cannot solve problems, and so they pick up the phone and abstract away the answer.
And I promise you, no 10 minute condescending conversation with someone is going to redefine their core attitudes about life. You're just going to have your well poisoned in the break room with your piss poor attitude because she called the plumber and he told her to fix her own shit (in a manner of speaking).
And I buy my fish in the supermarket, for even more obvious reasons. This example make me believe you actually might be trolling.
So the lady in the original examples uses that the company already employs people who are specialists in doing this kind of things, Because she has more important things to do with her time. And that you don’t understand what she’s doing all day that make her not having time for fighting with spreadsheets is your failure, not hers.
> In other words, you can throw money at a project to make things happen faster, but the highest time reduction you will ever be able to gain is by a quarter. Such a result, confirmed by many studies (by Boehm and many others after him), is typical of the kind of strong empirical work that Boehm favored.
If I was Mary I would probably want A. As a programmer I would tend toward C becuase I have been burned by not questioning requirements before. If Mary were me (so to speak) I would hope she asked me such questions, but most people giving requirements get annoyed with too much hair splitting, at least hair splitting from their perspective.
You can deliver value with the naïve implementation delivered quickly.
If Mary Jones has further requirements that were not considered at the outset, now she'll be able to consider them.
Conversely, if you've built a bunch of assumptions into your code, they'll be tested in the real world sooner rather than later.
Mary shouldn't care about a) vs b) unless she has to wait too much to get the answer. If she has, then her need has to be weighted against other business needs, so the data gathered in c) becomes relevant. b) then becomes one of c's aftermaths.
d) is dishonest
So it is a) -> c)
I wouldn't go directly to c), a) is cheap enough.
If the data are employee ages, you know that they are probably integers[0] and certainly bounded between 0 and 128.
Bin the ages into years and accumulate the per-year and total counts, which is a snap: O(N) time, O(1) space, and trivial to parallelize. Find the bin where the cumulative sum is equal to half the total counts and you're done.
[0] Even if they're not integers, you probably don't need ages more granular than a day, which is still a manageable number of bins (~50k).
"Rank the responses in the order of their relative concern with programming considerations, economic considerations, or other important considerations. If you were the programmer, which approach would you prefer? If you were Mary Jones, which approach would you prefer?"
After 20 years in industry, I constantly see people banging their heads against the wall, not understanding why the customer "doesn't get it," when in many cases they do in fact "get it" but the solution has different meaning to them. The complex challenge is identifying all of their underlying motivations and viewing the problem from their perspective.
Empathizing with the customer is the lesson, not the math. It's important because it makes for a happier professional relationship and if you're technically right, knowing the customer's drivers can help you efficiently negotiate the implementation path forward in a way that everyone is satisfied with and garuntees more future business. The lesson teaches a path to professional happiness, and that's invaluable. Who wants to be grumpy and angry 80% their life?
In fact, in this case, it is not difficult.
Going back to a professional who has requested the median and asking them if they didn't actually want the mean is not a display of empathy. It is patronising. The gender of the stakeholder is perhaps of relevance here.
You certainly shouldn't sneakily make the substitution. However, making a "client" aware of options and the associated trade-offs is very reasonable. Heck, I'd say it's the most professional approach to this problem!
It may be that Mary just needed some measure of central tendency, and would be happier with the mean now versus the median in a week. Alternately, she might need the median specifically for some legally-mandated reporting, and only that will do. You'll never know if you don't ask.
I wouldn't. I have seen first-hand so many projects that took weeks of efforts, because we assume the person making the requirements used perfect language, when they could have been done in a day instead. One word can be the entire difference.
Maybe it happens to you in a big company: "the VP said '...'", so you must do exactly as the VP said. In practice, it turns out that the VP, just like Mary, could easily agree they didn't care if it's median or mean, they just need some number that summarizes the data.
Understanding the customer is key.
MacBooks have something like 192 kb shared + 128 kb/core, so that should be okay if not much else is going on....
Incidentally this falls in the 'sort an then pick the middle' because the original text says nowhere that is must be a n*log(n) sort and what I described here is essentially the same but with counting sort (and a couple redundant steps removed).
This made me chuckle
x = [(randint(20,80), "John Smith") for x in range(2_300_000)]
x.sort(key=lambda x: x[0])
x[2_300_000//2]
In short: this is something you shouldn't even think about in modern computers since it's that fast.
In this day and age it would be like trying to sort 100 TB of data. Not a hard problem, but not exactly something you do daily either. And still dreadfully slow since you need to use disk memory while copying everything over.
A more modern version of the question would be:
>You have a list of integers, in random order, that is 20 times larger than the hard drive you have on your work station and 1,000 times larger than your work station ram....
The intent behind the problem in the textbook is fine - think non-linearly about the problem. Just the example used has a trivial solution not mentioned (i.e. option 5).
You're also assuming integer ages when a more natural comparison would have date of birth. Which has 365 times the number of buckets. Something that was again problematic to fit into a 1980s memory.
¯1↑5e6↑{(⊂⍋⍵)⌷⍵}10e6?⍤⍴100
The original question can get you thinking very close to contemporary problems, with only modest variations. We should have more longevity built into our textbooks.
(e) Show her the excel function wizard and launch her empowerment for great justice!
Same thing would happen to these questions. People would memorize them and answer not on experience or intuition but on memorization.
Possible improvement: The median will always be a member of the actual dataset, so after calculating the mean, run through the data to find the entry which is closest to it, and return that for the "median". Could make our dastardly plan harder to uncover.
- Any value that minimizes the sum of absolute differences? Then all real numbers between 3 and 5 are a median of that set.
- With an inequality over the PDF? The same as above.
- The 1/2-quantile? Then you need to tell me if we're rounding up or down.
I've seen that definition before, but it's a completely useless definition for any legitimate use case of the median as an order statistic. I have no idea where it comes from.
For example, names can be ordered alphabetically, so you can find the median of a set of names! OK, that's a silly example, but I expect someone could come up with a more sensible one.
Another case might be where you're using geometric means everywhere else in your working, but then you want a median in one place, but there are an even number of elements, so why would you suddenly use an arithmetic mean of the two middle elements?
- Imagine you hand out a survey where some answers are on a likert scale. "strongly dislike" is worse than "dislike", which is worse than "neutral" and so on.
- The median ranking over a set of ranking on different criteria.
- When the domain is not the real numbers. "The median employee of this company has 1.5 kids".
It's also the definition that I was taught at school.
Oxford Languages defines it as: "denoting or relating to a value or quantity lying at the midpoint of a frequency distribution of observed values or quantities, such that there is an equal probability of falling above or below it", which also supports the idea of taking the midpoint between the two middle values.
Merriam Webster define it explicitly in the way OP does (arithmetic mean of the two middle values): https://www.merriam-webster.com/dictionary/median
I'm not sure why you think it's a 'completely useless definition'. It would perhaps be a logical argument that data sets of even length do not have a median, but I think this would be even more useless.
To the layperson (which Mary Jones undoubtedly is), providing the 'median' age as an age half of the employees are older than/younger than, is what would be expected. Your first bullet point makes sense here. For example here:
18, 20, 25, 30, [35, 40], 45, 50, 55, 60
Most people would expect the median to be calculated as 37.5. However, as you mention, any real number higher than 35 and lower than 40 would equally fulfill the definition of 'equal probability of falling above or below' assuming this is the full population. Would you then argue that there are infinitely many medians in this data set, or none?
There are other issues with calculating 37.5, such as the fact it implies a higher degree of precision than it ought to. But ultimately, as a practical and usable insight into data, especially data with extreme outliers or high levels of skew, I strongly disagree that this definition is completely useless.
By the definition I usually go by (the one with the inequalities), that dataset has infinitely many medians. There is no reason to say the midpoint is privileged. This is a better definition because it also works on sets where an order is defined but the arithmetic mean is not.
If asked to report a single value with no qualifications, I would report either extreme of the interval.
This is a matter of opinion. I agree it's not 'privileged', but it sacrifices a minimal amount of accuracy for a usable answer.
> If asked to report a single value with no qualifications, I would report either extreme of the interval.
That's a very interesting answer - so for my contrived example of 18, 20, 25, 30, [35, 40], 45, 50, 55, 60, you would report 35 or 40?
How about if I change the dataset a bit (so it's even more contrived): 18, 18, 18, 18, [18, 60], 60, 60, 60, 60 - would you still report either 18 or 60 (again, asking without qualifications)?
I think most people would agree that the median calculated as the arithmetic mean of the two middle values (39) is misleading, but that it is less misleading than ignoring half of the data set. How would you respond to that?
Generally I report the lower end because it more easily generalizes to different quantiles.
> How about if I change the dataset a bit would you still report either 18 or 60 (again, asking without qualifications)?
Yes. I don't see how answering 39 is any better in that case.
> How would you respond to that?
I would respond that you should look at the distribution. Reporting the median is particularly misleading in the case of bimodal distributions. I would try to explain that summary statistics are to be taken with caution, possibly showing a picture.
Fair enough. I think 39 would show there's no bias towards younger or older employees. I think 39 is better but I can see both sides of the argument, and can ultimately see that it boils down to a question of personal preference as to which of two wrong answers is 'less wrong'.
I went to archive.org and searched for intro books in statistics (there are a lot!). All of them gave preference to the average of the two middle values. One of them also pointed out there were valid alternatives.
"Since there are 10 values [in the sorted list], the median is the average of the fifth and sixth values. However, it could be also be 4.1, or 4.9, or any other value between 4 or 5, since each of these values divides the 10 values into two equal groups." - https://archive.org/details/introductiontost0000chao/page/54...
"For a sample of size n, the sample median is the ... Average of the two order statistics in the middle if n is even." - https://archive.org/details/introductiontost0000salv/page/64...
"We find no middle value; therefore, the median is the mean of the two middle values" - https://archive.org/details/US_Navy_Training_Course_-_Introd...
"The sample median for this collection is given by the middle observation if n is odd. If n is even, the sample median is the average of the two middle observations." - https://archive.org/details/introductiontost0000milt_g9m2/pa...
"sample median = ... the average of the middle two values if n is even" - https://archive.org/details/introductiontost0000peck_o4j9/pa...
"If there were an even number of observations (say, six instead of five), the calculation would be more complex. We would need to find the middle pair of numbers (the third and fourth observations), and then find the value that’s halfway between them, by adding the values together and dividing by two." - https://archive.org/details/introductiontost0000haan/page/n6...
"If there is an even number of values, the median is equal to the mean of the two middle values of the ordered set." - https://archive.org/details/introductiontoec0000merr/page/18...
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10^30
I read …, 1, 10, 30 but …, 1, 10^30 is far more dramatic.
| u - m | = |E(X - m)|
<= E(|X - m|)
<= E(|X - u|)
<= E(sqrt((X - u)^2))
<= stddev
fit N(u, s) to {(x, y)...} then m will lie u+-s
rather than, def. s^2 = E[X^2] - E[X]^2
https://support.microsoft.com/en-us/office/median-function-d...
Additionally, one can assume that there's more younger people working in a company than older and make a little bit more accurate guess.
I like to think this is hinting that you should have asked first and maybe her answer is that she has a small number of records and if you took that option B you just wasted a few weeks.
Right?
But if you’re willing to assume that none of the ages are more than some reasonable constant bound, like no employees over the age of 65535 or something, then there’s a fun guaranteed O(n) algorithm closely related to counting sort.
There's the right answer right there.
I'll add: let the AI handle the details.
def getMedianAge(person_list):
# Let copilot fill in rest(Note, however, that counting occurrences is in principle at least O(log n) space and, without a bit of cleverness, likely O(n log n) time—your integers need to be O(log n) wide to count that big!)
I’m not sure if the latter has an updated version, so it’s probably that.
Supplemental question (for "software ethics" option students): If you've got 3 emails from recruiters waiting replies and you're 50% sure you won't be in your job in 1 month, does that increase or decrease the desirability of option (e)?
So answer to the question posed? None of the above. One can make a simplifying observation that ages are all < 255. I'd then use a radix sort.
from random import randint
from time import time
x = [(randint(20,80), "John Smith") for x in range(2_300_000)]
start = time.time()
ages = [0] * 256
for entry in x:
ages[entry] += 1
for age, count in enumerate(ages):
total += count
if total >= 2_300_000//2:
print(age)
break
print(time.time() - start)
If you converted this to native code I'm sure this would be over an order of magnitude faster, both because O(N) is faster than O(n log n) and because you're doing a linear scan through the records (just jumping randomly around within a 255 byte array which can be 1 cache line on some CPUs). Indeed, when I compare this in native code [1], on my machine it's 3ms for radix sort processing of 2.3M records vs 77ms (~25x faster). When run with -O0, it's 24ms vs 724ms (~30x faster).
If I needed to find the actual record for the median employee(s) (there can be more than one obviously), I'd just scan over the data linearly a second time which should STILL be faster [2] (in the benchmark it's still 7x faster than comparison sort).
[1] https://quick-bench.com/q/Bra8T5nv9nFzgUUUKxjVLNCie6I [2] https://quick-bench.com/q/CN0WBMpyICM2ZwnwgQadBX3cPj4
> The problem statement says "find the record" but all the answers are about printing the median age.
> So answer to the question posed? None of the above.
The problem statement does not say "find the record". The problem statement says, fully quoted:
> Rank the responses in the order of their relative concern with programming considerations, economic considerations, or other important considerations. If you were the programmer, which approach would you prefer? If you were Mary Jones, which approach would you prefer?
> The problem statement says "find the record" but all the answers are about printing the median age.
No. it doesn't. It asks you to "compute the median age" without asking about any records.
> she has a file of personnel records [2022 update: an Excel sheet] and asks you to develop a program to compute the median age of the personnel in the file. Here are four different ways you might respond:
So the textbook asks you to rank possible ways to respond, and the hypothetical is just asking "can you process this list and tell me the median age". No one in any context is asking for a record.
Many languages like C++ have this algorithm built in. Code reuse is amazing!
Otherwise, A C B D.