Data Structures: Tries

Learn the basics of tries. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

[xnadave]

Another key phrase to keep in mind (asked during an interview a few years back): "Imagine that you're implementing autocomplete for a video search engine..."

[moisesacero]

'Hi, I'm Gayle Laakmann McDowell, author of Cracking the Coding Interview' was spoken as if she weren't a demi-god of the highest caliber.

[apiphobian]

5 mins to explain Trie is all you need if prepared! Perfect!

[muzammilnxs]

Quick notes,
Motivation: String manipulation problems involves searching through a list of words/sentences. As a standard solution, we would store words in string or character array and iterate through characters to perform operations. This typically is limited by number of words in the list to search for and the number of characters that we have in the input string. If length of input string is l and number of words to search through is n, the time complexity would be O(l*n). For example, if there are 5 million words and length of input string is say 10, there would be 50 million operations which is extremely expensive computationally. Our goal is to reduce the time complexity to O(l) which is a factor of length of input string(l) only. So, for the above example, we would only have to do 10 operations to complete our search.

• Generally, We would use a tree like data structure when we can arrange data in a hierarchical way using a property of the data. For example, BST exploits the nature of sorted numbers ie the parent number is greater/smaller than the children. For words in the dictionary, we can exploit the feature that most words have common root. e.g house, housemaid
• The above nature of a tree data structure helps in massively reducing our search space for problems.
• A binary tree implemented correctly reduces the time complexity from O(n) to O(log n). Internally, because of the way it is organized, every traversal reduces the search space by half. And that's how there is huge save in time
• In binary tree, every node can lead to potentially two ways. In a Trie, every node can lead to potentially 26 ways(for character space lowercase alphabets a-z). Thus reducing our search space by a factor of 26
Potential character space allowed for a trie node is decided by the problem statement. Till now, we assumed the simple case of lower case alphabets(a-z). If we allow upper case alphabets(A-Z), then our search space increases to 52. And similarly we can decide to allow special characters, numbers and so on and so forth

[EchoVidsu]

I never learned about tries in data structures. This is the first time I have heard of them and I already graduated.

[davidlr]

"why don't you trie applying this to your own problems"

ha...

[Hitz]

She is so down to earth…. Author of cracking the coding interview 🙏🙏

[PaulXiaofangLan]

For UI engineer, this is the one we could use for autocomplete in combox or predict typo.

[lac]

Fantastic condensed, down to the point explanation. Anybody with some CS background can easily fill in the holes of any left out details.

[AninditKarmakar]

A well articulated description in under five minutes to get me going with Trie data structures! Impressive!!

[Bloodthirst]

i used this in my game engine where i divided the world into a bunch of cubes in 3D space, and instead of searching a word using characters (like the example of the video), i pass the (x, y, z) of the cube and i get quick access to the object in that world chunck

[divyanksharma]

I have implemented this in my rest framwork url mapping.. its cool!!

[devendratapdia]

I love this blackboard, virtual board. Its real fun. If I would have had that same board while I was studying, what a fun it would have been

[Icix]

"This isn't something CS students might have spent that much time in school, but it's really really important for interview"

Translation: You'll never use this in the real world but employers love to make impractical problems part of their interview process. Can't have enough hoops to jump through, especially if it has nothing to do with the role you're hiring for!

[Aerwith]

What is this beautiful blackboard program?

[jasonzhang]

What's the software that can make the virtual blackboard?

[Btotts]

Really wish I would've seen this before my interview...

[cokeeeeman]

"The term trie was coined two years later by Edward Fredkin, who pronounces it /ˈtriː/ (as "tree"), after the middle syllable of retrieval" -- Wikipedia

[sebbes]

THANKS! I have never heard about tries before.

[MS-ibxu]

Great video! Very clear presentation and great examples.