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.
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 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.
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.
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.
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.
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.
18 comments
[ 3.0 ms ] story [ 48.1 ms ] threadWe 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.
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.
Cheers!
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
The title is extremely ill-chosen for an otherwise acceptable blog post. The post itself really has nothing to do with tech interviews.
The footnote #2 for bloom filter is especially good. "The real interview pro tip is always in the footnotes."