Geek asks and answers

Best way to implement partial key hashing

I appeared for an interview, where I was asked to write an algorithm for partial hashing of keys; if ABCBC is inserted into the hash, then searching for any of the substrings should return the stored value. My answer was to create a collection of all possible substrings of a given key and maintain a match between each substring with one or more parent strings. Then support the BST from the collection of all substrings. Each node will point to a set of actual values ​​that may correspond to this substring. E.g. A, AB, ABC, ABCB, ABCBC, B, BC, BCB, BCBC, C, CB, CBC are possible substrings for this string. There may be other strings like BAB, of which AB and B are substrings. So, given AB, it will be displayed on two lines BAB and ABCBC.

Is there an even more efficient way? Thanks

+5
source share
1 answer

Store each substring in a hash with a note about whether it is final, and the possible next characters and previous characters. Keep the previous characters for all words that may have this substring in the middle, and the following characters for all words that have this substring as the beginning.

Therefore, the entry for adoes not have to contain all the words with a. But it's easy enough to create this list if you want. Also during insertion, as soon as you decrease in size on the substrings, you will find that you already have the current substring with the current continuation, you can stop.

, , . - O(n*n) n.

, , .

+3

More articles:


All Articles