ProgrammerHumor
twoPurposes
Discussion
Welcome to the real words, where you just learn to ask the same questions you were asked
The number of people who haven't even heard of fizzbuzz and can't write even the super shitty solution is insane.
I'm pretty certain I can solve it even if you roofied me.
The problem with using fizzbuzz is that people can study for these common problems. If they want to test your skill at solving like issues, you need to design a unique question that has a similar solution logically.
Luckily a decent number of new grads haven't even heard about it because it's not taught explicitly and it isn't in cracking the coding interview, idk if it's on leetcode.
It is
no wonder it's bragged about here. 99% of the stuff disussed here is garbage from leetcode which no dev faces most of the time. if someone tells me he implemented quicksort or fizzbuzz in the company i question their work.
you need to design a unique question that has a similar solution logically.
Pair programming or pull request reviews on production-like code is probably the best. You can include algorithms if it's realistically part of the job.
Reading code is twice as hard as writing it, after all!
Im not even in CS and I know fizzbuzz, its literally synonymous with hello world lol
That's why it's such a good opening question. Normally soft skills>technical experience(at my level), if you can learn shit and talk well you're gonna be fine.
Real life examples:
* Woman with 6 years of xp in Javascript who couldn't write the for loop. Let her flail about for 5 minutes before explaining it to her
* Guy who said "why do you require python skills if you're doing Gen AI."
* Lady who checked divisibility by if(i*3=) and told me that's the correct syntax when I asked her about it.
* Guy who refused to look something up(I think we were doing a different problem), told me chatgpt is better and then proceeded to use a non existent library.
* Guy who got mad at me for saying that the if-elif-elif-else solution is bad and to try and do it better.
Literally if you just describe the rules of the game in English and add a few semicolons you basically have a working python implementation.
Until you do and it backfires because "oh that question is too intense for a group setting"
The cycle of violence.
Sorting algorithms are taught because:
a) They’re basic toy problems that showcase divide and conquer, time and space complexity analysis, and recursion.
b) They show how a computational problem can be implemented in various different ways, and it is essential to be aware of what libs are doing “under the hood”.
c) They are classical, standard, simple, algorithms. A stepping stone for every student that wants to be a computer scientist. Similar to how engineers are exposed to mass-spring-damper models early on.
I agree, but don't expect that I will be able to implement any of them 15 years later without at least reading description on wikipedia
Sometimes the vague idea left in one's brain is enough to get the ball rolling.
Similar to how engineers are exposed to mass-spring-damper models early on.
They don't ask about it in interviews though.
Yep, probably not.
And that is why it is better to ask the candidate to explain them, than to implement.
This is a reasonable take!
It’s really not. I’m a pure mathematician that found his way into CS. Obviously CS is an immature logical science but I’d never quiz someone on the fucking Newtonian gravity equation to evaluate their mathematical literacy because we are ancient scientists who simply defer to the best solution after hundreds/thousands of years of refinement. Instead I’d just ask them things in general and skip the pen and paper other than to just have them outline their thought process. If I’m interviewing a quant I will also give them a general problem and ask how they’d provide a proof for it but from first principles, not shit they can cram before the interview and will never use again.
Well, my comment addressed the “why do I need to know” part of the meme, not the interviews. I too think it’s weird that there is this fixation with 101 algorithms in interviews.
The older I get, the more this becomes my default answer
this might seem like a stupid question, but why don't they let you google shit during the interview? that's what you're gonna do if they hire you, might as well start now
I let people Google when I interview them for that exact same reason.
If anything, I can gain more from seeing how someone is approaching the problem as if they were at work than by imposing unrealistic restrictions.
what i lack in programming knowledge, i make up for in googling abilities
in other words, i'm a bad coder but i know how to type in my native language
It also shows how you implement your research results and how to adjust them to your code, which shows how you understand the underlying task and code you are handling (I never had a coding interview, but that what I'd figure)
I want to see how much googling there will be before implementation
>job interview
>interviewer asks for some stupid tree algorithm
>google "how do i download chatgpt"
I mean the funniest part about these questions is they're basically you memorized it or you failed.
The odds of you being able to code one of these implementations from memory without any aid if you forgot is basically zero. However, if you have memorized it from doing some leetcode question grinds or something you just shit it out onto the paper from memory.
There is no in-between for these types of questions. The best you can hope for if you don't know is if the interviewer will accept trying to spring board questions off of them or give you hints at doing it.
I'm 100% of the belief these types of "technical" interviews don't actually test anything valuable for the job. The only level of software development I could see these questions being useful is if you're hiring a straight up junior dev with 0 experience to get some idea they understand stuff.
Like 60% of your job once you're past the intermediate portion of your career is literally spent writing up design documents, grooming tickets, code reviews, and mentoring., If you give this type of a question to a senior+ role wtf are you even testing for in your hiring practice.
I've worked with plenty of insanely talented and great senior / lead / staff level engineers that if you stuck them in a random interview with this type of a question there is a non-zero chance they couldn't answer it directly.
Some do. I let (and encourage) people to Google in interviews. The caveat is you must share your screen.
If they know their shit you can tell. I had a candidate who had to change hyphens to spaces in a string (we start with an easy question), and he asked to Google. Fine. He finds a Stack Overflow with the most straight forward answer. Thirty minutes later he still doesn’t have it done.
the first answer was just string = string.replace('-', ' ')? i would be so fucking stoked after that. but that's when you hit em with the DSA, right?
It was a take home test with some mock data. We’d move onto any bugs in their project, and then onto adding a new feature. You’d learn pretty quickly if they knew their stuff or not.
If knowing how to use the stdlib is "knowing my stuff" I'd be employed for like 10 years by now
My understanding is that the goal of a programming interview is to watch how you solve problems and gauge your understanding of general concepts like algorithmic complexity. Even if you have google, you do need some baseline knowledge to be able to do so effectively, and these are commonly treated as the measures of that.
Because there's no point in wasting your energy on trying to explain why it's a good idea to know how the algorithms work and why specific implementations are more efficient than others?
It was handy to write my own quick sort when I had to make a distance based median filter for a large number of randomly distributed points. For even larger data sets it became more efficient to use an octree to partition the data before sorting. But there was a crossover number of points where that was more efficient. In both cases it was faster to use a home rolled sort because we needed to do intermediate calculations that could be baked into the sort mechanics.
That was the one time I ever needed to write my own. Otherwise just good old .Sort() was sufficient.
It always bothered me when interviews tested knowledge that should have been conveyed in college (which is visible on the candidates resume) but is never practically used in real life.
In C++ for example you can use a std::map rather than implement your own self balancing binary search tree, or a std::list rather than a linked list.
It makes way more sense to test a real word use case that would require candidates to use the standard containers in the language used at the hiring company, as well as crafting a problem clever enough that it could be done wrongly, and so one must demonstrate knowledge of computational complexity to do it correctly.
That or you just ask them to solve whatever problem you would rather be solving than doing the interview
You don’t know how to implement QUICK SORT? Yall making this way harder than it needs to be. These aren’t difficult concepts.
I did Software Dev for over a decade.
I never implemented Quick Sort or Bubble Sort - Ever.
Same. And I do low-latency work. This thread is just full of loser programmers who want to feel superior because they know a sorting algo
Bet they wouldn’t feel so superior if they saw their salary compared to real software engineers
Same here. Show them a quick sort instead and ask them what it does and how.
5 YOE, I have written my own quicksort implementation multiple times in the past but would definitely not be able to just re-write it now without a quick 5 minute google and refresher on it.
Do most devs commit this kind of thing to memory and if so, how? I've not had to write my own since college, how are you retaining the details of how to implement this for years on end?
For me I feel as though my programming skill follows a use it or lose it rule. Sure I'll have a general idea of how to solve a problem I've solved previously, I know generally which sorting algorithm is best for which use case, but I wont remember this with such clarity that I could just write the solution out in a text editor years later.
You just remember the high level idea of "Choose a pivot, put everything smaller to the left of it, everything higer to the right of it, then recursively sort the left and right"
Thats it, then use your programming skills from there to fill in the details.
Huh yeah not that complicated to do on the fly after all.
Until you get asked about a different sorting algorithm. Every interviewer has a favorite.
It’s insanely stupid to memorize sorting algorithms. Just understand big O complexity and you can solve whatever you need
Dude, the majority of recent grads can’t tell me how many bits are in a byte or what an L2 cache is. That’s not me being crotchety, that’s nearly all of them failing the most basic of interview questions.
Most CS degrees have moved away from the “science” part and become glorified programming bootcamps.
In my undergrad of my teachers hammered the concept home that CS was the "study of algorithms" as opposed to "teaching programming" and the like. I take stuff like that to heart.
I wouldn't grade my undergrad curriculum super duper high or anything, compared to software engineering in "the real world"; it scaled a little too academic and not enough practical. I do also value a lot of what I picked up there.
In 10 years of embedded programming interviews I’ve never been asked about L2 cache.
Because I’m busy being asked real important questions about the work I’m going to do, not some stupid topic elderfoxboy wants to feel smart about.
& I make well over industry average. Keep complaining loser
Well, I mean it makes sense if the work you’ll do has anything to do with handling that type of memory directly.
But I guess it makes more sense to ask embedded engineers about things like RTOS, interruptions, serial communication and memory handling (stack vs heap). Depending on the specialization maybe some other things, embedded for house appliances is not the same as automotive embedded (obligatory, fuck Autosar).
Agreed. Fuck autosar.
Most CS degrees have moved away from the “science” part and become glorified programming bootcamps.
This is true. I switched from CS to IT because I wanted to spend more time programming. I'm not here to change the world unfortunately and I expected my career to be full of largely solved problems. And 10 years later that is still accurate.
Is it hard to imagine why a student with a future of writing high level CRUD and MACD is not that interested in how the hardware works?
tbf I had one class in total that touched on L2 cache, and it was definitely a theory/mathematics heavy program. There's definitely no reason to not understand Bit vs Byte though.
No because honestly. I had to learn on Kubernetes, how to develop a mobile app, how the framework Spring works, what is AOP, so no. I don't remember because I'm just asking the database. Order me that. If I needed an interview without the help of the net, I would be ok. Fine I leave.
Knowing at least a few basic sorting algorithms means that you can sort items where the library sorting algorithms are not applicable, or are inefficient and you need a different algorithm for your specific use-case. It also teaches you how to approach a whole class of programming problems. Definitely learn your sorting algorithms, folks!
But you can do that when the time arises. Unless someone has a very good long term memory or are interviewing all the time, they’re probably going to forget and just look it up again later if that time does come.
The modern man requires modern solutions: npm install quicksort
Unironically this. It has been invented. It has been implemented countless times. There's no need to be able to do it from scratch basically ever. They don't ask builders if they can produce bricks from scratch, do they? They don't need to. Even in a 30 minute interview there are better things to ask, unless the job really requires inventing algorithms.
problem is the bulk of these interviews, the interviewer is not a programmer and they dont understand shit. They claim they are but they havent written code in a decade or more.
A lot of places have useless managers in charge of programmers when you need a Programmer, someone who can actually do the job in the role to be able to accurately gauge what is going on and is needed.
Instead a lot of places have a fucking MBA that took CS 101 in college.
Yes, but if you don't know how it works you won't know when it's optimal to use it. Do I ask candidates to implement sorts? No. Do I value them knowing and understanding algos? Absolutely
Similarly, I am not gonna reimplement DES or AES, but it helps to know how (usually) symmetrical and asymmetrical keys work
Yep just show them a quick sort and ask them how it works and if it can be improved and why. No one fucking memorized that shit but they should be able to understand it if they see it. That’s how I interview.
Right, but the trick is that you have proven that you are capable of understanding it, the better you understand it the better the chance you can read up on something and adapt it properly when the time does come. Also, you can prove that you can talk about and explain an algorithm that isn't so simple as to be trivial.
Also, seeing how you handle whatever gap there is in your knowledge is valuable. Are you gonna make stuff up? Are you gonna admit to being unsure? How much can you fill in despite being unsure about it.
Quicksort is trivial though, I find it hard to imagine anyone that can program (beyond a beginner level) that wouldn’t be able to implement it if needed outside of an interview setting, regardless of if they have prior exposure to sorting algorithms or not. For an interview it’s really just coming down to whether they’ve prepped or not, and I guess also nerves.
The points you raise about what the interviewer gains from seeing them do it, can also apply to any similar style white boarding problem. There’s nothing inherently unique about implementing a sorting algorithm over anything else.
Like there’s nothing wrong with conducting such an interview but I find it questionable reading too much into it.
Unless someone has a very good long term memory
Quicksort is trivial though
I'm not sure these make sense together.
How so? If someone doesn’t remember the details of a specific algorithm then they’re not going to be able to implement it without looking it up, it doesn’t matter how easy the algorithm actually is to implement.
Indeed. An interview posing this kind of question is not auto-bad. Feeling out how you approach a problem and solve it -- even if you don't know it cold / off the top of your head, informs the interviewers how you approach a problem and work it out.
It is not literally "write a qs algorithm down on paper and make sure it compiles or you fail the interview" (I'm sure there are some cases like it, but generally not).
Probably easier to just use a Sorting class.
Or a Sorting Hat like in Harry Potter.
If they are "not efficient", then you will write one that won't work for 90% of the non-trivial cases, and be slower in the rest.
It is worthwhile to be vaguely familiar with how one is implemented (and the algorithmic complexity!!), but you will NEVER write one, with the ultra-niche exception of writing your own language's standard lib, or implementing a database.
I think it's useful, even important, to understand fundamental structures and algorithms. But I'm probably never actually implementing sort (outside of interviews) again.
Very true. I had to write a custom bisection algorithm a few months ago to solve a somewhat niche use case in our project. What used to take several minutes now takes less than a second
This is the answer. You will always use the library though.
It teaches you when you need to do some algorithmic work in the backend.
You need to know when you join or match data from different data sources that most of the naive ways lead to timeouts.
Lets say showing a list of 10 items takes 1s to load but the algorithm is O(n**3) to find the matches.
So in theory twice the data takes 8x to load.
Http timeout is 60s, so showing 40 items will lead to timeouts.
Humans are even more impatient, loading for 20 items and people will be annoyed.
Finding a O(n log(n)) solition means it less than doubles the time for double the input.
Yup. It's the fundamentals.
I studied algorithms and did a lot of stuff by hand at one point. That was like 20 years ago.
Offhand I can tell you that quicksort is one of the best but has worst case edge cases, although I don't recall what those are.
Mergesort is my all favorite in terms of overall balance.
Oh and you probably don't want a bubble sort.
Binary trees or searches in general are cool. They like apply a log to basically anything.
Beyond that, I don't recall much. I can talk a lot about handling edge cases in the cloud or how I've had to clone and modify npm packages in order to fix bugs in popular libraries to make client applications work, though!
but has worst case edge cases, although I don't recall what those are.
Depends on the implementation, but with the very standard implementation, a nearly sorted list is the worst. Not that this is that difficult to fix. There's several little tricks that can thoroughly blunt the problem.
you can sort items where the library sorting algorithms are not applicable, or are inefficient
...the library sorting algorithms are applicable and efficient for 99+% of use cases.
Are people genuinely complaining about knowing things?
Like I don't know about you but knowing how commonly used things work under the hood helps massively when building code.
And shockingly enough I've had to implement various sorts due to the language and/or framework not offering the tools to leverage an already implemented method or due to very specific requirements (like a sorting algorithm that sorts TB of data with only a fraction of the RAM. Which ended up using heap sort with the hot part of the heap being kept in RAM)
Tell me in detail about the different levels of abstraction of the Deque PHP function.
On one hand, it's knowledge. On the other, it's completely useless knowledge that you'll never use.
A lot of it just feels like gatekeeping at this point.
That’s because it is.
I think the frustration, some of which I'm actually facing now, is being interviewed about things that don't seem to matter in practice.
I have 15 years of experience developing applications and sorting algorithms and whatnot have not really come up.
I'm generally interested in tech, but getting to know stuff under the hood has been majorly secondary to just building the thing and doing so quickly at sufficient, even if not perfect, quality.
So I have a lot of experience building and shipping and maintaining and supporting actual applications across a variety of infrastructures, handling all kinds of crazy production scenarios and client requests, etc.
Something most developers don't have, and arguably equally as or more valuable than an algorithm I haven't had to review in two decades.
Yet I'm considering taking a few months refreshing on some of this stuff just to pass interviews. It feels weird.
That’s because it is weird. Our industry is still living in the fucking 90s.
It's more like a filtering process and everyone knows it. It's easiest and most cost effective way to shortlist the huge amount of applicants. They are merely identifying those who have done their homework and not necessarily testing the real world/relevant technical skills.
If I get asked this I'm going to tell them it's a solved problem and I'll use the sorts built into .net libraries and give hints that if a company is implementing their own sites then their code base must be a buggy mess and that management is wasting the company's money by reinventing wheels.
An analogy about showing up to work as a lumberjack and your boss pints you to the forge and blacksmithing tools so you can cast your own axe head before you can start doing the actual job might get through to them that they should buy or find tools for these jobs, not make crappy versions themselves
If I get asked this I'm going to tell them it's a solved problem and I'll use the sorts built into .net libraries
If I was an interviewer I'd be generally positive to hear this mentioned, though I'd still want to see you give it a go to see how you work.
and give hints that if a company is implementing their own sites then their code base must be a buggy mess and that management is wasting the company's money by reinventing wheels.
yeah, I probably wouldn't hire you if you said this to my face lol
Agreed. This another one of those posts that makes it clear why the average r/ProgrammerHumor poster is struggling to find a job. Of course I would want you to use a standard sorting function in our production code, but that isn't what I asked you to do. If you can't figure out Quicksort, an obscenely easy algorithm to wrap your head around, then I have major doubts about your ability to figure out the problems that our company has.
As someone who jumps in on the final interview process for spots on my team, I've watched 2 juniors basically piss away all but guaranteed job offers by being snippy and arrogant in the in-person interview. The stage that is basically a victory lap for 95% of people who make it to that point here post-covid.
Doesn't matter how smart you are, if you're an asshole nobody wants to work with or can't accept working within constraints, you're not a good fit for our team, or most teams.
So, ask me to solve a problem you might actually want me to solve on the job. I've learned a lot more about candidates that way, than by asking people to regurgitate an algorithm that people have solved ad nauseum in interviews.
You think the person who invented quick sort figured it out in 20mins?
He probably expects you to memorize several dozen leetcode answers instead.
It's wild how much of learning is just internalizing concepts rather than memorizing specifics. Like, I couldn't code a red-black tree on the spot anymore, but I damn sure know when to reach for one.
Sorting is (mostly) solved. These algorithms are just good pieces to study algorithms and reasoning about them.
I am giving a lot of interviews lately. I never ask leetcode type questions; there’s no point. Unless you’re doing deep tech, you don’t need to be so clever. Can you query a DB, map and refine the data, and then return it?
You’re hired!
Quick-sort is actually great of checking whether the person understands when allocations happen (and thrust me I have seen many JS implementation of quick-sort which allocate on each level), so as much as I think lot of the leetcode questions are straight up ass (dual heap medians etc.) quick-sort can actually at-least tell you something about how the person thinks.
I understood most of this comment. Not sure what dual heap median means, though.
it’s a streaming algorithm for calculating running medians…
Why are your medians running? Better go catch them.
(I'll have to Google or ChatGPT this stuff later.)
Kinda like a pyramid scheme
not sure if one can trust a programmer who can't even understand, and explain briefly, quicksort
I learnt it like 3 years ago, used it 0 times so I forgot everything about it completely. Just use arr.sort, every language has it. It's much more readable and easy to use than quick sort.
I keep hoping they'll ask about Bresenham's line algorithm which is a personal favourite of mine.
Spoken like an actual software developer.
Let's see all these quicksort lovers creating a well-designed modular monolith with all the correct patterns and good test coverage.
Yeah, if I'm brutally honest, the performance of a sorting algorithm is the least of my concerns. It's time consuming and really just unimportant.
A sort function is definitely more readable and easier to use than a sort function
Yes, when it's already implemented into the language.
I have 15 years of experience and have done a very wide range of development, and I don't recall anything about quicksort beyond the following:
- I believe it's memory efficient
- Generally one of the fastest sorting algorithms
- I believe ironically though it has edge cases (either everything basically already sorted, everything evenly distributed, or everything maximally unsorted - I don't remember which) where it it performs abysmally
I generally prefer mergesort as it's always seemed to be overall more balanced to me. And if I remember correctly there's a variation of mergesort that can be made concurrent/distributed, which is important if you're building like... A data center or whatever.
I could be right or wrong about the above. I don't really recall. I generally like to recall things I think are actually important or fundamental.
I was literally the lead software engineer at my last company, in charge of 4 - 8 projects at a time as well as our internal product.
What do you think?
Dang, that's quite an impressive resume you got there, but can you implement a double linked list? /s
I believe it's memory efficient
It can be implemented to sort in place, so yes, very memory efficient
I believe ironically though it has edge cases (either everything basically already sorted, everything evenly distributed, or everything maximally unsorted - I don't remember which) where it it performs abysmally
This depends on how its pivot is chosen, but the most common method of "first item in the sublist" generally performs poorly on mostly sorted contents. How the pivot is chosen is the main place where you can tweak the algorithm, and it's possible to more or less eliminate that edge case.
Imagine how it must feel if you’re one of the few people in the world who actually have to implement quicksort
I always find it funny when interviewers expect you to have rote memorised the n-complexities of every sorting algorithm. Like did they completely miss the point of an algorithms course?
Real talk, it's basically a Shibboleth to see if you retained knowledge from your degree or coasted. Weeds out the people who cheated or just learned the tests.
It also shows that you are capable of doing it. I.e. you're capable of understanding basic algorithms. I.e. when you encounter a problem of some complexity at work, you'll be able to find/figure out an algorithm that won't use all of the computer's resources. Sorting algorithms are also great for showing basic competence with indices. It's not about quick sort specifically.
When I am interviewing someone I am trying to gauge how knowledgeable a candidate is with programming in general.
The easiest way is to ask them to implement an easy algorithm. I'm not trying to test someone if they can memorize all algorithms. I just need something to have a discussion about programming.
It would be nice if interviewers chose an algorithm that isn't already implemented in the language.
I never learned this by heart. I saw it in school, I know it is the fastest but that's about it. There is no use for this knowledge in your daily working life normally.
Pretty much. Because irl you just call a quick sort library
The worst ones are the interviews that are basically riddles or trick questions. Am I interviewing for a programming position or am I interviewing to be a treasure hunter?
The purpose of this question is to sort out idiots. If you can't even implement something as basic as a sorting algorithm, why should the interviewer believe that you can implement anything slightly more complex?
Who the hell still gives whiteboard interviews with no Google?
I mean, if I can't figure something out immediately because my employer hands out unrealistic deadlines like candy... I'll use Google, or an AI. That's just real world stuff there.
Last coding interview I had, the guy was literally screaming at me because I froze when he wanted me to do a sorting algorithm that wasn't a well known or widely used one. I had to come up with something on the fly, on a whiteboard, with a marker.
Needless to say, I didn't get that interview.
Bullet dodged, I guess.
It's a simple algorithm, man. If you can't implement it, can you really implement anything else?
I don't see that argument, the question has nothing to do with actual work. If you have to implement basic algorithms like this in your daily work, you are replaceable by ChatGPT
Basic algorithms like quicksort should not be implemented on a daily basis unless for extremely specific circumstances. The basic version of quicksort is extremely inefficient especially. For worst case times it's quadratic.
If you wanted to implement a performant version you would be digging into tons of research articles that spends pages and pages on specifics of the algorithm like how to implement an efficient swap function.
Yeah, who needs theoretical computer science? It's better to have programmers who write list.sort() without understanding the underlying mechanisms at play. My goodness, their code tends to be both more efficient and more readable than people who actually fucking know how software works /s
The second a candidate implies they don't give a shit about this stuff, I know I'm not hiring them.
Edit: spelling
If I asked you to write a Hello World function in Python without using print, could you?
Maybe.
Should you?
No.
Yeah, you have to know every part of a car to be able to drive it. Nice.
I became a worse "programmer" but better "developer" when I started caring less about code and more about what we were actually trying to build.
Granted, I'm not saying these are mutually exclusive. Sorting algorithm internals haven't come up much during the last 15 years of software development, though.
It is more efficient and more readable 98% of the time.
tfw when you realize the only things that separate your education from a bootcamp education are pointless
In my opinion, it tests two things.
1) Do you still remember a basic sorting algorithm? Is about you knowing your basic tool box and the tradeoffs that come with each tool.
2) Can you translate such a concept into good enough code? Is very much job related. You have a basic strategy that you want to implement to solve a basic daily problem. Just moving some stuff around in arrays in a non-trivial way. Think about getting some stuff from a database. Now you have to rearrange it for your app or website. It uses the same set of skills.
Of course, all of that gets usually lost in interviews. Interviewers do not ask in a good way (to be fair, it is hard to ask the right questions), and interviewees just learn the implementation by heart. Then you get the meme and everybody is unhappy.
Imagine actually liking the carrer path you’ve chosen and learning these things because they are interesting instead of because they are useful.
Ignore when youre working in a language without a convienent sort-any-object function for a custom class... Or a language without objects...
It just reflects that you listened during Elementary Computer Science 101. That's all.
Oh.. you didn't take that course, or didn't listen? Maybe they don't want to hire you.
I only try to implement quicksort as a refresher for when I have an interview but the thing with most knowledge is to develop that way of thinking and at least remember enough to quickly search it.
I don't remember 90% percent of networking but at least I know the general parts and where to actually look for the specifications.
Hey, I use quicksort irl when sorting large amounts of things like exams, comic books etc.
The 3 pivot selection system works pretty well and then I have stacks of thing on my table where the left part is lower than the right. I optimise when there are 5 elements in the stack and then do a manual sort bubble style.
I have learned Quick sort today , wish me luck guys that I don't forget it later
maybe at least to have some fundamental understanding how algorithms work. so instead of your web page loading 10 seconds on a modern pc it only loads for 5
Honestly, you should learn it at some point, college or otherwise, just so you have the background knowledge of how things work. You shouldn’t be expected to recite this knowledge during an interview when you’re not going to use it in practice.
When working in memory constrained and slow clock environments it can be useful. I used introsort once on a 32khz ultra low power RTC coprocessor.
When I was on an interview panel I didn't really ask coding questions (unless they were a very junior applicant). Instead I learned a lot more from asking them about trade-offs between language paradigms such as OOP and FP. Also, how do they think about State? Should it be mutable / immutable, why / why not, give me some examples where (whatever direction you've taken) is a beneficial approach. You're into Rust? Cool, walk me through the benefits of it's memory model etc.,
There were a few other questions depending on the person's background and what they were applying for but these kind of general questions with "no wrong answer" gave candidates a lot of time to demonstrate their knowledge to me. It worked quite well.
I don’t care, just want my SQL ‘order by’ clause to be fast 🤷🤭
I don’t remember how to implement quicksort but I do remember how to use google
If you haven't had to know how quicksort works, you haven't been writing code professionally for long enough. Just wait.
Questions about quicksort determine whether you can persist in learning something.
It is sufficiently counterintuitive that nobody would understand it just by reading the code, but simple enough that with an hour or so of persistent effort even a child could understand it.
It's also counterintuitive enough that a child would not be able to explain quicksort even after understanding: it takes a bit of people skills and abstract thinking to explain it in a comprehensible manner.
---
In other words: if you can't explain how quicksort works even after preparing for an interview, then you can't be relied on to RTFM, explain the problem in a manager-friendly way, or debug issues thoroughly.
Also useful to know there are many ways to solve a problem, how they all work, and why they were developed. There’s a difference between true understanding and learning just the minimum you need to get the job done.
Every industry has these quirks. Accountants are tested on their ability to hand crunch numbers that they would always use excel for. Lawyers are tested on memorization of facts that they would always look up in practise. Engineers are tested on physics calculations that they would never crunch without specialized software. Such is our way.
20 years in and I've never been asked to write this, nor asked other to write it, as you will never do this in real life at a job.
I just want to add that Java's quicksort, used in Arrays.sort(), can be vulnerable to DoS attacks. Knowing the functions you use well, even if you don't have to implement them yourself, is crucial if you want bulletproof code. (Which I think most developers should strive for.)
Being able to quickly sort things out is a valuable skill everywhere.
If you're anywhere near competent quicksort should be easy
I think often it comes down to there being no widely recognized standards body for programming so interviewers only have the candidate's word they have any idea whatsoever.
I originally studied mech eng and have gone into embedded. Tend to do very well at more hardware oriented places because they'll ask about wider engineering knowledge and experience using specific stuff like low power modes and things.
When I'm asked about algorithms I just look like a dumbass though. I'm aware there are better/worse ways to do things in software algorithmically but in my type of embedded stuff the considerations are more 'does the microcontroller have a dedicated circuit for this task I could use?', 'could I just make a lookup table at compile time?' etc. The main gains are just finding ways not to do the thing in software at all.
Why did you learn quicksort? Because it's a randomized, average-case asymptotic algorithm, and learning to analyze its performance is valuable.
In particular, it teaches you some really important and fundamental things about computing:
sometimes picking a random element is the best choice! Quicksort which always picks the first or last element will take O(n2) on sorted lists or reverse-sorted lists, so if you're sometimes sorting lists that are already sorted, or somewhat ordered, quicksort has to have a random element.
Analyzing random algorithms is more complex, but very valuable! Quicksort's analysis gives you a tool you can use to reason about other algorithms, while being a task so simple, and so ubiquitous, that basically everyone in class will grasp the problem, and the value of solving it, without needing much extra background.
it's a pretty simple algorithm, and if you did need it, you'd have it available. But more importantly, being able to implement an algorithm like that helps you approach algorithms you actually do need to implement.
To be honest, it's not a great interview question.
It’s scary to me that people still don’t understand that the purpose of teaching these things is to display and impart the thought process behind the thing rather than the direct thing itself.
If quicksort gives you trouble I don't want to work with you.
Skill issue
Bonus question, how to do it without recursive calls. AS YOU SHOULD.
I just use the sort function :D
When hiring, we have a simple test that involves hand sorting a list of employees data. Not quick sorting, not writing an algorithm.
Hand sorting.
Just show us the list sorted in a meaningful way. And people still can't get it right or even vaguely sensible.
quicksort's partition algorithm is literally a version of quickselect which is the fastest algo for finding nth in array.
from some arbitrary perspective all math is just bunch of tricks. and the more you know of these tricks more you get to connect and use them in weird new situations.
So maybe just learn them and hope it will be useful in a 50 year long career?
It is dumb, but, its also a basic test to see if someone has lied on their resume. A few places will contact the school to see if you attended (and passed). Most do not.
A year and half ago I interviewed a guy who claimed to have an undergrad and masters in CS from a certain university. I started asking about the big oh of hash tables with linked list collision resolution. He said they did not teach that data structure. He was surprised when I said that that is the university that I attended and they for sure taught it. My guess is that his entire resume was BS.
Another fun big oh question: "imaging a balanced binary tree with a few million items, what is the big oh for lookup time." He responded with an estimate in seconds. he too claimed to have studied CS.
I am not sure about the US but Canada has many new people from India, Pakistan and China (etc) and a huge proportion claim to have advanced degrees from schools no has heard of (including google!). But, some pretty basic questions gets to the root of it. Many have memorized answers from famous "cracking the coding interview" from Gayle somebody books. So you need to just make them think on their feet with an original question. The ones who can are great.
I implemented binary search in Excel VBA once. So there's that.
It’s also a sorting algorithm or recursion. I’m sure somebody somewhere had used recursion in the wild, but I’ve never seen it. Doesnt stop every tech interview from having a “tricky” recursion question though.
Most interviews I've been to aren't like this thankfully. Amazon on the other hand... Talk about a waste of time in an otherwise wonderful trip to the Northwest.
I believe the problem was, "if you had n number of stairs and you can either walk up one stair or jump two at a time, what are the number of ways you can go up the stairs".
I was like... I guess I failed the interview. I'd even been studying because I didn't go to school for developing but had been doing it professionally for 3-5 years at that point, but I just choked and had no clue.
In the next 5+ years since that knowledge has made zero difference in my ability to learn or earn a good salary.
Stagnation explained as quick as possible:
I implemented most types of sorting and data structures from scratch for my studies. I don't remember how to do it anymore, however i do remember how they work and when it's best to use each of them, what is pretty valuable in actual work.
And yes, bubble sort has a use case, however almost 100% of the time it's better to use standard library sort(), because it uses either quicksort or merge sort and it's optimal.
it’s almost never merge-sort since merge-sort is almost always insanely slow due to how it manages memory. Usually the standard libs endup doing some form of intro-sort since it’s the best performing one in majority of cases.
Can’t you merge sort in place
you can… but in place merge sort implementations are usually slower then just normal tim-sort
All I remember from uni almost 20 years ago is that merge sort has a memory complexity of O(n log n) (and the same computational complexity too), whereas quick sort can be implemented completely in place, not allocating any additional memory.
Same average, but the upper bound of quicksort is O(n2). For every method of finding a pivot, there is some array that would force O(n2).
google says merge sort is still widely used
By whom tho? C++ std::sort is an intro-sort, std::stable_sort is modified tim-sort, Java uses something that looks like quick-sort for arrays of values, tim-sort for everything else, python uses tim-sort, C# uses intro-sort, V8 uses either shell-sort or tim-sort depending on the type, rust uses either intro-sort or tim-sort depending on what you call, go uses intro-sort by default, tim-sort for stable sorting…
inb4: no tim-sort is not merge-sort high level they look similar since they are both D&C (although tim-sort kinda isn’t in a way)
Huh... Today I learned.
Lots of good information in this comment.
I wasn't aware hybrid algorithms were the standard in practice, but it makes sense.
Yeah, even if big O notation says which sort is better in theory. Once you start talking about real world memory models and caches, you can fine tune better strategies.
Realistically you will always reach a point where insertion and bubble sort just murder you just because they have great properties when it comes to locality, so you have to figure out some hybrid approach if you want to be performant.
This guy sorts.
You know about month ago I got send down this rabbit hole when investigating what’s causing a random context switch in a piece of rust code…
All those sorts are implemented by libraries where the developer makes no assumption on the data being sorted.
IRL any data center uses bucket sorting, can google about TeraSort which is just a modified data aware bucket sort.
That is because IRL any dataset large amount for people to bother looking at efficient algorithms, is also data good enough to sample and retrieve a value distribution graph (pre-requisite for efficient bucket sorting)
I don’t think I ever implied they were the most effective way to sort data that isn’t completely opaque and entirely in memory.
And sorting out of memory data on some parallel system of nodes is its own different beast and works very differently since you don’t have to be worried about eating context switches left and right and you don’t have to be all that considerate of locality.
Ahn, sorry, I never meant to say that those algorithms are bad, just add a bit on that list by also talking about bucket sort - which most redditors seem to think is "only good when sorting integers with limited range".
And indeed, different set of problems. Most libraries have reasons for implement sorting the way they do, and they rightfully don't assume anything about data.
I'd never implement bucket sorting when I'm only sorting something of the order of a few million items locally, just use a .sort() and it's done. Only really useful when you have to, for whatever reason, sort a big database that won't fit in memory (ie >1TB).
Yes timsort is a merge sort variant, your opinion doesn't just auto win the argument.
Its not the school playground getting in first doesn't work in the real world lol.
Wikipedia or some random guy on reddit.
https://en.wikipedia.org/wiki/Timsort
Here's an interview with Tim Peters clearly saying its a merge sort hybrid.
Rare Tim Peters and Linus Torvalds interview: Why do nerds argue over classification of algorithms?
Arrays.sort() in Java uses merge sort for objects.
Wikipedia is a basically a random guy on reddit.
Timsort isn’t merge sort. It is derived from merge sort and insertion sort, but that doesn’t make them the same. That’s like saying C++ is just C with extra colons, or a Prius is the same as an Formula 1 because they both have engines. Shared components don’t make two things identical.
Also by this logic it "is" also insertion-sort, therefore insertion-sort and merge-sort are equivalent to each other. Or maybe it's tim-sort an algorithm derived from other algorithms...
Java has used tim-sort for Arrays of non-value types since java 7… I clearly stated that it quick-sorts value types and tim-sorts everything else.
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])
Wikipedia is more like 10 random redditors who see a post but can't find anything wrong enough with it to try and correct the poster.
You can check how many redditors it is by looking at the talk page.
really? I only used it in some games with pseudoprogramming puzzles where it's the most straightforward algorithm to implement with weird instructions that games throw at you, lol
It's good if you know for sure that your data is already very close to being sorted, and you just need to fix a few values. Merge/Quick have lower bounds of log(N), but bubble has a lower bound of just N while being possible without any extra memory and no complex pointer math.
However I suspect most use cases for data of that shape would perform better with a heap instead of a fully sorted array.
I prefer to ask easier questions in interviews, like "you have an array of numbers. Write code on a whiteboard to find the average value". Anyone who can do this can implement quicksort when they have access to the literature. Anyone who cannot do this cannot code at all.
It uses very little memory in comparison to other sorts (it need like 2 other sorts) and is O(n2) - not good, not terrible. It mattered in like 50s-70s, nor really now.
O(N2) matters a lot more now than it did in the 70s: sorting a list of 100 entries in ~5000 compare-swap operations at 4MHz is about a 1000 times less painful than sorting a list of 100000 entries in ~5000000000 compare-swap operations at 4GHz.
The stuff that doesn't (usually) really matter now is, like, optimizing the individual calling conventions for functions or eliding stack frame setup or using
xor reg, reginstead ofmov reg, 0.Every good developer should have a decent understanding of algorithmic complexity (time and space). And sorting algorithms are a good way to teach the concepts. The goal is clear, the algorithms are not too complex, and most algorithms have easy to understand worst-case and best-case complexities.
Especially for the case of combinatorial explosion, where iterating over all combinations of a seemingly small number of possible configurations can lead to huge computation times.
You don't need a perfect understanding of computational complexity, but you need to know the basics to navigate around the pitfalls.
I once implemented a custom sort to optimize a high throughput service with massive CPU usage. It was cool. It only works for the particular use case we had.
I instead rely on the highly optimized implementation provided by the standard library of the programming language i use ;)
I don't know what use case there is for bubble which insertion sort doesn't do better.
Bubble sort‘s use case is if you need to sort a list of twenty elements or less.
bubble sort is massively faster than quicksort on small datasets. are you sorting under 50 things? bubble sort is the best choice for performance.
I run into this regularly with new hires. Always ready to prove the new guys wrong when they start asking why the driver setup UI uses a bubble sort for presenting devices discovered in the system
I'm going to highjack your comment to spread the word of cpu locality. Usually O notation don't mean shit unless you're storing more data than can be stored in the cpu cache, but if not usually arrays are just faster because cpu's usually grab 64 bytes after accesing an element in ram and puts it in the cpu cache which is way faster access time than ram. So fragmented pointer based data structures actually suck if you don't have millions of elements because it has to go to ram for most element access which is super slow.
I guess some caveats is that it really depends what you're doing, how big your data is, what cpu is your program running is, but yeah Big O is not the whole picture.
Also this stuff totally unrelated to algorithms or whatever, but I feel like it's not talked about enough, and most people think Big O is the end all be all, just wanted to spread some good info.
If you have a standard library available. Not always. Bubble sort has it's use in that it's quick and easy to implement and suitable when it doens't matter that it's slow because you're only sorting about 10 items.
For me: the reason to know the algorithms in an interview is to show that you know the algorithms. This is the simplest of the computer science theory, if you are self taught then this shows me you also studied the boring stuff and the "why should I learn this crap since I can just use a library!!" stuff.
Sure, you'll likely never have to implement quicksort for real on the job. But it not at all uncommon to have to implement some other algorithm, or create a new algorithm, or have to analyze an algorithm. It is common to have to fix an existing library. It is extremely common as well to have to think on the job, and these sorts of things are ways to show that the candidate can think.
The N2 sorts do have a use case of being easy to implement with zero memory allocation. Though even then, insertion sort is still better than the others.
Yeah, I mean it's 2025, yet there are still plethora of obscure 15-20 y.o. legacy software-specific hot garbage "languages" not supporting basic features like sorting OOTB and then I usually implement bubble sort because it happens to be the easiest to implement and - at the same time - frequency of events/amount of items to be sorted usually is so low that it doesn't really make sense to overly complicate it (time-to-market trade-off)