devblogvn

 When dealing with strings—like searching for words in a dictionary, building autocomplete systems, or implementing spell checkers—efficiency matters. One powerful tool for such tasks is the Trie (pronounced “try” ), also known as a prefix tree . In this post, we’ll explore what a Trie is, why it’s useful, how it works, and where you can apply it. What is a Trie? A Trie is a tree-like data structure designed for storing and retrieving strings efficiently. Unlike a binary search tree (BST), where nodes represent keys, each node in a Trie represents a single character of a string . For example, consider inserting the words: cat , car , apple and ant . The Trie would look like this: Notice how the common prefix "ca" is stored only once, making the Trie memory-efficient when handling large sets of overlapping words. Key Properties of a Trie Nodes represent characters : Each edge corresponds to a letter in a string. Root node is empty : It represents the starting poin...

 A Bloom filter is a probabilistic data structure used to test whether an element is possibly in a set or definitely not in a set . It’s designed to be memory-efficient and very fast, but it allows false positives (saying an element might be in the set when it’s not) while guaranteeing no false negatives (if it says something is not in the set, it really isn’t). How it works: You start with a bit array (all bits set to 0). You have k different hash functions . To add an item: Compute its k hashes. Set the corresponding k positions in the bit array to 1. To check if an item is in the set: Compute its k hashes. If all those positions are 1 → item might be in the set (possible false positive). If any position is 0 → item is definitely not in the set . Example: Suppose you insert "cat" . Hash functions map "cat" to positions [3, 7, 12], so you set those bits. Later, you check "dog" . Its hashes are [3, 12...