Not Your Grandmother's Textbook Exercise

https://cacm.acm.org/blogs/blog-cacm/264263-not-your-grandmothers-textbook-exercise/fulltext

by zdw • 4 years ago

244 121 4 years ago

cacm.acm.org

umanwizard• 4 years ago

Presumably the list is not ordered adversarially, so you can just use quickselect, at O(n) running time.

pjscott2• 4 years ago

My personnel records are always ordered adversarially, on general principle. :-)

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.

tantalor• 4 years ago

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

naniwaduni• 4 years ago

I wouldn't really expect your personnel ages to leave the range of an unsigned octet in the foreseeable future. Hell, I'm pretty sure we're not expecting to have personnel exceeding 127yo anytime soon.

(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!)

exact_string• 4 years ago

You can use the median of medians with quickselect to guarantee the O(N) time complexity.

totoglazer2• 4 years ago

In that book in 1981 it’s quite likely to be a problem faced by the grandmother of many current programmers.

SamBam• 4 years ago

That's why it's Not your Grandmother's Textbook Exercise.

totoglazer2• 4 years ago

Maybe it’s just poorly tilted then? This literally IS. I guess they are trying to imply other problems aren’t? But that would apply to some other theoretical question not mentioned here…

akudha• 4 years ago

Compute the mean age, and print it out as the median. It's much easier to program, and Mary Jones will probably never notice the difference.

This made me chuckle

popotamonga2• 4 years ago

Customer only realizes 5 years later and you put the blame the customer for not discovering it earlier.

harry8• 4 years ago

It's an excel file.

(e) Show her the excel function wizard and launch her empowerment for great justice!

0823498723498722• 4 years ago

Interesting finding in the post referenced by TFA:

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.

cxr• 4 years ago

I'm partial to John Ousterhout's "The greatest performance improvement of all is when a system goes from not-working to working".

<https://web.stanford.edu/~ouster/cgi-bin/sayings.php>

kungfufrog• 4 years ago

Where's the option to start firing up a Kubernetes cluster?

analog31• 4 years ago

Also, how long would it actually take to sort a number of records consistent with the largest workforce today?

0823498723498722• 4 years ago

3e6 employees all of whom were born after 1768? <1s?

bobsmooth2• 4 years ago

A quick Google search says Walmart has 2.3 million employees. Using python to generate 2.3 million random age and name pairs and then sort them took about 8 minutes. And I'm pretty sure most of that time was spent creating the array.

xelxebar• 4 years ago

Dyalog APL is fast:

    ¯1↑5e6↑{(⊂⍋⍵)⌷⍵}10e6?⍤⍴100

This finds the median of 10 million "ages" in just under 50 milliseconds. Granted, with this randomly generated data it's probably doing something smart to avoid a full 10MB allocation, so on a static dataset the performance might be a bit different.

pjscott2• 4 years ago

Since this is from the 1980s, would a VAX cluster suffice?

retcore• 4 years ago

A high volume transaction concurrency capable routine scenario would make a good update for contemporary financial services. Delta median and tick moving average strategies eg for thought. Also, how to recalculate for cancellation, hot fill or kill and other execution strategies.

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.

zeristor5• 4 years ago

Surely the best of both worlds would be to run Vax on Kubernetes?

popotamonga2• 4 years ago

(x) find and npm package and question nothing, whatever happens happens. If it fails blame the author.

insane_dreamer• 4 years ago

(e) introduce Mary to Lotus 1-2-3

wzwy2• 4 years ago

Woah, flashback to was it Crossing the Chasm or Inside the Tornado?

I’m not sure if the latter has an updated version, so it’s probably that.

wzwy2• 4 years ago

(d) Compute the mean age, and print it out as the median. It's much easier to program, and Mary Jones will probably never notice the difference.

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.

deanmen2• 4 years ago

Excel has MEDIAN built-in https://support.microsoft.com/en-us/office/median-function-d...

sbierwagen• 4 years ago

You can also install the Analysis ToolPak add-in, select the column, click Data -> Data Analysis -> Descriptive Statistics. Gives mean, median, mode, SD and a bunch of other things. https://support.microsoft.com/en-us/office/use-the-analysis-...

Has been in Excel since 2007.

cwillu• 4 years ago

The problem states that Mary has an Excel file. It does _not_ state that Mary has an Excel software licence, or even a computer with which to run it.

bambax• 4 years ago

