10 ms·

Programmers can’t write algorithms without help

45 points by cryo8822 7y ago

starbugs 7y ago
> Programmers can’t write algorithms without help 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.
- Tehchops 7y ago
  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.
  - starbugs 7y ago
    Yes, being able to write a DFS is definitely a good thing. For more complex stuff I don't mind if you need to look it up.
  - rhinoceraptor 7y ago
    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.
    - jimbokun 7y ago
      > that isn't memoizing an array map "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?
- oneplane 7y ago
  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.
  - a_t48 7y ago
    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.
    - oneplane 7y ago
      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.
- Sarki 7y ago
  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. Must all painters be artists?
  - starbugs 7y ago
    I would go as far as saying that an "artist" might be detrimental to reaching your goal in a lot of cases, especially if a team is involved.
    - mark-r 7y ago
      To stretch the analogy to the breaking point, you probably don't want an "artist" to paint your living room walls.
- dickeytk 7y ago
  I get your point, but why would you pick bubble sort? 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 https://m.youtube.com/watch?v=k4RRi_ntQc8
  - starbugs 7y ago
    I picked bubble sort, because it's literally the example from the first sentence of the article: > 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.
    - dragontamer 7y ago
      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.
      - a_t48 7y ago
        Mergesort is also worth looking into.
- nraynaud 7y ago
  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.
- AnimalMuppet 7y ago
  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?
  - klyrs 7y ago
    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.
    - jcranmer 7y ago
      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.
- Gunax 7y ago
  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.
  - MatekCopatek 7y ago
    I think it's just the simplest sort to describe/implement on a whiteboard.
  - cinnamonheart 7y ago
    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.
    - Gunax 7y ago
      I see. I would hope one would give a description of what bubble sort is during the question. It's definitely easy to implement, it just had me worried because I had never heard of it!
  - mark-r 7y ago
    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.
    - kadoban 7y ago
      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.
- mark-r 7y ago
  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.
- tiborsaas 7y ago
  > And that might be a good thing. - 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.
  - starbugs 7y ago
    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.
stunt 7y ago
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.
- kiba 7y ago
  You can store those information inside a SRS system which lets you remember those algorithms essentially forever.
- tzs 7y ago
  > 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.
- SAI_Peregrinus 7y ago
  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.
- commandlinefan 7y ago
  > Nobody remembers them for ever 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.
glitchc 7y ago
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.
- 99052882514569 7y ago
  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.
  - oneplane 7y ago
    I'd say give them a doubly-linked list for their doubly-stupid hiring process.
- oneplane 7y ago
  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.
  - Gunax 7y 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.
commandlinefan 7y ago
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.
- delinquentme 7y ago
  Yes you're the exception. 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.
- zwieback 7y ago
  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.
- Eleopteryx 7y ago
  >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.
kps 7y ago
Shouldn't be a surprise; the person who wrote the algorithm without help took more than 15 minutes, and got a paper or a PhD out of it.
- mark-r 7y ago
  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.
  - commandlinefan 7y ago
    You should have written a paper.
    - mark-r 7y ago
      I was hardly the first person to figure it out.
deleted 7y ago
[deleted]
lidHanteyk 7y ago
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. [0] https://www.youtube.com/watch?v=HQh1_zyig1M https://www.youtube.com/watch?v=HQh1_zyig1M [1] https://www.youtube.com/watch?v=zxHskrqMqII https://www.youtube.com/watch?v=zxHskrqMqII
- drizze 7y ago
  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. https://apidock.com/ruby/String/count https://apidock.com/ruby/String/count https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#length() https://docs.oracle.com/javase/7/docs/api/java/lang/String.h... https://developer.apple.com/documentation/swift/string/3003522-count https://developer.apple.com/documentation/swift/string/30035...
- Eleopteryx 7y ago
  >Yes, they're incompetent. 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()?
  - commandlinefan 7y ago
    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).
Gunax 7y ago
I wish I got asked questions like this. 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.
- jagged-chisel 7y ago
  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..."
zwieback 7y ago
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.
growlist 7y ago
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?!
- arthev 7y ago
  Yes.
