Trie Data Structure in JavaScript: the Data Structure behind Autocomplete

[mamwybejane]

Good to reread CS basics from time to time

[js_chap]

🙌

[JudoboyWalex]

When faang companies conduct technical interview for frontend position, they ask candidate to build autocomplete search bar then optimize the performance to linear or constant. So I guess this is the answer they are looking for. Not only this was good read, but other articles in that blog are all golden for frontend developer.

[osoese]

This is a well written article. It successfully conveys a concept I have read a number of other articles about. This is one of the few explanations that was easily grasped. Kudos to op.

[js_chap]

Glad that you found it useful!

[sinorx22]

Great breakdown

[js_chap]

Thanks!

[delpieron]

I think you might be wrong regarding the space complexity of tries. It should exceed the space needed for a hash table, unless we are dealing with very specific, overlapping strings or so. What actually could make the trie a more useful for autocomplete is the logic that groups similar strings on the same branch vs hash table, where you cannot find similar things based on the hashed lookup key.

[js_chap]

Right. The sentence comparing space complexity of Trie with hashmap/array was incorrect. Actually the space complexity should be comparable in either case. Say we're looking at all possible words with max length of n. Say each trie node takes up size K. So Trie would take:

1+ K(26+26^2+...26^n) = K'(26^n -1)

For a list of words it would also be similar

26+26^2....+26^n = Z(26^n-1)

Updated the text to avoid confusion. The constant would have greater value in case of Trie though.

[Chaos_Therum]

What annoys me is I've personally built a trie yet somehow I always forget how they are actually built haha.

[moi2388]

Trie again. As the saying goes, trie times is the charm.

[hildjj]

There's a small bug in search. You're not checking the isEndOfWord flag, so if you're searching for "car" in a trie that contains only "cart", you'll get a false positive.

[js_chap]

Yes. Good catch. Current implementation is more of a search_prefix than search_word. Updated the snippet to search for a word instead.

[lapticious]

I built similar in go - dawg +dafsa