It's not just Mary Jones. The controversial (to say the least) French medical professor Didier Raoult last year showed he didn't quite grasp the difference between median and mean. There was some mockery on Twitter but no journalist ever called him up on it.

brutusborn• 4 years ago

I couldn't believe an Academic could be this ignorant, so I had to look it up. I found it but only basic french. I can't find a translation, does anyone know of one? https://mobile.twitter.com/cubic_logic/status/15410902478613...

pjc50• 4 years ago

Quite difficult now to reach this scale with personnel records, but: imagine that you're asked to provide the median of one trillion data points. This could provide lots of interesting possible approaches, since it's about the boundary between "big data" vs "do it on your laptop". And you can't just load it into Excel.

(and also to ask about the range of the data!)

raverbashing• 4 years ago

For 1 trillion records I'd say: estimate the probability distribution and values and give the corresponding value as the answer

nmstoker• 4 years ago

For a trillion records, if you were in the UK government, you might just drop those above the Excel limit and proceed until journalists flagged the concern nationally.

Background context here:

- https://www.theguardian.com/politics/2020/oct/05/how-excel-m...

Psyladine• 4 years ago

re: (e), they can't. I don't mean they cannot physically operate the sequence of events (even a properly incentivized chimpanzee could do that), but that they lack the programmatic sense of problem solving that is assumed (quite arrogantly) by the programmatic crowd.

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).

Ma8ee• 4 years ago

No, it’s not that they don’t think they can do it, it’s that one of the foundations of modern economics is specialisation. I know I can repair my car myself, and even think it would be kind of fun. But the mechanic in his shop already knows exactly what to do and in which order. I’d spent hours reading and watching videos before I even could start and still make plenty mistakes. The mechanic already has the tools and know where to source the parts. I’d spend half a day just to make sure that I’d get the right parts to a reasonable price. In the end it would take me four days what the mechanic would do in an hour or two.

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.

sinuhe69• 4 years ago

Wow! I love the old school time where text books stimulated you to think broadly and deeply. Not just solving some artificial tiny problems and let you think when you can solve them all, you’re on the top of the world.

wrycoder• 4 years ago

If there are any boxes of greenbar sitting around, it’s C A B D.

Otherwise, A C B D.

jenaimarre• 4 years ago

We almost agree, I would go for D, A, C, B :-)

mgaunard3• 4 years ago

ACBD is clearly the right ranking.

deanmen2• 4 years ago

If it is indeed an Excel spreadsheet MEDIAN is a built-in function

https://support.microsoft.com/en-us/office/median-function-d...

vlovich1235• 4 years ago

The exercise is a bit weird. 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. 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)

This is ~1.6x faster than the variant that uses sort with a custom key that someone else posted. If you simplify it into an array of numbers, it's still 5-10% faster on my machine than sort (i.e. comparing pure native code running sort vs running radix sort in interpreted Python).

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

Liru• 4 years ago

I had to reread this comment multiple times since I felt that I had a fundamental failure of reading comprehension somewhere along the line.

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?

vlovich1235• 4 years ago

You’re right. I was looking at option A. Therefore radix sort is strictly the right answer. Simple, easy to read, easy to understand and an order of magnitude faster.

bisby• 4 years ago

Indeed. The question asks you to rank responses. Furthermore,

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.

gumby• 4 years ago

Seriously, interviewers should ask these kinds of questions, not leetcode.

zeristor5• 4 years ago

The question sort of answers itself as you read through the options, but then that can’t be taken for granted.

Attrecomet• 4 years ago

Yes, in a world where fizzbuzz is a useful filter for advanced software developer positions, I'm pretty sure this would also help.

layer83• 4 years ago

The task is to evaluate and discuss the options, which would be the valuable part in an interview.

corpMaverick2• 4 years ago

Simple leet code questions are good to find out who can think algorithmically. But once people catch up they are not longer useful since you can study them and memorize them. Then the leet code questions need to be more difficult and it becomes a race. Now you are obligated to study them even if you are already a practicing Software engineer.

Same thing would happen to these questions. People would memorize them and answer not on experience or intuition but on memorization.

zwkrt• 4 years ago

Five hours and no one has actually attempted to answer the question as far as I can tell.

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.

jamesrom• 4 years ago

I like A, as it iterates toward C anyway.

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.

zeristor5• 4 years ago

“Just go away and write the code”

samuel• 4 years ago

A) is the right *business* answer the 99% of the time, assuming you have a fast routine for sorting an array but not one for computing the median directly.

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.

