Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A software engineering interview question I like: computing the median

krisshamloo.com

Post reply on HN
Print view View original

81–90 of 97 posts

Re: A software engineering interview question I like: computing the median

#81

Post by bigiain »

Induane wrote: post #73
bigiain wrote: post #43

Earlier quoted context omitted.

Is that really a "more applicable" task that finding the median? Are there actually software development jobs where either of those tasks are a regular/common part of the work, where people don't "just know" how to do them using whatever tools the job already uses? I'm guessing I'd flunk your interview, because my initial response would be something like "No, I wouldn't write code for that. Unless there are unstated…

That's a good solution using existing tools, but I usually want it solved in whatever programming language is being tested. Not because command line tools aren't often an underutilized solution but because I am looking for their tendencies. Do they reach for a hashmap? Can they calculate it all in one pass? That kind of thing. As for the why, it covers a class of issue that does come up; counting like items. Determin…

Yeah - I think we're on the same page here?

If I'm interviewing at a Python shop that actually does statistics t=ype stuff or text munging, I'd expect them to have preferred/existing solutions for these tasks in their standard dependencies. And if it were a Javascript/Nodejs shop, or a C/C++ shop, or a Rust shop, they'd also have "standard tooling" that'd be "the preferred option" to anything I could hand roll (either in an interview or during a regular workday).

My "sort | uniq | sort" pipeline (usually combined with grep/tr/awk/sed or similar) is a reasonable answer for an underspecified task with none of the obviously existing but as yet unstated requirements that'd come along with this task is "the real world". It's not an actual proposed piece of production code - it's a way to demonstrate "a" way of doing it without even committing to a language, never mind whatever is in the in house standard set of modules.

If you want to test how find the median in Python, my immediate question would be "what Python modules are you already using? It'd be foolish to invent it myself if the actual codebase already imports numpy or pandas or SciPy. And it's be equally foolish to import one of those if they are already not in use.

