And that might be a good thing. How often does a normal software engineer have to write bubble sort from scratch in his daily life? If someone from my team came to me telling me he had to sort an array and wrote bubble sort from scratch, then I'd probably not be very happy with that unless there is a really good reason to spend that time on it rather than using an existing solution.
Purely anecdotally: I've seen online discourse that suggests that the complex nature of the modern web requires FE devs be able to keep at least a couple efficient data-structure traversal tools in their toolbox.
Anyone with more experience could probably chime in.
In my experience, most front end performance problems are just unoptimized assets, or huge JS bundles. After that, there's issues where you're doing a lot of unnecessary rendering, for example in a React app, a Redux mapStateToProps function that isn't memoizing an array map, which is causing the whole subtree to re-render on every state update. The only time I even needed algorithmic complexity was implementing a drag and drop control, for a list that could have several hundred thousand elements, and my naive implementation was n^2.
"memoizing" is a pretty computer-sciencey word, so not implementing a data structure exactly, but still requires knowledge beyond "plug these APIs together."
> The only time I even needed algorithmic complexity was implementing a drag and drop control, for a list that could have several hundred thousand elements, and my naive implementation was n^2.
And if you didn't have an intuition for algorithmic complexity, how long would it have taken you to figure out the problem? And how many times have you instinctively avoided having an explosion in algorithmic complexity, by intuitively picking a suitable data structure or algorithm?
I suppose that depends on what a programmer is asked to do. There are many roles and not all of them need the same thing regarding knowledge, computer science or abstract thinking.
If you are in a position where you mostly do the same thing over and over inside a relatively complete framework for a managed or scripting language, you are unlikely to find yourself building data structures, algorithms or understand what a query planner in an RDBMS might be up to. Those positions are far more prevalent than people might think.
On the other side are the people that have to make sure that they get as much speed and/or as little memory usage as possible because they work on software that will scale (i.e. a small data structure that is used to keep track of filesystem allocations - you don't want a slow structure that also eats up a lot of disk space). But there are far fewer people that actually do that, and in theory far fewer people are needed to do that because a 'good enough' filesystem will fit all of those people from the other category. If one filesystem developer can support 100 million managed-language-framework-MVC-website engineers it's a pretty good scale.
Speaking as someone who has had to write performance critical data structures and also someone who does well with whiteboard interviews - there is a large difference between writing an algorithm with the advantage of having time to read, reason, and test your code and doing it on a whiteboard. There are many people who would do a fine job as a filesystem developer but might not be able to pass the interview for it.
The current situation benefits me personally in many ways, but I recognize that it's unfair to many other people.
Yes, that is true. At the same time, most of those interviews are of course more about finding out how a person performs under pressure and how a person thinks rather than how well the white boarded shell sort for red-black trees with double-rot13 'encryption' would be usable in the real world.
At the same time I'd hope that we get better at asking questions rather than repeating the same nonsense in every interview. The more people we can work with, the better. Because maybe not everyone is a fit for the position we had in mind, but maybe a less complex position could be filled that way. Often the interviews are rather binary (due to it often targeting a vacancy instead of a workforce role) costs everyone involved much more than it ideally should.
I agree, what's more important IMHO is education/knowledge of existing data manipulation, after all 99% of the work is reuse not pure creation (incremental vs pure innovation).
Algorithmicians (? - well... algorithm researchers, obviously) and programmers are not working in the same field of work, even though the boundary might seem thin for most, there's a world between both.
I wouldn't be able to write a bubble-sort specifically.
But if I were asked to "sort" a set of numbers, I'm sure I'd come up with some unholy combination of bubble, selection, and insertion sort that got the job done.
I always have to consult the books to remember the difference between bubble, insertion, and selection sorts. But even without documentation, surely people can write a list of numbers (ex: 9, 4, 5, 3, 2, 6, 0, 1, 8, 7), and then tinker with an algorithm until that list was in order? (0 1 2 3 4 5 6 7 8 9)
------------
Here's the thing about programming: you don't have to travel very far before you get into the "nobody knows the answer". The internet provides enough information for the first ~2 months on the job. Specialized books on your topic (ex: GPUs, HPC, OpenMP, etc. etc.) may cover another 1 or 2 months of training on the job.
After that? Nobody in the world is doing what you do. Nobody has to work with your particular configuration of tools, your particular problems (performance? Bugs? Architecture?). Your particular office politics. Literally no one else in the world. And yet, you'll be responsible for coming up with a solution that works, even without any guides.
That's why people like testing people "without the internet". Because in most cases, there's no guide to tell you how to progress a real project in the real world.
Merge sort is wonderful. Not only is it as easy to remember as bubble sort, but is there anything else that can work with data that doesn't all fit in memory?
Strangely enough, I always found quicksort easier to write than Mergesort. But that's probably just how my mind works.
Hmmm... with Mergesort, you gotta be copying the data to new buffers, malloc-ing arrays and new arrays, managing the data etc. etc.
Quicksort can be trivially done in-place. And yes, I know Merge-sort has an in-place variation, but in-place Mergesort is non-intuitive IMO.
-------
I guess merge-sort is easy if you are willing to call malloc / free (or new / delete) over-and-over again. But those functions scare me. I prefer to get things done without dynamic memory, especially if its a whiteboard interview.
Quicksort does require more brainpower than selection / insertion / bubble sorts. But if I were to use a recursive methodology, trying to do quicksort would be my strategy.
Mergesort sticks in my memory better, for whatever reason. And yes, definitely agree that in real life, avoid those allocations. For a whiteboard interview, declare an std::vector and call it a day, no need to manually call new and delete.
Off the top of my head, I could write selection sort, insertion sort, merge sort, quick sort, and with a few minutes of thinking about it, even heapsort. But bubble sort? It's a useless sort, even worse than selection and insertion sort, which have their advantages in certain circumstances. So I don't bother to remember what the algorithm for bubble sort is in the first place.
Do you learn algorithms by blindly memorizing their steps? There's nothing to remember in bubble sort, if you know that it "bubbles" by swaping the elements you're already done.
The main "issue" I have is that if you write a "bubble" sort backwards, then its suddenly insertion sort instead and much more efficient.
For people who know about knots out there... its like asking for somebody to tie a Granny Knot instead of a square-knot. Anyone who actually practiced knot-tying will "accidentally" tie a square-knot instead (because the square-knot is stronger for the same level of effort).
Similarly, bubble sort is the "bad" way to write insertion sort. Anybody who actually practiced writing sorts will write insertion sort by accident instead.
I'm pretty sure the original meaning of "I can't even write bubble sort on a whiteboard" wasn't "I would accidentally write a more efficient algorithm instead" ;)
I learn algorithms by memorizing their general structure and filling in gaps using the invariants of the process. A selection sort is pulling the largest elements to the end of the list; an insertion sort sorts the first N elements and inserts the next element; a quick sort picks a pivot to divide the list for sorting; mergesort sorts half the list and then merges them; heap sort heapifies the input (this takes me some time to remember how to do efficiently) and then pulls out the top repeatedly.
But bubblesort? There's no invariant. Sure, I can tell you that it's this structure:
for i = ? .. ?:
for j = ? .. ?:
i1, i2 = ?, ?
if A[i1] < A[i2]:
A[i1], A[i2] = A[i2], A[i1]
But, with the lack of invariants, I don't know how to fill in the ? correctly. With trial and error, I could write a correct sort from this template. But insertion sort and selection sort also follow this template (as does any other sorting network if you try hard enough), and I can't guarantee that I'd hit bubblesort instead of those.
I don't buy it. Bubble sort is the simplest, the most naive one, you don't even have to remember anything about it.
do
sorted = true
for i = 0 .. n-1:
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
sorted = false
while not sorted
That's already a perfectly valid bubble sort. You can then optimize it by noticing that after nth iterations nth elements will already be sorted, and you're done.
If you're trying to recall this algorithm from memory by comparing it with other sorting algorithms you've memorized, you're probably doing it wrong, because there's hardly a place for real world usage of bubble sort, so your memory of it is naturally going to fade away. The trick is - you don't even need to memorize it or recall any structure to fit it into. Just imagine an inefficiently bubbling array of numbers in your head and that's it.
I think it's that "bubble sort" has come to mean "a simple O(N²) sort implementation", of which there are many. But the selection sort just feels more natural than the actual bubble sort. At the very least, selection sort doesn't get my face to scrunch up in a scowl at all those memory movements.
It's either an exaggeration, or his mind works in some very special ways.
You don't need to memorize multiplication table to be good at math, but this is an equivalent of saying "I wouldn't even be able to add two numbers together in my head!".
> That’s one any engineer should be able to implement without any help.
If I wrote it down every time someone claims that "this is so important any engineer should know it," I'd have a book as thick as the bible full of trivia. All of it so easy, and yet in every position you can find a person who hasn't mastered it all. Maybe it isn't all that important after all. Most of these people are capable of finding help should it come to that.
Just like an engineer even at the most junior level should be able to swap and write fizz buzz. If you can’t do that you certainly cannot call yourself an engineer.
And also, even if the sort was important in my app and there was a superior compelling reason to rewrite it internally (one common case is computing 2 things at once), I would probably google what people in the domain do and think first, try to find a few blog post from people who implemented a sort to look at tradeoffs (getting a feel for the politics is in the domain: they probably critiqued each other's "real life" loads, optimization goal: memory vs. CPU vs cache), and then find something on github that I can follow, and do my tweak on.
I agree. In a world where good standard libraries exist, and where Google exists, why would a good software engineer write any of the standard algorithms from scratch?
One thing I find myself implementing repeatedly is the Union-Find datastructure. I never just need that though. Sometimes I need statistics about the disjoint sets, which inevitably means a custom Union implementation. Sometimes I know more about how often Find will be called, where I can get better performance without doing full path compression.
Another one I've encountered recently is priority queues. Here, memory requirements and operation runtimes depend on which operations are supported -- insert/pop heaps are faster than insert/decrease/pop heaps are faster than insert/update/pop heaps. And if heap operations are your innermost loop on your critical path, you can get huge gains from rolling your own -- because a standard library's priority queue will support whichever operations it supports and you can't pick features a la carte.
But no, I never do this without a search engine handy.
Union-find is one I find needing a fair amount too, although it does make algorithms tricky to debug if the problem is a bad union ("which union was the bad one that caused all these groups to collapse into one?").
But even for these simple data structures, I am much more comfortable implementing them with an algorithm textbook in front of me (or some other resource with similar level of detail), simply because it greatly reduces the scope for implementing the data structure itself incorrectly and, secure in that knowledge, I can focus my debugging on the algorithm itself.
I've been a developer for almost 2 years (I know not that long) but I have never even heard of bubble sort. Looking it up, it is O(n^2). Is there a reason this is a common interview question? It doesn't seem like a sort one would ever really use, or at least it has very obscure uses.
I always thought merge/quick sorts accounted for 99.9% of use cases and only ever really learned about those.
The logic of bubble sort is so simple that just the description is enough for an implementation. It's a common interview question for the same reason Fizzbuzz is used -- any programmer worth their salt should be able to just write it down.
Insertion and selection sort are also O(N^2), but sorts like merge and quick will use them to sort small sublists in their recursive cases because they are fast when input is small enough.
Bubble sort is good for two reasons. First, it's so easy that anybody should be able to remember how to do it. Second, it's slow and everybody should know that and be able to point it out.
It's actually usable for small enough n. I once coded it when I expected n to be 4 or less, and I'm sure the person who replaced it cursed my name when that expectation turned out to be false.
For a simple sort you can use for small N, I'd suggest insertion sort. Its constants are better, it performs well on almost-sorted input, and I think it's even easier to implement, personally.
It's not one you'd ever use in practice (I know of no use at least). It's pretty simple to implement given a short description though, so it can be seen as kind of an "advanced" fizzbuzz.
If someone just says "hey, implement bubblesort", that's pretty awful though. Then it's just testing your memory and/or gating by people that studied a particular algorithms curriculum. (Though _many_ intro algorithms courses go through sorting and most of those mention bubble sort probably)
I think bubble sort is used in beginner CS classes because it's easy to understand the operation and the complexity. It makes a good prologue before moving on to more efficient sorting algorithms.
I only remember it because a machine language book for the Motorola 6809 used it as an introductory program.
Keep in mind that big-O notation describes how something behaves as the problem size goes up. Something O(n^2) will be slower than something that is O(n log(n)) for large enough n. For smaller n, it is quite possible that an O(n^2) algorithm can beat an O(n log(n)) one.
If you have an application that only has to sort small lists, but has to sort a lot of them, it is quite possible that an O(n^2) sort like bubble, insertion, or selection sort will be better than merge/quick sort.
Among the O(n^2) sorts, insertion almost always will be faster than bubble, so you probably wouldn't actually choose bubble sort.
I understand. In a sense merge/quick are 'galactic algorithms' at the size.
It's more just that I am concerned I would be cornered trying to remember what 'bubble sort' is. It's not difficult to write the algorithm per se--just hard to remember what 'bubble sort' means.
I guess it's a common question because it's usually taught in college because it's probably the simplest after select sort.
Personally I've never found this case myself, but regarding why it's used some times, the O(n²) is the worst case scenario. The best case scenario is O(2n) which is really good, so for lists that are sorted or almost sorted it works well.
Other algorithms like timsort have O(n) for the best case scenario, but O(n) only tells you how many times you go through the loop.
Without actually measuring it, I would expect each iteration of timsort to be at more than twice as expensive as bubble sort, so in this case O(2n) would be cheaper than O(n).
When you know with a certain degree of certainty how is the data you expect in most cases, some times it's kinda easy to make a more efficient algorithm than the one that is the best for the average scenario.
I was once asked to sort a singly linked list in an interview, and the bubble sort was the only one I could think of at the time. This was a small part of a larger coding test that I think was based on a problem they actually ran into, which a previous employee had solved badly. I got a low-ball offer and turned it down. It wasn't until a couple of years later that I thought about that problem again and realized a merge sort would have been perfect.
Being able to write algorithms is a different thing than being able to do it without any reference or documentation on the state of the art, basically from scratch and from the top of your head, as commonly found in interview situations.
The point is that as an interviewer/employer you risk not getting the information you've asked for. Someone who is able to memorize interview algorithms isn't necessarily a good fit for the role you are trying to fill. Forcing people to memorize the details of these concepts just to comply in an interview is often a waste of time for both parties.
Even as a gamedev/ML guy you don't have to reinvent the wheel everyday. You have to understand what is available, judge about the pros and cons of different solutions, pick the right one and build a good system. Preferably on time.
String length in Python is maybe too much exaggeration unless someone hasn’t wrote Python for a long time.
But, algorithms? Sure! Nobody remembers them for ever. Often you at least need to read how the algorithm works before implementing it. Obviously for most devs it is faster to just search for a sample implementation or a pseudocode.
> String length in Python is maybe too much exaggeration unless someone hasn’t wrote Python for a long time.
Or they use several languages. Say you have client side code in JavaScript, with the client served by PHP on the server. You've got some log analysis scripts in Perl. You've got some SOAP services in Java. You've got some machine learning stuff in Python. You've got a mobile app in Swift.
It's real easy to get confused about which of foo.length, strlen($foo), length($foo), foo.length(), len(foo), or foo.characters.count is the right one for the language you are dealing with at the moment.
And for some algorithms (pretty much anything in cryptography) you really, REALLY shouldn't be implementing them yourself! The correct answer is almost always "use a library call" for how to do it.
Actually I always thought the opposite - if you started programming in the 80’s (maybe early 90’s), you had to write sort algorithms and you had to study them in college, so you’re going to be bound to remember them at least well enough to come up with the “base case” (i.e. bubble sort). I do assume that younger programmers, especially self-taught types, probably haven’t come across these to if they did, it was one lecture, once, ten years ago, memorized and forgotten because they never applied it again.
Yet another article showcasing how the tech interview process is fundamentally flawed.
Personal anecdote: I recently underwent an interview process for a position in my field of expertise (computer vision) consisting of multiple in-person stages, whiteboard coding, product design and a take-home assignment that required developing a foundational (bubble-sort like) algorithm from scratch. After successfully completing all of these hurdles, I ended up with a low-ball offer targeting entry-level candidates. If we could have discussed the compensation up front, I wouldn’t even have bothered.
This is infuriatingly stupid. Not only does that waste your time (which we can be uncharitable and say they don't care about), but it wastes their time! i.e. costs lots and lots of money.
It's very weird how some of those tech interviews are done. I've luckily never had to do one of those, but from the YouTube videos of training interviews and example interviews, almost everyone seems to be asked to implement a slight variation on something to be found in a Data Structures & Problem Solving book by Weiss. Great if that is what you'll be doing all day, but regurgitating some way to get the smallest number in a list or making a directed graph for a word morphing joke hardly represents anything other than a persons skill to repeat what someone else did and wrote down decades ago.
So everyone knows that the interview isn't perfectly realistic--it's a simulation.
Consider that when athletes are scouted, they are usually not asked to play in a full game of their sport. But instead certain stats like 'how fast can he run 100m' and 'how high can he jump' are used.
Sure, in a real game you will never run 100m in a straight line on asphalt--but the speed at which one runs 100m in a straight line is a good proxy for how fast one can maneuver during real play.
That's not a very good example. Athletes are being watched for 4-8 years before they are ever drafted. Colleges are watching all the high school games, and Pros are watching all the college games.
For almost any sport this is a spectacularly bad metric. Just because it can be measured doesn’t make it meaningful. FWIW, the “fitness” required for sportspersons is a very sport-dependent diffuse constellation of factors.
> Consider that when athletes are scouted, they are usually not asked to play in a full game of their sport. But instead certain stats like 'how fast can he run 100m' and 'how high can he jump' are used.
Teams rarely sign players based solely on measures like this, and those that do frequently regret it.
Additionally, the nature of contracts in professional sports are very different from regular employment. Players are cut or traded frequently, often find themselves on very team-friendly deals when unproven, and are granted employment in time-limited blocks.
I know. It's just an analogy. You can replace it with a better one if you want.
The general point I am making is: these are not trying to measure actual job tasks, but instead measuring something that (they hope) is closely related to, or correlated with one's ability to perform the job. The idea is that if one can do these sorts of problems, one can probably do the actual job at hand.
> (they hope) is closely related to, or correlated with one's ability to perform the job. The idea is that if one can do these sorts of problems, one can probably do the actual job at hand
This is a claim about the intentions behind these practices.
Intentions aside, the whole point of this perennially recurring discourse is about effectiveness — that certain overused methods of filtering job candidates are ineffective on their own terms — and negative side effects — that they're biased against people with non-traditional / from underrepresented backgrounds.
I had an interview question a few weeks ago (writing a JSON parser from scratch) that required me to remember that in python that a for loop allows you to iterate through not just a list but also each of the characters in a string. I forgot about that and spent several minutes wasting time trying to think of a regex-based solution before I remembered that was an option.
Why should an interview question reward you/require you to remember this? If I actually had to solve a real-world problem similar to this, I would google it, see a solution that iterated through the characters with a for loop and go “oh yeah, I forgot you could do that. Duh.” Why am I not allowed to google dumb things? On most days, my brain is focused on high-level abstractions that tie together two or more tools via disparate APIs, why the hell should I remember or think about for loops?
Did you try asking about comp before interviewing though? I usually do and most of the time you get a reasonable answer. Probably depends on how easy it would be for them to estimate your own comp though
Is cultural? I always discuss price AT THE START, when was hunting jobs, and now as contractor, and even when I sub-contract.
In the other side, I always pitch "We do this or that, this is what we need help for, and this is how much we can pay (or: how much is your rate?)".
Is an amazing filter. Specially when you don't have much cash to give. Because: If I can't pay... why lost more time? And if I can pay and the other accept it.. only need to solve if is capable.
This is also for my customers. I put a money estimate as soon as possible, or ask upfront what is the budget range.
Is an amazing filter. Because: If I the customer can't pay... why lost more time? And if can pay I only need to solve why I'm a good fit.
A few years ago I had a case where I had told the company what salary I'm expecting. Then I had two in-person interviews and one phone conversation with an additional department in the company that I would be working with.
After that, they offered me something like $10k less than what I had asked for and minimum vacation, saying that when you add in the value of all additional benefits (health insurance, rrsp benefits), you end up at the salary I had originally requested. Did not exactly win me over.
Sad. But at least because you state your rate, you can see how much them lowered. I have lost customer after them say their own prices after I estimate a lot more (that is based in decades of experience, in the same market).
When the counter-offer is TOO BAD you can say, 100% sure, the experience moving forward will be VERY BAD. I'm not in a market where programming is well paid, and this is the most certain sign the customer will not pay on time, or even at all..
I recently interviewed for a job running a kubernetes cluster. I have two years of experience running a kubernetes cluster, including writing a custom provisioner and several controllers in go.
They spent two hours doing coding interviews and 15 minutes asking me about kubernetes, if that.
Whenever this comes up, I can only assume that people are talking about very different sorts of technical interviews than I’ve ever been subject to. I’ve been working as a programmer for 25 years now and must have been through at least two dozen technical interviews in that time (one just a couple of years ago) and I’ve never had this level of pedantry thrown at me. It sounds like the poster has been rejected from a job interview for missing a semicolon or writing “length” instead of “len”. Maybe I’ve just been lucky? I did once have somebody ask me if I knew SQL - I said I did since I had written some queries using it, but not much. He asked me what command was used to add data into a database. I didn’t know (like I said, I knew the query syntax, but that was about it). That seems to me to have been a very reasonable question to ask, and a good, quick way to figure out that I didn’t really have much experience with SQL.
Somehow we arent really adept at interviewing at what the day-to-day requirements of a position.
Instead were much more interested in edge-case stuff like bubble sort.
I wonder if this is some assessment of "are they capable of substantially more complex tasks, and if so, safe to assume they're capable of less-complex minutiae.
Seems about right, as often these evaluation type things are proxies.
That's my experience as well - 30 years under the belt and I don't see interviews like this nor do I give them. I think the audience here is a bit different, startups are by definition immature and usually don't have the experience or means to set up a proper interview team that screens for the right things.
The flip side is that in mature companies like the one I work for, where professional interviews are more of the rule, we don't get the best candidates, at least not right now. I could imagine that super attractive startups can afford to set the bar higher and still get enough applicants.
>It sounds like the poster has been rejected from a job interview for missing a semicolon or writing “length” instead of “len”.
These kinds of anecdotes make me often wonder if candidates are "disqualified" for far more superficial reasons, and if interviewers hone in on pedantry like this to legitimize their reasoning perhaps even unconsciously. I have trouble believing most candidates wouldn't make at least one trivial mistake of that sort and I am equally reluctant to believe the same interviewers would disqualify any given candidate for a mistake so trivial.
The first time I heard the problem of detecting a circular link in a linked list, I figured out the tortoise/hare solution in probably 15 minutes without having heard it before, so it's not impossible.
The tech lead who doesn't know `len()` but claims to know Python? Yes, they're incompetent. It's okay; it's a common problem in our industry, and easily remedied by study and practice.
Chinese is not a great example. Native speakers have trouble reading and writing their own language; it is so complicated that people cannot remember how to write commonly-spoken words or how to read. [0][1] (Choice moment from [1] is when a university student says that Chinese literacy is as difficult as English!)
Perhaps we can do better as a community to design better languages, but also we should not condone people claiming that they know the languages when they clearly don't. Yes, Python could be easier; no, Python is not that hard.
In their defense, some other languages make the length of a string an attribute/property on a string instance. Python feels like the odd one out here making it a free function you must pass an instance to.
If the tech lead spent a lot of time working with another language that made the length an attribute, I think it would be reasonable for them to need to look it up often.
So you feel confident in asserting that, at the time that the person made that tweet, the quality of the Python code that they shipped was poor, or it took an inordinate amount of time to produce? All because they had to look up len()?
Actually, yeah. That one jumped out at me, too: that’s kind of like saying “I know how to drive a car, but I always have to look up which one is the gas pedal and which one is the brake”. If you’ve done _anything_ in Python, the length function is ingrained in your brain, so if you honestly don’t remember it, you just haven’t written any Python (or it’s been more than 10 years).
I routinely use several languages, and am constantly forgetting which ones use .size() and which ones .len(). It's not worth committing to memory because, if I get it wrong, the compiler will tell me "what is this function of which you speak?", and I will simply turn around and use the other one, at which point it starts compiling again, wasting me at most a minute of my time.
Furthermore, I should point out that it's not out of the imagination that someone wouldn't use len() all that heavily. Python has functional operators that let you do map/reduce-style operations on lists, strings, dicts, etc. that don't require you to use length all that much. My most recent python script only uses len() in two places for more robust error reporting.
Well... try not to take this personally, but... that means that you're not really an expert in Python, which is what (I assume) the interviewer in the linked post was looking for. You're capable in several languages, and may be an expert in one or more of them, but if they're looking for Python expertise, asking you how to find the length of a string is a good way to get a feel for how much time you're going to need to get to where you can really be trusted to produce mission-critical Python software (which may not be a deal breaker, if you're good at a lot of other things).
>that’s kind of like saying “I know how to drive a car, but I always have to look up which one is the gas pedal and which one is the brake”
OK, I agree, it's kind of like saying that.
But it's also kind of not like saying that.
Incompetence in driving and incompetence in software development are measured in completely different ways for completely different reasons. In driving, notions of what you definitely should know in order to qualify as "competent" extend from the intrinsic risk to other people's well-being. You can't simply transpose those notions onto the low-stakes sandbox environment that is software development. In software development, process is only important as far as it hinders or helps to deliver good code; competence should be dictated purely by results. All of the actual competence of driving comes during the actual process part; successfully reaching your destination is actually considered to be less important than simply not fucking anything up on the way there.
Sometimes I pick up a video game that I haven't played in weeks, and perform actions incorrectly because the button layout has been overwritten by the button layout of a similar and more recent game. It would foolish to say I'm wholly incompetent at either game; I still have a strong concept of what I should be doing and what I intend to do, it's just that I'm fumbling a bit at the specifics of executing my intent. Am I incompetent for looking up the button layout? Am I incompetent, but only for the 1 hour that it takes me to get back in the groove of things?
Declaring someone is incompetent is a bold assertion to make from such limited information. At the end of the day you either deliver good code in good time or you don't. I would be extremely reluctant to determine this guy can't deliver good code because he had to look something up. Figures no one will hire me.
> I would be extremely reluctant to determine this guy can't deliver good code
See, I’d be extremely reluctant to assume the opposite - that he can, even though he doesn’t remember “len”. Given this one bit of information, all I know is that he has exactly one thing in common with everybody who doesn’t know how to program in Python: he doesn’t know the function for determining the length of a string. Now, he may (somehow?) know everything else about Python except for that one thing: I’m assuming the interviewer was a bit surprised (as I would be) that somebody presenting themselves as a Python programmer didn’t know len, but went ahead and asked him a few more questions which he may well have nailed. If the answer to every question was “I don’t know, I have to look it up”, you’d pass on him, too. I just can’t picture how anybody who didn’t remember that could remember much else, but I guess that’s why job interviews last an hour or so.
>See, I’d be extremely reluctant to assume
>Given this one bit of information, all I know
This seems like a really flawed way of approaching most things. Why assume anything? And if you're going to assume anything, why only factor in that one bit of information, and not any other context. How about the fact that he's been coding for 30 years and works at Google. Is that also relevant?
>I’m assuming the interviewer was a bit surprised
There was no interviewer in this situation. His tweet was not in regards to any interview. Did you read the article?
>If the answer to every question was “I don’t know, I have to look it up”, you’d pass on him, too.
But if I were to do so, at least in such a case I would be basing my suppositions on more than just one thing.
Usually it's just 'How many years of experience do you have in XYZ?' and it's almost never enough. Doesn't matter if your experience is in something similar ('Oh you used Spring boot! We are looking for Spring MVC!') and of course they just care about decades of 'experience'--doesn't matter if you actually know it well.
Then the job ends up not having any relation to what was posted anyway, so it was all moot.
Yes, I am salty. I am sick of taking 'exciting' opportunities just to end up babysitting software that has no relation to the posted skills/requirements.
My favorite is "Yes! We'd love to have someone with broad experience who can dive in a learn new stuff!" followed by "you've read the $TECHNOLOGY_TOOL docs, but haven't deployed anything with it? Sorry, we're taking a pass..."
Asking hard brainteasers in interviews is questionable but bubble sort is so simple anyone should be able to do it or at least start writing a correct loop to go through the list and put a useful if statement in there.
If you don't remember bubblesort the interviewer could explain what the algo does and then you should be able to implement it. I'm all for looking stuff up on the web and we all have phones in our pockets but if there's to be a minimum bar it shouldn't be lower than bubblesort.
Isn't one of the key skills in tech these days knowing how to avoid having to go low-level? And if not, where does it end? Should we know hardware design? Particle physics?!
Anyone ever go in w/ an iron clad algorithm you've perfected then when asked 'Do you have any questions for us?' be like..yeah, I only work w/ the best developers can you beat my algorithm?
or hell just ask them if they can do a whiteboard problem for you. See how the recruiter likes it. See if they do as good as you. Flip the script so to speak!
I was a little skeptical of take home coding exams but the more interviewing I do it seems to be a pretty efficient way to screen candidates as it is less stressful than live coding and more realistic "simulation" of the work they will do. It also allows you to deep dive into their thought process without having to worry about semicolons.
A persons ability to think through a problem and communicate it clearly will get them 75% through the hiring process in my books. (Another ~10% is curiosity).
In theory, algorithms are an important aspect of CS. Having learned about them plus some experience, enables the logical thinking mindset required to develop better code.
In practice, algorithms are hardly useful, either because T&M don't allow it, or the problem gets escalated when adding dependencies to existing code and services.
In theory, some CS, algorithmic or systems thinking background may be that crucible required to avoid many known pitfalls and rabbit holes.
In practice, developing and maintaining IT systems have nothing much in common with sports. This being something more of a distraction by ignorance and management, than anything of tangible value to people and environment.
Been a programmer for 20 years and doing the interview dog and pony show for the first time now. Tons of algo questions out there. Apparently memorizing algos is more important than actually knowing how to build an app front and back and knowing how a web browser, http, tcp works. And knowing dev ops and server admin and how to write maintable code. None of that matters as long as you can say which easter basket has the most eggs in O(1) time and constant space.
104 comments
[ 1.8 ms ] story [ 220 ms ] threadAnd that might be a good thing. How often does a normal software engineer have to write bubble sort from scratch in his daily life? If someone from my team came to me telling me he had to sort an array and wrote bubble sort from scratch, then I'd probably not be very happy with that unless there is a really good reason to spend that time on it rather than using an existing solution.
Anyone with more experience could probably chime in.
"memoizing" is a pretty computer-sciencey word, so not implementing a data structure exactly, but still requires knowledge beyond "plug these APIs together."
> The only time I even needed algorithmic complexity was implementing a drag and drop control, for a list that could have several hundred thousand elements, and my naive implementation was n^2.
And if you didn't have an intuition for algorithmic complexity, how long would it have taken you to figure out the problem? And how many times have you instinctively avoided having an explosion in algorithmic complexity, by intuitively picking a suitable data structure or algorithm?
If you are in a position where you mostly do the same thing over and over inside a relatively complete framework for a managed or scripting language, you are unlikely to find yourself building data structures, algorithms or understand what a query planner in an RDBMS might be up to. Those positions are far more prevalent than people might think.
On the other side are the people that have to make sure that they get as much speed and/or as little memory usage as possible because they work on software that will scale (i.e. a small data structure that is used to keep track of filesystem allocations - you don't want a slow structure that also eats up a lot of disk space). But there are far fewer people that actually do that, and in theory far fewer people are needed to do that because a 'good enough' filesystem will fit all of those people from the other category. If one filesystem developer can support 100 million managed-language-framework-MVC-website engineers it's a pretty good scale.
The current situation benefits me personally in many ways, but I recognize that it's unfair to many other people.
At the same time I'd hope that we get better at asking questions rather than repeating the same nonsense in every interview. The more people we can work with, the better. Because maybe not everyone is a fit for the position we had in mind, but maybe a less complex position could be filled that way. Often the interviews are rather binary (due to it often targeting a vacancy instead of a workforce role) costs everyone involved much more than it ideally should.
Algorithmicians (? - well... algorithm researchers, obviously) and programmers are not working in the same field of work, even though the boundary might seem thin for most, there's a world between both.
Must all painters be artists?
That’s one any engineer should be able to implement without any help. It’s the more complex/useful ones worth discussing.
Even Obama knows this: https://m.youtube.com/watch?v=k4RRi_ntQc8
> David Hansson, the creator of Ruby on Rails, admitted in a tweet that he wouldn’t be able to write bubble sort on a whiteboard.
But if I were asked to "sort" a set of numbers, I'm sure I'd come up with some unholy combination of bubble, selection, and insertion sort that got the job done.
I always have to consult the books to remember the difference between bubble, insertion, and selection sorts. But even without documentation, surely people can write a list of numbers (ex: 9, 4, 5, 3, 2, 6, 0, 1, 8, 7), and then tinker with an algorithm until that list was in order? (0 1 2 3 4 5 6 7 8 9)
------------
Here's the thing about programming: you don't have to travel very far before you get into the "nobody knows the answer". The internet provides enough information for the first ~2 months on the job. Specialized books on your topic (ex: GPUs, HPC, OpenMP, etc. etc.) may cover another 1 or 2 months of training on the job.
After that? Nobody in the world is doing what you do. Nobody has to work with your particular configuration of tools, your particular problems (performance? Bugs? Architecture?). Your particular office politics. Literally no one else in the world. And yet, you'll be responsible for coming up with a solution that works, even without any guides.
That's why people like testing people "without the internet". Because in most cases, there's no guide to tell you how to progress a real project in the real world.
Hmmm... with Mergesort, you gotta be copying the data to new buffers, malloc-ing arrays and new arrays, managing the data etc. etc.
Quicksort can be trivially done in-place. And yes, I know Merge-sort has an in-place variation, but in-place Mergesort is non-intuitive IMO.
-------
I guess merge-sort is easy if you are willing to call malloc / free (or new / delete) over-and-over again. But those functions scare me. I prefer to get things done without dynamic memory, especially if its a whiteboard interview.
Quicksort does require more brainpower than selection / insertion / bubble sorts. But if I were to use a recursive methodology, trying to do quicksort would be my strategy.
Whoever said it, I have a super hard time believing DHH couldn’t implement bubble sort on a whiteboard.
Am I the only one? I get that people hate whiteboard/algorithm interviews, but bubble sort?
Everyone in this field should be able to do this, maybe not right away, maybe not without bugs, but with help within 45 minutes.If you can't do that without help in 45 minutes, what can you actually do?
I think the actual problem is most developers / programmers are just bad at the job, and then go in a huff when this is pointed out.
For people who know about knots out there... its like asking for somebody to tie a Granny Knot instead of a square-knot. Anyone who actually practiced knot-tying will "accidentally" tie a square-knot instead (because the square-knot is stronger for the same level of effort).
Similarly, bubble sort is the "bad" way to write insertion sort. Anybody who actually practiced writing sorts will write insertion sort by accident instead.
But bubblesort? There's no invariant. Sure, I can tell you that it's this structure:
But, with the lack of invariants, I don't know how to fill in the ? correctly. With trial and error, I could write a correct sort from this template. But insertion sort and selection sort also follow this template (as does any other sorting network if you try hard enough), and I can't guarantee that I'd hit bubblesort instead of those.If you're trying to recall this algorithm from memory by comparing it with other sorting algorithms you've memorized, you're probably doing it wrong, because there's hardly a place for real world usage of bubble sort, so your memory of it is naturally going to fade away. The trick is - you don't even need to memorize it or recall any structure to fit it into. Just imagine an inefficiently bubbling array of numbers in your head and that's it.
More importantly, what you wrote is a selection sort, not a bubble sort!
A bubble sort swaps neighboring terms. Eg, if I interpret the code in 2.1 of https://users.cs.duke.edu/~ola/bubble/bubble.html correctly, the 'definitive' version is:
You don't need to memorize multiplication table to be good at math, but this is an equivalent of saying "I wouldn't even be able to add two numbers together in my head!".
If I wrote it down every time someone claims that "this is so important any engineer should know it," I'd have a book as thick as the bible full of trivia. All of it so easy, and yet in every position you can find a person who hasn't mastered it all. Maybe it isn't all that important after all. Most of these people are capable of finding help should it come to that.
Merge sort? Quick sort? Bogosort? Maybe not. But bubble sort yes.
Just like an engineer even at the most junior level should be able to swap and write fizz buzz. If you can’t do that you certainly cannot call yourself an engineer.
Another one I've encountered recently is priority queues. Here, memory requirements and operation runtimes depend on which operations are supported -- insert/pop heaps are faster than insert/decrease/pop heaps are faster than insert/update/pop heaps. And if heap operations are your innermost loop on your critical path, you can get huge gains from rolling your own -- because a standard library's priority queue will support whichever operations it supports and you can't pick features a la carte.
But no, I never do this without a search engine handy.
But even for these simple data structures, I am much more comfortable implementing them with an algorithm textbook in front of me (or some other resource with similar level of detail), simply because it greatly reduces the scope for implementing the data structure itself incorrectly and, secure in that knowledge, I can focus my debugging on the algorithm itself.
I always thought merge/quick sorts accounted for 99.9% of use cases and only ever really learned about those.
Insertion and selection sort are also O(N^2), but sorts like merge and quick will use them to sort small sublists in their recursive cases because they are fast when input is small enough.
It's definitely easy to implement, it just had me worried because I had never heard of it!
It's actually usable for small enough n. I once coded it when I expected n to be 4 or less, and I'm sure the person who replaced it cursed my name when that expectation turned out to be false.
If someone just says "hey, implement bubblesort", that's pretty awful though. Then it's just testing your memory and/or gating by people that studied a particular algorithms curriculum. (Though _many_ intro algorithms courses go through sorting and most of those mention bubble sort probably)
I only remember it because a machine language book for the Motorola 6809 used it as an introductory program.
If you have an application that only has to sort small lists, but has to sort a lot of them, it is quite possible that an O(n^2) sort like bubble, insertion, or selection sort will be better than merge/quick sort.
Among the O(n^2) sorts, insertion almost always will be faster than bubble, so you probably wouldn't actually choose bubble sort.
It's more just that I am concerned I would be cornered trying to remember what 'bubble sort' is. It's not difficult to write the algorithm per se--just hard to remember what 'bubble sort' means.
Personally I've never found this case myself, but regarding why it's used some times, the O(n²) is the worst case scenario. The best case scenario is O(2n) which is really good, so for lists that are sorted or almost sorted it works well.
Other algorithms like timsort have O(n) for the best case scenario, but O(n) only tells you how many times you go through the loop. Without actually measuring it, I would expect each iteration of timsort to be at more than twice as expensive as bubble sort, so in this case O(2n) would be cheaper than O(n).
When you know with a certain degree of certainty how is the data you expect in most cases, some times it's kinda easy to make a more efficient algorithm than the one that is the best for the average scenario.
- Graphics
- Machine learning
- Gaming
Imagine yourself working in these fields and not being able to implement algorithms, you wouldn't be a super useful teammate.
The point is that as an interviewer/employer you risk not getting the information you've asked for. Someone who is able to memorize interview algorithms isn't necessarily a good fit for the role you are trying to fill. Forcing people to memorize the details of these concepts just to comply in an interview is often a waste of time for both parties.
Even as a gamedev/ML guy you don't have to reinvent the wheel everyday. You have to understand what is available, judge about the pros and cons of different solutions, pick the right one and build a good system. Preferably on time.
Or they use several languages. Say you have client side code in JavaScript, with the client served by PHP on the server. You've got some log analysis scripts in Perl. You've got some SOAP services in Java. You've got some machine learning stuff in Python. You've got a mobile app in Swift.
It's real easy to get confused about which of foo.length, strlen($foo), length($foo), foo.length(), len(foo), or foo.characters.count is the right one for the language you are dealing with at the moment.
Actually I always thought the opposite - if you started programming in the 80’s (maybe early 90’s), you had to write sort algorithms and you had to study them in college, so you’re going to be bound to remember them at least well enough to come up with the “base case” (i.e. bubble sort). I do assume that younger programmers, especially self-taught types, probably haven’t come across these to if they did, it was one lecture, once, ten years ago, memorized and forgotten because they never applied it again.
Personal anecdote: I recently underwent an interview process for a position in my field of expertise (computer vision) consisting of multiple in-person stages, whiteboard coding, product design and a take-home assignment that required developing a foundational (bubble-sort like) algorithm from scratch. After successfully completing all of these hurdles, I ended up with a low-ball offer targeting entry-level candidates. If we could have discussed the compensation up front, I wouldn’t even have bothered.
Consider that when athletes are scouted, they are usually not asked to play in a full game of their sport. But instead certain stats like 'how fast can he run 100m' and 'how high can he jump' are used.
Sure, in a real game you will never run 100m in a straight line on asphalt--but the speed at which one runs 100m in a straight line is a good proxy for how fast one can maneuver during real play.
Sometimes analogies are not really meant to be perfect, but just simpler methods of communicating information.
Teams rarely sign players based solely on measures like this, and those that do frequently regret it.
Additionally, the nature of contracts in professional sports are very different from regular employment. Players are cut or traded frequently, often find themselves on very team-friendly deals when unproven, and are granted employment in time-limited blocks.
The general point I am making is: these are not trying to measure actual job tasks, but instead measuring something that (they hope) is closely related to, or correlated with one's ability to perform the job. The idea is that if one can do these sorts of problems, one can probably do the actual job at hand.
This is a claim about the intentions behind these practices.
Intentions aside, the whole point of this perennially recurring discourse is about effectiveness — that certain overused methods of filtering job candidates are ineffective on their own terms — and negative side effects — that they're biased against people with non-traditional / from underrepresented backgrounds.
Why should an interview question reward you/require you to remember this? If I actually had to solve a real-world problem similar to this, I would google it, see a solution that iterated through the characters with a for loop and go “oh yeah, I forgot you could do that. Duh.” Why am I not allowed to google dumb things? On most days, my brain is focused on high-level abstractions that tie together two or more tools via disparate APIs, why the hell should I remember or think about for loops?
In the other side, I always pitch "We do this or that, this is what we need help for, and this is how much we can pay (or: how much is your rate?)".
Is an amazing filter. Specially when you don't have much cash to give. Because: If I can't pay... why lost more time? And if I can pay and the other accept it.. only need to solve if is capable.
This is also for my customers. I put a money estimate as soon as possible, or ask upfront what is the budget range.
Is an amazing filter. Because: If I the customer can't pay... why lost more time? And if can pay I only need to solve why I'm a good fit.
The less hidden variables the better for all...
After that, they offered me something like $10k less than what I had asked for and minimum vacation, saying that when you add in the value of all additional benefits (health insurance, rrsp benefits), you end up at the salary I had originally requested. Did not exactly win me over.
When the counter-offer is TOO BAD you can say, 100% sure, the experience moving forward will be VERY BAD. I'm not in a market where programming is well paid, and this is the most certain sign the customer will not pay on time, or even at all..
They spent two hours doing coding interviews and 15 minutes asking me about kubernetes, if that.
Somehow we arent really adept at interviewing at what the day-to-day requirements of a position.
Instead were much more interested in edge-case stuff like bubble sort.
I wonder if this is some assessment of "are they capable of substantially more complex tasks, and if so, safe to assume they're capable of less-complex minutiae.
Seems about right, as often these evaluation type things are proxies.
The flip side is that in mature companies like the one I work for, where professional interviews are more of the rule, we don't get the best candidates, at least not right now. I could imagine that super attractive startups can afford to set the bar higher and still get enough applicants.
These kinds of anecdotes make me often wonder if candidates are "disqualified" for far more superficial reasons, and if interviewers hone in on pedantry like this to legitimize their reasoning perhaps even unconsciously. I have trouble believing most candidates wouldn't make at least one trivial mistake of that sort and I am equally reluctant to believe the same interviewers would disqualify any given candidate for a mistake so trivial.
Chinese is not a great example. Native speakers have trouble reading and writing their own language; it is so complicated that people cannot remember how to write commonly-spoken words or how to read. [0][1] (Choice moment from [1] is when a university student says that Chinese literacy is as difficult as English!)
Perhaps we can do better as a community to design better languages, but also we should not condone people claiming that they know the languages when they clearly don't. Yes, Python could be easier; no, Python is not that hard.
[0] https://www.youtube.com/watch?v=HQh1_zyig1M
[1] https://www.youtube.com/watch?v=zxHskrqMqII
If the tech lead spent a lot of time working with another language that made the length an attribute, I think it would be reasonable for them to need to look it up often.
https://apidock.com/ruby/String/count https://docs.oracle.com/javase/7/docs/api/java/lang/String.h... https://developer.apple.com/documentation/swift/string/30035...
So you feel confident in asserting that, at the time that the person made that tweet, the quality of the Python code that they shipped was poor, or it took an inordinate amount of time to produce? All because they had to look up len()?
Furthermore, I should point out that it's not out of the imagination that someone wouldn't use len() all that heavily. Python has functional operators that let you do map/reduce-style operations on lists, strings, dicts, etc. that don't require you to use length all that much. My most recent python script only uses len() in two places for more robust error reporting.
OK, I agree, it's kind of like saying that.
But it's also kind of not like saying that.
Incompetence in driving and incompetence in software development are measured in completely different ways for completely different reasons. In driving, notions of what you definitely should know in order to qualify as "competent" extend from the intrinsic risk to other people's well-being. You can't simply transpose those notions onto the low-stakes sandbox environment that is software development. In software development, process is only important as far as it hinders or helps to deliver good code; competence should be dictated purely by results. All of the actual competence of driving comes during the actual process part; successfully reaching your destination is actually considered to be less important than simply not fucking anything up on the way there.
Sometimes I pick up a video game that I haven't played in weeks, and perform actions incorrectly because the button layout has been overwritten by the button layout of a similar and more recent game. It would foolish to say I'm wholly incompetent at either game; I still have a strong concept of what I should be doing and what I intend to do, it's just that I'm fumbling a bit at the specifics of executing my intent. Am I incompetent for looking up the button layout? Am I incompetent, but only for the 1 hour that it takes me to get back in the groove of things?
Declaring someone is incompetent is a bold assertion to make from such limited information. At the end of the day you either deliver good code in good time or you don't. I would be extremely reluctant to determine this guy can't deliver good code because he had to look something up. Figures no one will hire me.
See, I’d be extremely reluctant to assume the opposite - that he can, even though he doesn’t remember “len”. Given this one bit of information, all I know is that he has exactly one thing in common with everybody who doesn’t know how to program in Python: he doesn’t know the function for determining the length of a string. Now, he may (somehow?) know everything else about Python except for that one thing: I’m assuming the interviewer was a bit surprised (as I would be) that somebody presenting themselves as a Python programmer didn’t know len, but went ahead and asked him a few more questions which he may well have nailed. If the answer to every question was “I don’t know, I have to look it up”, you’d pass on him, too. I just can’t picture how anybody who didn’t remember that could remember much else, but I guess that’s why job interviews last an hour or so.
This seems like a really flawed way of approaching most things. Why assume anything? And if you're going to assume anything, why only factor in that one bit of information, and not any other context. How about the fact that he's been coding for 30 years and works at Google. Is that also relevant?
>I’m assuming the interviewer was a bit surprised
There was no interviewer in this situation. His tweet was not in regards to any interview. Did you read the article?
>If the answer to every question was “I don’t know, I have to look it up”, you’d pass on him, too.
But if I were to do so, at least in such a case I would be basing my suppositions on more than just one thing.
Usually it's just 'How many years of experience do you have in XYZ?' and it's almost never enough. Doesn't matter if your experience is in something similar ('Oh you used Spring boot! We are looking for Spring MVC!') and of course they just care about decades of 'experience'--doesn't matter if you actually know it well.
Then the job ends up not having any relation to what was posted anyway, so it was all moot.
Yes, I am salty. I am sick of taking 'exciting' opportunities just to end up babysitting software that has no relation to the posted skills/requirements.
If you don't remember bubblesort the interviewer could explain what the algo does and then you should be able to implement it. I'm all for looking stuff up on the web and we all have phones in our pockets but if there's to be a minimum bar it shouldn't be lower than bubblesort.
or hell just ask them if they can do a whiteboard problem for you. See how the recruiter likes it. See if they do as good as you. Flip the script so to speak!
A persons ability to think through a problem and communicate it clearly will get them 75% through the hiring process in my books. (Another ~10% is curiosity).