4 ms·

Data structures to name-drop when you want to sound smart in an interview

53 points by loige 8y ago

crb002 8y ago
Python and C++ standard libraries should include the prefix trie, suffix array, Bloom filter, T/Q Digest, and Count-min sketch. Also generic dense/sparse matrix-matrix multiply, and lazy/streaming algorithm interfaces to operate on network supplied data.
- sitkack 8y ago
  More importantly, those libraries should use the same on-disk representation so that bloom filters and HLL can be exchanged. Most libraries provide no way for these to be reused, or they require the library be everywhere. Some systems cannot install your (the library author's) libraries.
  - TeMPOraL 8y ago
    That's a serialization/deserialization problem, which is mostly orthogonal to the implementation of the data structure itself.
    - sitkack 8y ago
      The hashing algorithms and their configuration parameters need to be fully specified, or the whole lib needs to be compiled into WASM. We need a portable standard for the external encoding of Bloom and HLL that captures important internal implementation details. I can serialize a map as a list of key values, but I cannot do that with a Bloom filter. The same case could be made for maps, when one has multiple GB hashmaps, rehashing and inserting on load could make it untenable. CaptnProto aadresses some of this, but more work needs to done to treat the heap as a portable database with internal visibility.
moneywoes 8y ago
Would this actually be effective or could i tback fire?
- SamReidHughes 8y ago
  I had one interview derailed when I did this (earnestly answering, not name-dropping).
  - fogetti 8y ago
    So what happened?
    - SamReidHughes 8y ago
      I wound up having to explain finger trees from memory over the phone to somebody who did not want to listen to a high level description of an algebraic data type. Upon being asked for a more low-level description, I gave a word-by-word description of the pointer layout of a tagged union. Then I got asked for the simplest possible data structure, so I answered with an array, and then the guy scoffed like I was an idiot because that was too simple. So then I went with a cut buffer. He tried talking me into using a doubly linked list, and IIRC I wound up going for a doubly linked list of arrays varying in size between 40 and 80 bytes, because I wouldn't want to waste so much memory. Didn't get an on-site.
karmakaze 8y ago
The LMAX Disruptor is a fun one for anyone into Mechanical Sympathy.
kccqzy 8y ago
Who still uses prefix tries? I thought most uses have long been replaced by ternary search trees. No one wants to waste memory storing 26 pointers at each node.
- matthewmacleod 8y ago
  Memory Use and speed will vary heavily depending on the workload; sometimes the ternary search tree isn’t a good solution, especially for small sets - where a radix trie is probably better.
paradoxparalax 8y ago
Once I encountered this curious recursion:' Here sounds infinite loop maybe, but it should finishing calling each other (a calling b that calls a that calls b again...infinite...) But when there is a Top maximum Parent that is the top of the parent child pyramid (like a html Body "div", I mean, the one that contains all others") It should stop...well def a self.insert //something to make it child of the parent, like a html structure maybe b //call the second method, the b method below end def b self.insert //same here, same logic// a //call the first method, the a method above end thisHtmlDiv.a //crazy example So the subject on which you call the method will be added in all the hierarchy chain of the parent child pyramid.
- jeromebaek 8y ago
  This is called mutual recursion. Interpretors rely on it heavily.
  - paradoxparalax 8y ago
    Thank you very much , sincerely, jeromebaek. This is the real nice spirit of Hackernwes, and you are one of the heroes who help pass the good Knowledge. Thank you very much, buddy. Cheers!
TeMPOraL 8y ago
There is what seems to be a repeated typo in footnote 1: "You take the length N. N % M (pronounced N modulo M) gives you a value Q such that 0 ≤ Q < N." I assume the author meant taking M % N here, and later on.
galkk 8y ago
I think that "name-dropping" of something that you don't really know is pretty dangerous strategy in interview. From other point of view, why not to excercise an idea? :) KD-trees and other spatial data structures "True time" when talking about consistency Fenwick tree for right problem
shakkhar 8y ago
I have just one thing to say - never ever "name-drop" a data structure in a coding interview unless you are going to use it in your solution. It doesn't add anything to your interview but has the potential to get you in trouble. The title is extremely ill-chosen for an otherwise acceptable blog post. The post itself really has nothing to do with tech interviews.
- jiveturkey 8y ago
  The title is facetious. It is 100% consistent with her writing style (which I love) and is therefore exactly correct. The footnote #2 for bloom filter is especially good. "The real interview pro tip is always in the footnotes."

53 points by loige 8y ago

Python and C++ standard libraries should include the prefix trie, suffix array, Bloom filter, T/Q Digest, and Count-min sketch. Also generic dense/sparse matrix-matrix multiply, and lazy/streaming algorithm interfaces to operate on network supplied data.

sitkack 8y ago
More importantly, those libraries should use the same on-disk representation so that bloom filters and HLL can be exchanged. Most libraries provide no way for these to be reused, or they require the library be everywhere. Some systems cannot install your (the library author's) libraries.
- TeMPOraL 8y ago
  That's a serialization/deserialization problem, which is mostly orthogonal to the implementation of the data structure itself.
  - sitkack 8y ago
    The hashing algorithms and their configuration parameters need to be fully specified, or the whole lib needs to be compiled into WASM. We need a portable standard for the external encoding of Bloom and HLL that captures important internal implementation details. I can serialize a map as a list of key values, but I cannot do that with a Bloom filter. The same case could be made for maps, when one has multiple GB hashmaps, rehashing and inserting on load could make it untenable. CaptnProto aadresses some of this, but more work needs to done to treat the heap as a portable database with internal visibility.

moneywoes 8y ago

Would this actually be effective or could i tback fire?

SamReidHughes 8y ago
I had one interview derailed when I did this (earnestly answering, not name-dropping).
- fogetti 8y ago
  So what happened?
  - SamReidHughes 8y ago
    I wound up having to explain finger trees from memory over the phone to somebody who did not want to listen to a high level description of an algebraic data type. Upon being asked for a more low-level description, I gave a word-by-word description of the pointer layout of a tagged union. Then I got asked for the simplest possible data structure, so I answered with an array, and then the guy scoffed like I was an idiot because that was too simple. So then I went with a cut buffer. He tried talking me into using a doubly linked list, and IIRC I wound up going for a doubly linked list of arrays varying in size between 40 and 80 bytes, because I wouldn't want to waste so much memory. Didn't get an on-site.

karmakaze 8y ago

The LMAX Disruptor is a fun one for anyone into Mechanical Sympathy.

kccqzy 8y ago

Who still uses prefix tries? I thought most uses have long been replaced by ternary search trees. No one wants to waste memory storing 26 pointers at each node.

matthewmacleod 8y ago
Memory Use and speed will vary heavily depending on the workload; sometimes the ternary search tree isn’t a good solution, especially for small sets - where a radix trie is probably better.

paradoxparalax 8y ago

Once I encountered this curious recursion:' Here sounds infinite loop maybe, but it should finishing calling each other (a calling b that calls a that calls b again...infinite...) But when there is a Top maximum Parent that is the top of the parent child pyramid (like a html Body "div", I mean, the one that contains all others") It should stop...well def a self.insert //something to make it child of the parent, like a html structure maybe b //call the second method, the b method below end def b self.insert //same here, same logic// a //call the first method, the a method above end thisHtmlDiv.a //crazy example So the subject on which you call the method will be added in all the hierarchy chain of the parent child pyramid.

jeromebaek 8y ago
This is called mutual recursion. Interpretors rely on it heavily.
- paradoxparalax 8y ago
  Thank you very much , sincerely, jeromebaek. This is the real nice spirit of Hackernwes, and you are one of the heroes who help pass the good Knowledge. Thank you very much, buddy. Cheers!

TeMPOraL 8y ago

There is what seems to be a repeated typo in footnote 1: "You take the length N. N % M (pronounced N modulo M) gives you a value Q such that 0 ≤ Q < N." I assume the author meant taking M % N here, and later on.

galkk 8y ago

I think that "name-dropping" of something that you don't really know is pretty dangerous strategy in interview. From other point of view, why not to excercise an idea? :) KD-trees and other spatial data structures "True time" when talking about consistency Fenwick tree for right problem

shakkhar 8y ago

I have just one thing to say - never ever "name-drop" a data structure in a coding interview unless you are going to use it in your solution. It doesn't add anything to your interview but has the potential to get you in trouble. The title is extremely ill-chosen for an otherwise acceptable blog post. The post itself really has nothing to do with tech interviews.

jiveturkey 8y ago
The title is facetious. It is 100% consistent with her writing style (which I love) and is therefore exactly correct. The footnote #2 for bloom filter is especially good. "The real interview pro tip is always in the footnotes."