gremlinsinc 7y ago
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!
stephenmm 7y ago
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).
loopz 7y ago
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.
dplgk 7y ago
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.

45 points by cryo8822 7y ago

> Programmers can’t write algorithms without help 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.

Tehchops 7y ago
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.
- starbugs 7y ago
  Yes, being able to write a DFS is definitely a good thing. For more complex stuff I don't mind if you need to look it up.
- rhinoceraptor 7y ago
  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.
  - jimbokun 7y ago
    > that isn't memoizing an array map "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?
oneplane 7y ago
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.
- a_t48 7y ago
  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.
  - oneplane 7y ago
    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.
Sarki 7y ago
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. Must all painters be artists?
- starbugs 7y ago
  I would go as far as saying that an "artist" might be detrimental to reaching your goal in a lot of cases, especially if a team is involved.
  - mark-r 7y ago
    To stretch the analogy to the breaking point, you probably don't want an "artist" to paint your living room walls.
dickeytk 7y ago
I get your point, but why would you pick bubble sort? 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 https://m.youtube.com/watch?v=k4RRi_ntQc8
- starbugs 7y ago
  I picked bubble sort, because it's literally the example from the first sentence of the article: > 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.
  - dragontamer 7y ago
    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.
    - a_t48 7y ago
      Mergesort is also worth looking into.
nraynaud 7y ago
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.
AnimalMuppet 7y ago
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?
- klyrs 7y ago
  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.
  - jcranmer 7y ago
    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.
Gunax 7y ago
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.
- MatekCopatek 7y ago
  I think it's just the simplest sort to describe/implement on a whiteboard.
- cinnamonheart 7y ago
  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.
  - Gunax 7y ago
    I see. I would hope one would give a description of what bubble sort is during the question. It's definitely easy to implement, it just had me worried because I had never heard of it!
- mark-r 7y ago
  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.
  - kadoban 7y ago
    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.
mark-r 7y ago
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.
tiborsaas 7y ago
> And that might be a good thing. - 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.
- starbugs 7y ago
  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.

stunt 7y ago

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.

kiba 7y ago
You can store those information inside a SRS system which lets you remember those algorithms essentially forever.
tzs 7y ago
> 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.
SAI_Peregrinus 7y ago
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.
commandlinefan 7y ago
> Nobody remembers them for ever 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.

glitchc 7y ago

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.

99052882514569 7y ago
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.
- oneplane 7y ago
  I'd say give them a doubly-linked list for their doubly-stupid hiring process.
oneplane 7y ago
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.
- Gunax 7y 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.

commandlinefan 7y ago

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.

delinquentme 7y ago
Yes you're the exception. 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.
zwieback 7y ago
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.
Eleopteryx 7y ago
>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.

kps 7y ago

Shouldn't be a surprise; the person who wrote the algorithm without help took more than 15 minutes, and got a paper or a PhD out of it.

mark-r 7y ago
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.
- commandlinefan 7y ago
  You should have written a paper.
  - mark-r 7y ago
    I was hardly the first person to figure it out.

deleted 7y ago

[deleted]

lidHanteyk 7y ago

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. [0] https://www.youtube.com/watch?v=HQh1_zyig1M https://www.youtube.com/watch?v=HQh1_zyig1M [1] https://www.youtube.com/watch?v=zxHskrqMqII https://www.youtube.com/watch?v=zxHskrqMqII

drizze 7y ago
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. https://apidock.com/ruby/String/count https://apidock.com/ruby/String/count https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#length() https://docs.oracle.com/javase/7/docs/api/java/lang/String.h... https://developer.apple.com/documentation/swift/string/3003522-count https://developer.apple.com/documentation/swift/string/30035...
Eleopteryx 7y ago
>Yes, they're incompetent. 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()?
- commandlinefan 7y ago
  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).

Gunax 7y ago

I wish I got asked questions like this. 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.

jagged-chisel 7y ago
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..."

zwieback 7y ago

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.

growlist 7y ago

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?!

arthev 7y ago
Yes.

gremlinsinc 7y ago

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!

stephenmm 7y ago

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).

loopz 7y ago

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.

dplgk 7y ago

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.