Data structures to name-drop when you want to sound smart in an interview | Hacker News Reader

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

blog.amynguyen.net

53 pointsloige18 comments

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

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.

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.

That's a serialization/deserialization problem, which is mostly orthogonal to the implementation of the data structure itself.

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.

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.

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."

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.

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

Would this actually be effective or could i tback fire?

I had one interview derailed when I did this (earnestly answering, not name-dropping).

So what happened?

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.

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.

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.

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.

This is called mutual recursion. Interpretors rely on it heavily.

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!

Reply on news.ycombinator.com