Programmers can’t write algorithms without help
queworx.com
queworx.com
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.
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.
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?
for i = 0..n:
for j = i..n:
if arr[i] > arr[j]:
arr[j], arr[i] = arr[i], arr[j]
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:
for i = ? .. ?:
for j = ? .. ?:
i1, i2 = ?, ?
if A[i1] < A[i2]:
A[i1], A[i2] = A[i2], A[i1]
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
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:
for i = n-1..0:
for j = 0..i:
if arr[j+1] < arr[j]:
arr[j], arr[i] = arr[i], arr[j]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.
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.
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.
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!
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.
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).
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.