(Admittedly, it's been a _looooong_ time since I interviewed for a junior or mid level developer role where leetcode games might be part of the hiring hoop-jumping.)

Re: A software engineering interview question I like: computing the median

#82

Post by dgacmu »

mcmoor wrote: post #71
dgacmu wrote: post #40

> Right out the gate: the numbers must be sorted. But they don't. I hope you, as an interviewer, have the grace to learn when one of your interviewees points out your mistake. :-) Median is O(n), not nlogn

With worst case of O(n^2) though? In hindsight it should be possible, since if we use insertion sort, we also get best of O(n) and worst of O(n^2). Though quick select do have average O(n).

Depends if you're talking theory or practice. introselect is worst case O(n) but a lot of implementations implement it with avg case O(n) and worst case O(log n). Median of medians is worst case O(n) but it's slow so mostly avoided.

Re: A software engineering interview question I like: computing the median

#83

Post by AndrewDucker »

karmakaze wrote: post #65
ycui7 wrote: post #36

there is an algorithm called quick-select. getting median of an array should not require full sort of the whole array, only a partial sort is needed to get the median. quick-select does this.

I just discovered the name of this. I visualized that you can do a quicksort but only recurse one of the partitions each time--the one that contains the median index. It has the same worst-case O(n^2) and can be fixed the same way choosing the median pivot of 3 potential pivots. Apparently C++'s `std::nth_element` uses quick-select and since if you choose a different target index can find any percentile not just the…

I assume that "index" in this case is for the index in the fully sorted list? i.e. if you're looking for the 50th place in a 100 item list, then it's 50th place in the sorted list you want.

But as you don't know what value that is, how do you know which partition it's in?

(I am feeling very stupid today and hoping someone can explain this to me)

Re: A software engineering interview question I like: computing the median

#84

Post by AndrewDucker »

AndrewDucker wrote: post #83
karmakaze wrote: post #65

Earlier quoted context omitted.

I just discovered the name of this. I visualized that you can do a quicksort but only recurse one of the partitions each time--the one that contains the median index. It has the same worst-case O(n^2) and can be fixed the same way choosing the median pivot of 3 potential pivots. Apparently C++'s `std::nth_element` uses quick-select and since if you choose a different target index can find any percentile not just the…

I assume that "index" in this case is for the index in the fully sorted list? i.e. if you're looking for the 50th place in a 100 item list, then it's 50th place in the sorted list you want. But as you don't know what value that is, how do you know which partition it's in? (I am feeling very stupid today and hoping someone can explain this to me)

Never mind, you're keeping the parts that are going to end up in that sorted location. That makes sense.

This visualisation made it click for me: https://www.youtube.com/watch?v=HylYYer2hR4

Re: A software engineering interview question I like: computing the median

#85

Post by Traster »

lubujackson wrote: post #64

This question, and many "but make it a bit more challenging!" comments always strike me as CS101 navelgazing type questions. The best part of this question is that it is simple and can be used to swing into deeper concerns but it is still at odds with actual job responsibilities - even more so with LLMs in the mix. Maybe this is because I have only worked at startups, but I am much more interested in if someone can r…

I think there's two elements to this. First - all the things you list are important too, and we'll get to that. But there's no point in getting to those things if the candidate can't write 5 lines of python and has no idea how the language operates.

Second, hiring at startups is massively different to hiring at big companies. At big companies you have a website and a linkedin and a recruiter and external recruiters and they're all funnelling CVs to you dozens at a time. You're glancing over a CV and if it looks roughly right you'll do a phone screen. People lie on their CVs. So you need a few questions like this just drop the 90% of candidates who have literally no chance at getting the job. Keep in mind, the external recruiters will interview the candidates you reject, find out your interview questions, find the answers and tip off future candidates.

We're also hiring for a different set of skills. At a start up everyone is doing everything. Does it matter how well you can talk to customers? Maybe! That could be useful. In a large company if you ever talk to a customer as an engineer you will have been at the company for years, you'll have a Sales guy, Technical Sales guy, an Account Manager, your manager, and maybe a Project Manager all in the room if you ever get to see a customer.

Re: A software engineering interview question I like: computing the median

#86

Post by Traster »

ta93754829 wrote: post #9

I don't know... I've been coding for ~30 years, and I've never had to write code to compute the median so it doesn't seem that useful unless it's somehow relevant to the job

I'm not certain the point of an interview is to ask you to write the exact lines of code that you would write during the job.

Re: A software engineering interview question I like: computing the median

#88

Post by ismailmaj »

gedy wrote: post #75
ismailmaj wrote: post #18

Earlier quoted context omitted.

I got that recently, I really didn't like that question. For the n-th percentile version, the obvious solution is sorting and it takes 10 seconds to get to that point, 5 minutes of implementation with tests. Good. It's all downhill from here. Then you get hit with the "it's a data stream" and you realize you have to implement a balanced tree on the spot which I wouldn't describe as fun. You may or may not be able to…

Please tell me this was not interview for a SaaS CRUD app role

I don't know what the day to day would be like but it was a ML research engineer role.

Re: A software engineering interview question I like: computing the median

#89

Post by verelo »

rokob wrote: post #60
verelo wrote: post #35

Earlier quoted context omitted.

So for about 10 years my main interview question was: "Write me a function in any language of your choosing, that takes an array of integers and returns the sum." I loved it. Here is why: 1. I'd get to see them write code, in a low pressure way, but they'd have to write something 2. A shocking number of people would struggle to write the code. That was my signal to end the interview early. 3. I'd get to ask "So tell…

I used to do phone screens with a similarly simple question. I am still blown away that something like 60% would fail to write working code. I had more parts for the 40% that got it the first one, but it was crazy how many people couldn't do the most trivial task.

That success rate aligns with mine. I was also shocked, at first.

Re: A software engineering interview question I like: computing the median

#90

Post by dgacmu »

dgacmu wrote: post #82
mcmoor wrote: post #71

Earlier quoted context omitted.

With worst case of O(n^2) though? In hindsight it should be possible, since if we use insertion sort, we also get best of O(n) and worst of O(n^2). Though quick select do have average O(n).

Depends if you're talking theory or practice. introselect is worst case O(n) but a lot of implementations implement it with avg case O(n) and worst case O(log n). Median of medians is worst case O(n) but it's slow so mostly avoided.

* introselect implementation often worst case n log n, typo
Post reply on HN