mattkrause4• 4 years ago

I'd cheat in a slightly different way.

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).

abrax31413• 4 years ago

Just report 38.8 years, the median age for us population as reported by the census. Mary won’t notice, it’s scalar in time and space, and in the limit you’ll be correct.

vlovich1235• 4 years ago

It’s actually currently 42 For what it’s worth (went up 2 years in the last decade).

abrax31413• 4 years ago

Oh. And it can be engineered at minimal cost (although all the test writing will require 2FTEs for 6months). UnleSS you write it in Haskell, in which case tests are unnecessary, but it’ll be 3FTEx2yrs to send the engineering team to a monastery to learn how to tie themselves into the appropriate monadic knot.

zeristor5• 4 years ago

42!

thinkingemote• 4 years ago

These are personnel records - people who are working at least (16-64 years) so not the total population. Will be similar though. Depends on demographics.

Additionally, one can assume that there's more younger people working in a company than older and make a little bit more accurate guess.

abrax31413• 4 years ago

Aha! Let’s build a DNN model, train it on all the occupation data we can scrape from the web, then run it forward to deliver Mary’s result. Once the training is completed, say a year (or, with advances in gpu tech, two years), the forward model can be run in scalar time to confabulate a very convincing wrong answer to any demographic question Mary might have! That way we can fire the whole engineering team because the model will comphabulate answers to any future question Mary might have. (“. . . in the style of a software engineer.”)

jeffrallen• 4 years ago

Update for 2022: (e) import some random code from NPM that turns out to be O(n^2), and has a bug which results in the same output as (d) would have had. Also, it has one dependency that will be deleted with no replacement next month, and another that will be a victim of a supply chain attack the month after 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)?

taylorius2• 4 years ago

(d) Compute the mean age, and print it out as the median. It's much easier to program, and Mary Jones will probably never notice the difference.

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.

eesmith2• 4 years ago

If there is an even number of elements then the median is usually defined as the arithmetic mean of the two middle values. Eg, the median of [1, 3, 5, 7] is 4.

mgaunard3• 4 years ago

I prefer the 2-quantile myself.

taylorius2• 4 years ago

That's true - maybe that gets us off the hook. :-)

qsort4• 4 years ago

Depends on how you define 'median'.

- 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.

hhmc2• 4 years ago

Also, the median can only be 1stddev away from the mean in any distribution, so this can further winnow the search.

mjburgess2• 4 years ago

...this isn't true:

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10^30

smeagull• 4 years ago

They're ages, and therefore integers over a tiny range. You ignore these solutions, and insert the counts of values into a tiny dictionary, and compute the median from that.

wikfwikf2• 4 years ago

The right answer.

mojomark• 4 years ago

I think the point is being missed here. This response does not answer the direct brief nor the (more important IMHO) underlying question that attempts to excercise empathy for the customer:

"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?

layer83• 4 years ago

Maybe they want the median age in number of days?

mattkrause4• 4 years ago

Assuming Methuselah doesn't work for you, you can still do that in about 200k of memory.

evolvingstuff• 4 years ago

Maybe I'm missing something obvious, but this seems like a way to calculate a mode, not a median.

xanathar• 4 years ago

I think the idea in parent post is: fill the dictionary (I would use a 200 entries array though), iterate over the keys in sorted order summing the values, stop when you are at N/2. The 'iterate over keys in order' part depends heavily on the data structure choice of the dictionary (good for treemaps, bad for hashmaps, best for preallocated array).

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).

andrepd• 4 years ago

(b)

Many languages like C++ have this algorithm built in. Code reuse is amazing!

pcblues3• 4 years ago

I love this so much. I know what I should do, and yet my conscience will make my final decision more expensive for the company I work for. Should I be fired for that?

pcblues3• 4 years ago

I would also try to find a way that didn't involve programming. Less bugs.

duxup• 4 years ago

Spend a couple of weeks attempting (unsuccessfully) to improve on Floyd's algorithm, a day programming Floyd's algorithm, and then return to Mary Jones with some questions on the size and format of her file.

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?

corpMaverick2• 4 years ago

Take a random sample of 100 elements. Calculate the median from them.

yccs27• 4 years ago

Ooh, I'm getting nerd-sniped here. I wonder how accurate this method is - getting a pen and paper, BRB.

spennant• 4 years ago

With, or without replacement?

tmaly• 4 years ago

I can remember learning OO with Eiffel.

Not Your Grandmother's Textbook Exercise

Related Stories