5 ms·

You're too forgiving. I turn down interviews when they list "linked lists, hashing, breadth/depth first search" on their study guide. I've never had to write

by supran 9y ago

You're too forgiving. I turn down interviews when they list "linked lists, hashing, breadth/depth first search" on their study guide. I've never had to write a linked list EVER in my career, don't fucking bother me with that shit. Also, if the position is in a language where linked lists would be stupid (i.e. python), then I definitely reject that company. I can explain what everyone of them is, and why you'd want to use them. But I've never written any one of them and I'm not going to spend the time to memorize something I can look up in my CLR book or stackoverflow. It's embarrassing that tech interviewing is still stuck in a 1990s mindset.

emerongi 9y ago
I've written at least 5 linked lists in the past year. They're quite useful.
- Apocryphon 9y ago
  What were you using them for?
  - deleted 9y ago
    [deleted]
  - mickg10 9y ago
    Not sure about GP, but very recently, an open-addressing hashtable that could be traversed in both reverse modification and reverse insertion time order. There are actually some interesting subtleties when doing this for open-addressing hashtables (i.e., entries (and pointers to them) move around when the table rehashes).
- stevenwoo 9y ago
  Five different implementations of linked lists?
  - emerongi 9y ago
    Yes. To be fair, this is the first time in my life I can clearly remember implementing a number of linked lists. I'm pretty sure my lifetime total is not much greater than 5.
DonaldFisk 9y ago
(Singly linked) lists have many advantages (e.g. useful operations on them are side-effect free), but whether they should be used depends upon which problems you solve and which languages you use. It's unsurprising they're used all the time in Lisp, and functional programming languages generally. I'd advise against their use in C or other languages without garbage collectors. They're rarely needed in languages (such as Python and Java) which have vectors and hash tables as basic data structures. I've never found a need for doubly linked lists in any language, for any problem. So you'll either have them built in to the language you'll be using, the company's using the wrong language, or you'll be tackling problems where they're not really needed.
- deathanatos 9y ago
  What language would you recommend using a singly-linked list in, aside from Lisp? Why is it any less valid in non-GC'd languages? (Aside from memory management in C is fraught with error, but that's a problem not unique to singly-linked lists.) I've never looked (at least, that hard) at the language; it was always a question of "is this the appropriate data structure for this task?". Linked-lists have somewhat peculiar time complexities, but occasionally those line up with what you need. (Usually a vector is also as good, time-complexity-wise, and wins out by being contiguous. But if you need O(1) removal…)
  - trishume 9y ago
    Linked lists make way more sense in languages with bump-pointer allocating garbage collectors specifically. In those languages (e.g Haskell, OCaml, Java) allocation is really cheap and they preserve locality so allocating all the links isn't as much of a penalty. Also if you don't have a garbage collector you have to do reference counting, and if you want parallelism your reference counting has to be atomic, which when you're sharing a lot of linked list nodes, is another large penalty.
    - deathanatos 9y ago
      > Linked lists make way more sense in languages with bump-pointer allocating garbage collectors specifically. In those languages (e.g Haskell, OCaml, Java) allocation is really cheap and they preserve locality so allocating all the links isn't as much of a penalty. Such allocation is possible in languages such as C++/Rust/C as well. (Though to how much the standard library in each supports you may vary.) My point was that at least I choose linked lists for the O(1) node insertion/removals in addition to maintaining a sequence of items, a trait pretty much unique to linked lists. It's a matter of whether or not the order notation beats out any additional allocation time and cache effects (Vec/std::vector/continuous-memory lists being more friendly towards cache) > Also if you don't have a garbage collector you have to do reference counting, and if you want parallelism your reference counting has to be atomic, which when you're sharing a lot of linked list nodes, is another large penalty. Neither Rust nor C++'s linked list implementations require ref counting, and neither have a GC. A node is essentially, struct LLNode<T> { LLNode *next; LLNode *prev; // if doubly linked T item; } (the above is pseudo-syntax, adjust appropriately) Rust, for example, knows the linked list is only ever owned by a single person. (Barring either the list or the items being wrapped in Rc/Arc/Mutex/etc., but in that case, of course it is, but that's yet different and doesn't really impinge upon a linked list's general usefulness)
