4 ms·

I don't really see how you can choose one without at least a rough idea of the other. How do you know what data structure to use if you have no idea how you'll

I don't really see how you can choose one without at least a rough idea of the other. How do you know what data structure to use if you have no idea how you'll be accessing the data?

softfalcon 3y ago
You're not wrong, data structures and an algorithm for data retrieval are often connected and developed together. You often see someone come up with a novel way of traversing data, then they model an elegant data structure to match it and enable said traversal. What isn't covered in this flow is how composition of multiple data-structure/algorithm pairings work together amidst many others. It's often not an algorithm on its own that defines an overall solution. It's the connecting of many of them together, to build a whole software stack, domain language, etc. When you understand the algorithms, the corresponding data structures, when to use them, similarities in various frameworks in your chosen domain, how that analogues to your current problem set, etc you really start getting somewhere.
- eska 3y ago
  * data structures and an algorithm for data retrieval are often connected and developed together* Often? Always! An algorithm always only works on a certain data data structure.
  - nonrandomstring 3y ago
    Or as Fred Brooks put it: " Show me your tables, and I won't usually need your flowcharts; they'll be obvious." But to be fair, you need to be a pretty damn good comp sci person (and actively thinking in algs and DS) to quickly look at DS and see the "obvious" processing implied.
    - sfn42 3y ago
      A problem I see a lot is when the flowcharts should be obvious, but aren't because whoever wrote the code didn't write the obvious solution. Instead they wrote a horrible buggy mess that tries (and usually fails at least a little) to do the same thing as the obvious solution but with much more, and more convoluted, code.
  - softfalcon 3y ago
    I appreciate your particularness in this regard, and you'll have to forgive me as I've spent a lot of time with folks who are very wary of the word "data structures". I tend to use softer words like "often" as it makes folks feel less defensive towards the discussion. If someone came up to you and told you that your outlook on something is 100% definitively wrong, you might balk at the statement merely because I said "100%". Just as you have stated "Always!" and corrected me so emphatically. Since I've found this to be a difficult topic for some, and given this is a public forum, I chose to be cautious in my wording.
    - a1369209993 3y ago
      Also they're just straightforwardly wrong. For example, binary search works on a array, or on a predicate like \x->(x*x <= 2.0), or on a hash table with contiguous integer indexes, or even on a linked list. Of course it works very badly on a linked list (worse than linear scanning unless the comparison is ruinously expensive), but they didn't say "An algorithm always only works properly on a certain data data structure.".
      - eska 3y ago
        A binary search on a linked list is a different algorithm than on a a sorted array (which is different from a generic array). In this case linked lists don’t have random access for example. So binary search on a linked list is actually not possible.
        a1369209993 3y ago
        > linked lists don't have random access `list.get_nth(n)` has O(N) runtime, as does `list.length()`, so binary search is actually completely possible, with runtime O(N^2) (aka "works very badly"). (Fair point that all four data structures need to be sorted, though, although ideally that would go without saying, since it's kind of inherent in what binary search is.)
        eska 3y ago
no_wizard 3y ago
I have found you can, even if its slowest of the slowest, brute force your way through traversal of a data structure, if you need to, since most languages (all?) give you iteration out of the box. Being able to choose the appropriate data structure and explain trade-offs etc is much more valuable than simply knowing how to reverse a binary tree sorta stuff. As I noted elsewhere in the thread, I haven't interviewed in awhile where I needed to grind out DS&A questions, but at the time where I did, I often found myself given a particular structure and asked to traverse it in some way, with is pretty heavy on the algorithmic thinking but not really testing my knowledge on data structures themselves. Sounds to me like things have become a little more even handed out there
- BearOso 3y ago
  > Being able to choose the appropriate data structure and explain trade-offs etc is much more valuable than simply knowing how to reverse a binary tree sorta stuff. Indeed. The simplest way to invert a binary tree is to include an "invert" flag in the data structure. If it's set, walk the tree right to left instead of left to right.

