12 ms·
Not Your Grandmother's Textbook Exercise
- School-Cotton 4y agoPresumably the list is not ordered adversarially, so you can just use quickselect, at O(n) running time.
- pjscott 4y agoMy 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 4y 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 4y agoI 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 4y agoYou can use the median of medians with quickselect to guarantee the O(N) time complexity.
- totoglazer 4y agoIn that book in 1981 it’s quite likely to be a problem faced by the grandmother of many current programmers.
- SamBam 4y agoThat's why it's Not your Grandmother's Textbook Exercise.
- totoglazer 4y agoMaybe 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 4y agoCompute 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
- popotamonga 4y agoCustomer only realizes 5 years later and you put the blame the customer for not discovering it earlier.
- harry8 4y agoIt's an excel file. (e) Show her the excel function wizard and launch her empowerment for great justice!
- deleted 4y ago[deleted]
- 082349872349872 4y agoInteresting 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 4y agoI'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 https://web.stanford.edu/~ouster/cgi-bin/sayings.php>
- kungfufrog 4y agoWhere's the option to start firing up a Kubernetes cluster?
- analog31 4y agoAlso, how long would it actually take to sort a number of records consistent with the largest workforce today?
- 082349872349872 4y ago3e6 employees all of whom were born after 1768? <1s?
- bobsmooth 4y agoA 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.
- thrown_22 4y agox = [(randint(20,80), "John Smith") for x in range(2_300_000)] x.sort(key=lambda x: x[0]) x[2_300_000//2] Takes under a second. You can expand it to generate random names rather than just ages, if you feel like it, but the end result wouldn't be much different. In short: this is something you shouldn't even think about in modern computers since it's that fast.
- vlovich123 4y agoOn my laptop generating it takes ~1s and sorting takes ~280ms. As always, dependent on the power of the machine running things.
- thrown_22 4y agoAfter thinking about it for a while, the reason why it was a hard problem back then is that the payroll wouldn't fit in memory and you'd need to do a sort on disk. 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....
- popotamonga 4y ago(x) find and npm package and question nothing, whatever happens happens. If it fails blame the author.
- insane_dreamer 4y ago(e) introduce Mary to Lotus 1-2-3
- wzwy 4y agoWoah, 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.
- deleted 4y ago[deleted]
- wzwy 4y 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.
- deanmen 4y agoExcel has MEDIAN built-in https://support.microsoft.com/en-us/office/median-function-d0916313-4753-414c-8537-ce85bdd967d2 https://support.microsoft.com/en-us/office/median-function-d...
- sbierwagen 4y agoYou 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-toolpak-to-perform-complex-data-analysis-6c67ccf0-f4a9-487c-8dec-bdb5a2cefab6 https://support.microsoft.com/en-us/office/use-the-analysis-... Has been in Excel since 2007.
- mananaysiempre 4y agoSince 1997 at least (except it’s under Tools there).
- cwillu 4y agoThe 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.
- k_sze 4y ago
- sinuhe69 4y agoWow! 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 4y agoIf there are any boxes of greenbar sitting around, it’s C A B D. Otherwise, A C B D.
- jenaimarre 4y agoWe almost agree, I would go for D, A, C, B :-)
- mgaunard 4y agoACBD is clearly the right ranking.
- deanmen 4y agoIf it is indeed an Excel spreadsheet MEDIAN is a built-in function https://support.microsoft.com/en-us/office/median-function-d0916313-4753-414c-8537-ce85bdd967d2 https://support.microsoft.com/en-us/office/median-function-d...
- vlovich123 4y agoThe 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 https://quick-bench.com/q/Bra8T5nv9nFzgUUUKxjVLNCie6I [2] https://quick-bench.com/q/CN0WBMpyICM2ZwnwgQadBX3cPj4 https://quick-bench.com/q/CN0WBMpyICM2ZwnwgQadBX3cPj4
- Liru 4y agoI 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?
- gumby 4y agoSeriously, interviewers should ask these kinds of questions, not leetcode.
- zeristor 4y agoThe question sort of answers itself as you read through the options, but then that can’t be taken for granted.
- layer8 4y agoThe task is to evaluate and discuss the options, which would be the valuable part in an interview.
- Attrecomet 4y agoYes, in a world where fizzbuzz is a useful filter for advanced software developer positions, I'm pretty sure this would also help.
- corpMaverick 4y agoSimple 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 4y agoFive 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 4y agoI 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.
- zeristor 4y ago“Just go away and write the code”
- samuel 4y agoA) 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.
- mattkrause 4y agoI'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).
- abrax3141 4y agoJust 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.
- vlovich123 4y agoIt’s actually currently 42 For what it’s worth (went up 2 years in the last decade).
- abrax3141 4y agoOh. 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.
- zeristor 4y ago42!
- PebblesRox 4y agoThe median of life, the universe, and everything.
- thinkingemote 4y agoThese 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.
- abrax3141 4y agoAha! 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 4y agoUpdate 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)?
- taylorius 4y 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.
- eesmith 4y agoIf 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.
- mgaunard 4y agoI prefer the 2-quantile myself.
- taylorius 4y agoThat's true - maybe that gets us off the hook. :-)
- qsort 4y agoDepends 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.
- irishsultan 4y agoIn any reasonable definition of what a median is then there is either a unique value, or the mean between the two middle elements is a median, so it's perfectly reasonable to take the average (something which you can always do and gives a unique answer).
- smeagull 4y agoThey'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.
- wikfwikf 4y agoThe right answer.
- mojomark 4y agoI 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?
- wikfwikf 4y agoIf someone asks for the median, you supply the median if possible. The assumption underlying the question is that it is difficult to calculate the median. 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.
- aaron695 4y ago
- andrepd 4y ago> (b) Many languages like C++ have this algorithm built in. Code reuse is amazing!
- pcblues 4y agoI 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?
- pcblues 4y agoI would also try to find a way that didn't involve programming. Less bugs.
- duxup 4y 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?
- 752963e64 4y ago
- corpMaverick 4y agoTake a random sample of 100 elements. Calculate the median from them.
- tmaly 4y agoI can remember learning OO with Eiffel.