watwut 9y ago
For me it is opposite. If the company gives reasonably sized study guide, I am cool with it. I also implemented linked list like structures (it was not linked list but similar). You don't need to memorize it to suceed, the construction is pretty logical.

by supran 9y ago

emerongi 9y ago

I've written at least 5 linked lists in the past year. They're quite useful.

Apocryphon 9y ago
What were you using them for?
- deleted 9y ago
  [deleted]
- mickg10 9y ago
  Not sure about GP, but very recently, an open-addressing hashtable that could be traversed in both reverse modification and reverse insertion time order. There are actually some interesting subtleties when doing this for open-addressing hashtables (i.e., entries (and pointers to them) move around when the table rehashes).
stevenwoo 9y ago
Five different implementations of linked lists?
- emerongi 9y ago
  Yes. To be fair, this is the first time in my life I can clearly remember implementing a number of linked lists. I'm pretty sure my lifetime total is not much greater than 5.

DonaldFisk 9y ago

(Singly linked) lists have many advantages (e.g. useful operations on them are side-effect free), but whether they should be used depends upon which problems you solve and which languages you use. It's unsurprising they're used all the time in Lisp, and functional programming languages generally. I'd advise against their use in C or other languages without garbage collectors. They're rarely needed in languages (such as Python and Java) which have vectors and hash tables as basic data structures. I've never found a need for doubly linked lists in any language, for any problem. So you'll either have them built in to the language you'll be using, the company's using the wrong language, or you'll be tackling problems where they're not really needed.

deathanatos 9y ago
What language would you recommend using a singly-linked list in, aside from Lisp? Why is it any less valid in non-GC'd languages? (Aside from memory management in C is fraught with error, but that's a problem not unique to singly-linked lists.) I've never looked (at least, that hard) at the language; it was always a question of "is this the appropriate data structure for this task?". Linked-lists have somewhat peculiar time complexities, but occasionally those line up with what you need. (Usually a vector is also as good, time-complexity-wise, and wins out by being contiguous. But if you need O(1) removal…)
- trishume 9y ago
  Linked lists make way more sense in languages with bump-pointer allocating garbage collectors specifically. In those languages (e.g Haskell, OCaml, Java) allocation is really cheap and they preserve locality so allocating all the links isn't as much of a penalty. Also if you don't have a garbage collector you have to do reference counting, and if you want parallelism your reference counting has to be atomic, which when you're sharing a lot of linked list nodes, is another large penalty.
  - deathanatos 9y ago
    > Linked lists make way more sense in languages with bump-pointer allocating garbage collectors specifically. In those languages (e.g Haskell, OCaml, Java) allocation is really cheap and they preserve locality so allocating all the links isn't as much of a penalty. Such allocation is possible in languages such as C++/Rust/C as well. (Though to how much the standard library in each supports you may vary.) My point was that at least I choose linked lists for the O(1) node insertion/removals in addition to maintaining a sequence of items, a trait pretty much unique to linked lists. It's a matter of whether or not the order notation beats out any additional allocation time and cache effects (Vec/std::vector/continuous-memory lists being more friendly towards cache) > Also if you don't have a garbage collector you have to do reference counting, and if you want parallelism your reference counting has to be atomic, which when you're sharing a lot of linked list nodes, is another large penalty. Neither Rust nor C++'s linked list implementations require ref counting, and neither have a GC. A node is essentially, struct LLNode<T> { LLNode *next; LLNode *prev; // if doubly linked T item; } (the above is pseudo-syntax, adjust appropriately) Rust, for example, knows the linked list is only ever owned by a single person. (Barring either the list or the items being wrapped in Rc/Arc/Mutex/etc., but in that case, of course it is, but that's yet different and doesn't really impinge upon a linked list's general usefulness)

watwut 9y ago

For me it is opposite. If the company gives reasonably sized study guide, I am cool with it. I also implemented linked list like structures (it was not linked list but similar). You don't need to memorize it to suceed, the construction is pretty logical.