4 ms·

I've had dozens of interviews for mid-level and senior-level engineer positions in the past 10 months at many diverse companies and gotten offers from most of t

I've had dozens of interviews for mid-level and senior-level engineer positions in the past 10 months at many diverse companies and gotten offers from most of them (retracted for unrelated reasons), and none of them asked about data structures even close to this. So it seems like it's probably really obscure. Or maybe only interviews for certain positions look for this kind of knowledge?

AstralStorm 8y ago
Almost nobody writes heaps anymore, they're not even the best structure for priority queues now, that typically taken by skiplists or more advanced balanced trees like red-black tree. It is one of those stupid questions. The good question would be to task them to implement a priority queue (also a bit rough as they are in standard library now or boost, but for old C++ you may get to write one) and see what they come up with. Discuss a bit too.
- jstimpfle 8y ago
  I'm curious, what's wrong with array based heaps? I've implemented both Red-black trees and array based heaps in the past. If I had to take a guess I would say the latter should be noticeably faster. In any case Red-black trees are much harder to implement.
  - AstralStorm 8y ago
    The problem with heaps is cache locality if you have anything different from tiny types like pointers stored inside. Plus that they do have to be resized more often than the other structures and you're forced to allocate a continuous chunk of memory if they're big. (And for small, you actually cannot beat a simple list with a one item sort by a heap.) Both skiplists and rbtrees allow for a tricky but efficient colored pointer implementation and also if you need fine grained locking or lock free implementations.
    - kadoban 8y ago
      Red-black trees aren't known for having good spatial locality of reference (heaps aren't either, but I fail to see how this is a point in favor of RB trees). Is there a particular implementation that doesn't share this shortcoming that you had in mind? That would be interesting to me. If allocating a heap as a big chunk were a problem, you could certainly do it as nodes and pointers like a RB tree is traditionally done (reify the tree instead of array-encode it). Though the array-encoding is itself usually an optimization, so I wouldn't think you'd want to do that. Doing one big allocation (and copy) every once in a while (in a table-doubling-esque manner) should be a win over individually allocating nodes, if you can amortize over many operations. And again if that's not true or undesireable, you can just allocate a heap like you'd allocate a tree normally.
      - jstimpfle 8y ago
        I was wondering the same, and was thinking that maybe the RB needs to touch fewer nodes to rebalance after a remove operaiton, thus resulting in better cache friendliness (although GP said cache _locality_)? But it seems unlikely since the heap property is much weaker than the RB-balanced binary tree property.
        AstralStorm 8y ago
        RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around as in some balancing trees and are small. Thus you end up with cache locality even when not directly aiming at it. B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.
        jstimpfle 8y ago
        > RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.
- deleted 8y ago
  [deleted]
pjmlp 8y ago
Cool startups that want to be like Google and FB, but are still at around 10 employees.

AstralStorm 8y ago

Almost nobody writes heaps anymore, they're not even the best structure for priority queues now, that typically taken by skiplists or more advanced balanced trees like red-black tree. It is one of those stupid questions. The good question would be to task them to implement a priority queue (also a bit rough as they are in standard library now or boost, but for old C++ you may get to write one) and see what they come up with. Discuss a bit too.

jstimpfle 8y ago
I'm curious, what's wrong with array based heaps? I've implemented both Red-black trees and array based heaps in the past. If I had to take a guess I would say the latter should be noticeably faster. In any case Red-black trees are much harder to implement.
- AstralStorm 8y ago
  The problem with heaps is cache locality if you have anything different from tiny types like pointers stored inside. Plus that they do have to be resized more often than the other structures and you're forced to allocate a continuous chunk of memory if they're big. (And for small, you actually cannot beat a simple list with a one item sort by a heap.) Both skiplists and rbtrees allow for a tricky but efficient colored pointer implementation and also if you need fine grained locking or lock free implementations.
  - kadoban 8y ago
    Red-black trees aren't known for having good spatial locality of reference (heaps aren't either, but I fail to see how this is a point in favor of RB trees). Is there a particular implementation that doesn't share this shortcoming that you had in mind? That would be interesting to me. If allocating a heap as a big chunk were a problem, you could certainly do it as nodes and pointers like a RB tree is traditionally done (reify the tree instead of array-encode it). Though the array-encoding is itself usually an optimization, so I wouldn't think you'd want to do that. Doing one big allocation (and copy) every once in a while (in a table-doubling-esque manner) should be a win over individually allocating nodes, if you can amortize over many operations. And again if that's not true or undesireable, you can just allocate a heap like you'd allocate a tree normally.
    - jstimpfle 8y ago
      I was wondering the same, and was thinking that maybe the RB needs to touch fewer nodes to rebalance after a remove operaiton, thus resulting in better cache friendliness (although GP said cache _locality_)? But it seems unlikely since the heap property is much weaker than the RB-balanced binary tree property.
      - AstralStorm 8y ago
        RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around as in some balancing trees and are small. Thus you end up with cache locality even when not directly aiming at it. B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.
        jstimpfle 8y ago
        > RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.
deleted 8y ago
[deleted]

pjmlp 8y ago

Cool startups that want to be like Google and FB, but are still at around 10 employees.