I don't really see how you can choose one without at least a rough idea of the other. How do you know what data structure to use if you have no idea how you'll be accessing the data?

softfalcon 3y ago

You're not wrong, data structures and an algorithm for data retrieval are often connected and developed together. You often see someone come up with a novel way of traversing data, then they model an elegant data structure to match it and enable said traversal. What isn't covered in this flow is how composition of multiple data-structure/algorithm pairings work together amidst many others. It's often not an algorithm on its own that defines an overall solution. It's the connecting of many of them together, to build a whole software stack, domain language, etc. When you understand the algorithms, the corresponding data structures, when to use them, similarities in various frameworks in your chosen domain, how that analogues to your current problem set, etc you really start getting somewhere.

eska 3y ago
* data structures and an algorithm for data retrieval are often connected and developed together* Often? Always! An algorithm always only works on a certain data data structure.
- nonrandomstring 3y ago
  Or as Fred Brooks put it: " Show me your tables, and I won't usually need your flowcharts; they'll be obvious." But to be fair, you need to be a pretty damn good comp sci person (and actively thinking in algs and DS) to quickly look at DS and see the "obvious" processing implied.
  - sfn42 3y ago
    A problem I see a lot is when the flowcharts should be obvious, but aren't because whoever wrote the code didn't write the obvious solution. Instead they wrote a horrible buggy mess that tries (and usually fails at least a little) to do the same thing as the obvious solution but with much more, and more convoluted, code.
- softfalcon 3y ago
  I appreciate your particularness in this regard, and you'll have to forgive me as I've spent a lot of time with folks who are very wary of the word "data structures". I tend to use softer words like "often" as it makes folks feel less defensive towards the discussion. If someone came up to you and told you that your outlook on something is 100% definitively wrong, you might balk at the statement merely because I said "100%". Just as you have stated "Always!" and corrected me so emphatically. Since I've found this to be a difficult topic for some, and given this is a public forum, I chose to be cautious in my wording.
  - a1369209993 3y ago
    Also they're just straightforwardly wrong. For example, binary search works on a array, or on a predicate like \x->(x*x <= 2.0), or on a hash table with contiguous integer indexes, or even on a linked list. Of course it works very badly on a linked list (worse than linear scanning unless the comparison is ruinously expensive), but they didn't say "An algorithm always only works properly on a certain data data structure.".
    - eska 3y ago
      A binary search on a linked list is a different algorithm than on a a sorted array (which is different from a generic array). In this case linked lists don’t have random access for example. So binary search on a linked list is actually not possible.
      - a1369209993 3y ago
        > linked lists don't have random access `list.get_nth(n)` has O(N) runtime, as does `list.length()`, so binary search is actually completely possible, with runtime O(N^2) (aka "works very badly"). (Fair point that all four data structures need to be sorted, though, although ideally that would go without saying, since it's kind of inherent in what binary search is.)
        eska 3y ago

no_wizard 3y ago

I have found you can, even if its slowest of the slowest, brute force your way through traversal of a data structure, if you need to, since most languages (all?) give you iteration out of the box. Being able to choose the appropriate data structure and explain trade-offs etc is much more valuable than simply knowing how to reverse a binary tree sorta stuff. As I noted elsewhere in the thread, I haven't interviewed in awhile where I needed to grind out DS&A questions, but at the time where I did, I often found myself given a particular structure and asked to traverse it in some way, with is pretty heavy on the algorithmic thinking but not really testing my knowledge on data structures themselves. Sounds to me like things have become a little more even handed out there

BearOso 3y ago
> Being able to choose the appropriate data structure and explain trade-offs etc is much more valuable than simply knowing how to reverse a binary tree sorta stuff. Indeed. The simplest way to invert a binary tree is to include an "invert" flag in the data structure. If it's set, walk the tree right to left instead of left to right.