3 ms·

Yes, you should never be reimplementing something that's in a standard library and for what it's worth I would never expect an interview candidate to know how t

Yes, you should never be reimplementing something that's in a standard library and for what it's worth I would never expect an interview candidate to know how to implement a red-black tree. What I meant was that knowing core algorithms and data structures is important so you can recognise familiar problems so you avoid reinventing the wheel + you know where to look for answers. Maybe you have to use some clever combination of data structures to model your data efficiently. Maybe your data is actually a graph so now you can lean on graph algorithms. Maybe you just realised you're naive implementation to answer some question about your data has n^2 growth so now you can consider if a different data structure would help. Personally, I find people that have poor knowledge of data structures and algorithms are the ones that will reinvent the wheel the most as they don't know what exists already.

lmm 9y ago
What do you mean by "knowing core algorithms and data structures" then? Because for me that phrase would definitely include knowing how to implement your own red-black tree, hash table, linked list and so on.
- ubernostrum 9y ago
  Being able to implement off the top of one's head is a skill that fades as soon as one is no longer required to do so. Requiring it as a criterion of hiring is, essentially, a back-door way of saying "we only hire people fresh out of college", since they're the ones who've recently been having to do this stuff on exams and have it fresh in their minds.
  - seanwilson 9y ago
    > Being able to implement off the top of one's head is a skill that fades as soon as one is no longer required to do so. I haven't implemented a hash table, linked list, growable array or binary tree for years but know I could because I understand how they work and I select which one to use often while coding. I find it hard to understand how you could claim to know how those data structures work and not be able to implement them.
    - sidlls 9y ago
      My point was that most of the time one doesn't need to know how they work in the first place for the vast majority of programming. Simply memorizing or referencing a card with very simple performance metrics (e.g. "dict: fast map of keys to values; array: very fast lookup by integer index") is sufficient for most cases today. Very few people who are doing any programming work need to know that the "dict" is a hashtable or some esoteric data structure with similar performance, or even anything else at all about it except for the API for it.
      - seanwilson 9y ago
        If someone can memorise how a dictionary and an array work, why would they have trouble quickly understanding how a hash table works for example? To me, coding for years and never coming across or being curious about understanding hash tables when they're applicable in so many places and not hard to understand is a bad sign. I don't care about more esoteric data structures but linked lists, hash tables, arrays and binary trees should be basic knowledge.
        sidlls 9y ago
        They wouldn't necessarily have trouble understanding what's under the hood, and that isn't my contention anyway: I contend that whether they can and whether they need (or even ought) to do so are separate questions, most of the time with the latter answered in the negative.
- seanwilson 9y ago
  I mean knowing the memory and runtime costs of basic data structures like binary trees, linked lists, hash tables and arrays along with typical algorithms applied to them like insertion, removal and searching. Implementing each of those data structures (naively at least) shouldn't be challenging if you understand how they work. Red-black trees however are notoriously fiddly to implement; just knowing they exist is good enough in my opinion and you'd likely never have to implement anything remotely similar. I'm not advocating memorising implementation details but learning general concepts. Again, I'm not saying you should be writing your own version of these data structures but knowing they exist and recognising when you're implementing something that fits their mould is helpful.

lmm 9y ago

What do you mean by "knowing core algorithms and data structures" then? Because for me that phrase would definitely include knowing how to implement your own red-black tree, hash table, linked list and so on.

ubernostrum 9y ago
Being able to implement off the top of one's head is a skill that fades as soon as one is no longer required to do so. Requiring it as a criterion of hiring is, essentially, a back-door way of saying "we only hire people fresh out of college", since they're the ones who've recently been having to do this stuff on exams and have it fresh in their minds.
- seanwilson 9y ago
  > Being able to implement off the top of one's head is a skill that fades as soon as one is no longer required to do so. I haven't implemented a hash table, linked list, growable array or binary tree for years but know I could because I understand how they work and I select which one to use often while coding. I find it hard to understand how you could claim to know how those data structures work and not be able to implement them.
  - sidlls 9y ago
    My point was that most of the time one doesn't need to know how they work in the first place for the vast majority of programming. Simply memorizing or referencing a card with very simple performance metrics (e.g. "dict: fast map of keys to values; array: very fast lookup by integer index") is sufficient for most cases today. Very few people who are doing any programming work need to know that the "dict" is a hashtable or some esoteric data structure with similar performance, or even anything else at all about it except for the API for it.
    - seanwilson 9y ago
      If someone can memorise how a dictionary and an array work, why would they have trouble quickly understanding how a hash table works for example? To me, coding for years and never coming across or being curious about understanding hash tables when they're applicable in so many places and not hard to understand is a bad sign. I don't care about more esoteric data structures but linked lists, hash tables, arrays and binary trees should be basic knowledge.
      - sidlls 9y ago
        They wouldn't necessarily have trouble understanding what's under the hood, and that isn't my contention anyway: I contend that whether they can and whether they need (or even ought) to do so are separate questions, most of the time with the latter answered in the negative.
seanwilson 9y ago
I mean knowing the memory and runtime costs of basic data structures like binary trees, linked lists, hash tables and arrays along with typical algorithms applied to them like insertion, removal and searching. Implementing each of those data structures (naively at least) shouldn't be challenging if you understand how they work. Red-black trees however are notoriously fiddly to implement; just knowing they exist is good enough in my opinion and you'd likely never have to implement anything remotely similar. I'm not advocating memorising implementation details but learning general concepts. Again, I'm not saying you should be writing your own version of these data structures but knowing they exist and recognising when you're implementing something that fits their mould is helpful.