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

Programmers can’t write algorithms without help

queworx.com

Post reply on HN
Print view View original

71–80 of 105 posts

Re: Programmers can’t write algorithms without help

#71

Post by [deleted] »

smoll wrote: post #41
oneplane wrote: post #17

Earlier quoted context omitted.

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 num…

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/req…

[deleted]

Re: Programmers can’t write algorithms without help

#72

Post by klyrs »

AnimalMuppet wrote: post #21
starbugs wrote: post #2

> 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 exi…

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.

Re: Programmers can’t write algorithms without help

#73

Post by SAI_Peregrinus »

stunt wrote: post #4

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.

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.

Re: Programmers can’t write algorithms without help

#74

Post by vonmoltke »

Gunax wrote: post #31
oneplane wrote: post #17

Earlier quoted context omitted.

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 num…

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…

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

Re: Programmers can’t write algorithms without help

#75

Post by jcranmer »

klyrs wrote: post #72
AnimalMuppet wrote: post #21

Earlier quoted context omitted.

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…

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.

Re: Programmers can’t write algorithms without help

#76

Post by Eleopteryx »

lidHanteyk wrote: post #34

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…

>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()?

Re: Programmers can’t write algorithms without help

#77

Post by dragontamer »

seba_dos1 wrote: post #50
jcranmer wrote: post #44

Earlier quoted context omitted.

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.

Re: Programmers can’t write algorithms without help

#78

Post by commandlinefan »

Eleopteryx wrote: post #76
lidHanteyk wrote: post #34

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…

>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()?

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

Re: Programmers can’t write algorithms without help

#79

Post by glitchc »

opportune wrote: post #40
glitchc wrote: post #6

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…

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

Yes indeed. And I received the standard "we have a large range and offer based on experience and expertise," but no explicit figures.

Re: Programmers can’t write algorithms without help

#80

Post by jcranmer »

seba_dos1 wrote: post #50
jcranmer wrote: post #44

Earlier quoted context omitted.

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.

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]
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.
Post reply on HN