
An active Player in the game of technology


Brian Baliach


Imagine this: You're typing a friendly message in a WhatsApp group directed to one of your peers, and your fingers,
seemingly possessed by a digital imp, instead of typing 'far too nice', types 'fart oo nice'. Now everyone thinks you're
a creep. Frustrating, right? Fear not! Trie is the unseen sidekick behind your keyboard here to maintain your public
image.

### How 'Trie' Solves the Typo Trouble

Think of Trie as your personal autocorrect wizard. When you type a word, Trie steps in to predict what you're trying to
say. It's like having a smart assistant that finishes your sentences, but for typing!

Imagine you're typing "eleph." Trie jumps in and goes, "Ah, you must mean 'elephant'!" It's like magic—no more wrestling
with the keyboard to spell out every word perfectly.

### So, How Does It Work?

I'll do something different here. Instead of starting off with a written explanation, I'll do a visual walkthrough on
how the Trie works (yes, I also happen to be an artist). If the visual explanation doesn't work for you, feel free to
read on!

![trie diagram](/images/posts/trie_explanation.drawio.png "Trie Diagram")

Picture Trie as a giant family tree of words. Each letter in a word is like a family member. The journey from the root (
the grandparent) to the leaves (the kids) spells out a complete word.

Let's say you've typed "eleph." Trie checks its family tree and quickly realizes that "eleph" fits perfectly into the "
elephant" branch. Voila! It suggests the complete word without missing a beat.

### A Friendly Go-Away Message

This silent sidekick is also evident in other aspects of your life other than Autocorrect. An example most of us might
relate to: Browser History. So for those clandestine folks who toggle 'Incognito Mode' at those wee hours to remove
traces
of their online presence, think of the 'Trie' and it's selfless contributions next time you do this.

Feel free to share your feedback especially if something wasn't clearly explained!

If you are intrigued by the inner workings of Trie, and ready for a deep dive into the digital ocean (don't sue me,
digitalocean), keep reading. The next section is where we unveil the code sorcery behind Trie for our tech-savvy
friends. Also, if you have already read the previous blog titled: 'Unveiling the Trie: A Masterstroke for Efficient
String Searches', you can stop here (but you don't have to :-)).

Gentlemen, and women, and everyone else, shall we?

A brief introduction to Trie: it's a data structure (similar to an array, a list, a tuple etc.) that stores data as
a tree where the branch of the tree traces out the path to where the data is, i.e. the leaf nodes/child nodes.

Here's the link to
the [GitHub repository with the full implementation.](https://github.com/TylerMutai/coding-challenges-solutions/tree/main/js-coding-challenges-solutions/trie_dictionary)

Now, let's get hands-on with some JavaScript code!

Here's our Trie implementation:

```javascript
// Trie Node
function TrieEntry(word) {
  this.word = word;
  const words = [];
  for (let i = 0; i < 26; i++) {
    words.push(null);
  }
  this.words = words;
}

// Main Trie Dictionary
function TrieDictionary() {
  const letterToIndexMapping = {
    "a": 1,
    "b": 2,
    "c": 3,
    "d": 4,
    "e": 5,
    "f": 6,
    "g": 7,
    "h": 8,
    "i": 9,
    "j": 10,
    "k": 11,
    "l": 12,
    "m": 13,
    "n": 14,
    "o": 15,
    "p": 16,
    "q": 17,
    "r": 18,
    "s": 19,
    "t": 20,
    "u": 21,
    "v": 22,
    "w": 23,
    "x": 24,
    "y": 25,
    "z": 26,
  }

  this.root = new TrieEntry();

  this.insertWord = (word) => {
    const wordChars = word.toLowerCase().split("");
    let currWord = "";

    let currSlot = this.root;
    for (const char of wordChars) {
      currWord += char;
      // traverse our root adding each char.
      const idx = letterToIndexMapping[char] - 1;
      const arraySlotForChar = currSlot.words[idx];
      if (arraySlotForChar) {
        currSlot = arraySlotForChar;
      } else {
        currSlot.words[idx] = new TrieEntry(currWord);
        currSlot = currSlot.words[idx];
      }
    }
  }

  this.searchWord = (word) => {
    const wordChars = word.toLowerCase().split("");

    let currSlot = this.root;
    for (const char of wordChars) {
      const idx = letterToIndexMapping[char] - 1;
      const arraySlotForChar = currSlot.words[idx];
      if (!arraySlotForChar) {
        break;
      }
      currSlot = arraySlotForChar;
    }
    return currSlot.word === word;
  }

  this.printDictionary = () => {
    const printRecursively = (entry) => {
      if (!entry) return "";

      for (const en of entry.words) {
        if (en) {
          console.log("en: ", en);
          console.log("--------------------");
        }
        printRecursively(en);
      }
    }

    printRecursively(this.root);
  }
}
```

### Why Trie? A Performance Benchmark Comparison Between Trie and Linear Search

Feel free to run the code directly on your machine if you'd prefer a more hands-on approach.

#### 1. Dictionary Population (1049938 words)

Adding words to our Trie is a breeze. Here's the javascript code sample:

```javascript
const trieDict = new TrieDictionary();
const wordsDictionary = ["apple", "banana", "orange", /* ...a million more words */];

const start = new Date();
for (const word of wordsDictionary) {
  trieDict.insertWord(word);
}
const end = new Date();

const elapsedTime = (end - start) / 1000;
console.log(`Trie Population Time: ${elapsedTime} seconds`);
```

```bash
Dictionary population (1049938 words) timestamp start:  1699963909921
Timestamp after population:  1699963911482
Trie Population Time:  1.561
------------------------------------------------------------
```

In a mere 1.561 seconds, our Trie is ready to rock and roll with over a million words. Impressive, isn't it?

#### 2. The Great Search Showdown

Now, let's pit Trie against the traditional linear search in a battle for supremacy. Our contenders: Trie vs. Linear
Search!

```javascript
const wordsToSearch = ["apple", "programming", "debugging", /* ...4,829 more words */];

// Linear Search
const linearSearchStart = new Date();
for (const word of wordsToSearch) {
  // ... linear search logic
}
const linearSearchEnd = new Date();

// Trie Search
const trieSearchStart = new Date();
for (const word of wordsToSearch) {
  trieDict.searchWord(word);
}
const trieSearchEnd = new Date();

// Calculating and Displaying Results
const linearSearchTime = (linearSearchEnd - linearSearchStart) / 1000;
const trieSearchTime = (trieSearchEnd - trieSearchStart) / 1000;

console.log(`Linear Search Time: ${linearSearchTime} seconds`);
console.log(`Trie Search Time: ${trieSearchTime} seconds`);
```

Drumroll, please! The results are staggering:

- **Linear Search Time:** 8.839 seconds
- **Trie Search Time:** 0.004 seconds

Yes, you read it right! Trie search takes a mere fraction of a second, showcasing a jaw-dropping 2200X performance
boost!

### Use-Cases: 'Trie's' Playgrounds

#### 1. Autocomplete During Search

Ever wondered how autocomplete in search bars works seamlessly? Trie is the wizard behind the curtain, swiftly
predicting your next word as best as it can.

#### 2. Spell Checking

Tries are responsible for checking typos and spelling mishaps. It detects errors with the swiftness of a
well-optimized algorithm, making corrections before you finish typing "debug."

### Wrapping it Up: Trie and the Future of Performance

In the blink of an eye, Trie has transformed the landscape of our search experiences. With its unparalleled speed in
word insertion and instant searches, this data structure emerges as a strategic asset for software optimization.

As you navigate through the complexities of code, consider the Trie as a reliable companion, streamlining your path
through the intricate web of linguistic data.

Before we part ways, contemplate this: How might integrating Trie elevate the efficiency of your software projects?
Share your insights in the comments below! Stay tuned for our upcoming tech discussions, where we'll unravel more coding
intricacies.

Wishing you seamless coding journeys!


Autocomplete Demystified: A Common Use-Case of Trie


Welcome back, fellow developers! In our last rendezvous, we deciphered the intricacies of recursion, peeking into the call stack and heap dynamics. Today, we embark on a journey to unravel the mysteries of the Trie data structure, a silent hero in the realm of efficient string searches. So buckle up your code belts and let's dive in!

### The ABCs of Trie: What is it?

Imagine a dictionary, organized not alphabetically, but in a way that groups words by common prefixes. That's essentially what a Trie (pronounced "try") is—a tree-like data structure where each node represents a single character. It's a linguistic maze where the journey from the root to a leaf node spells out a complete word.

Here's the link to the [GitHub repository with the full implementation.](https://github.com/TylerMutai/coding-challenges-solutions/tree/main/js-coding-challenges-solutions/trie_dictionary)

Now, let's get hands-on with some JavaScript code!

Here's our Trie implementation:

```javascript
// Trie Node
function TrieEntry(word) {
  this.word = word;
  const words = [];
  for (let i = 0; i < 26; i++) {
    words.push(null);
  }
  this.words = words;
}

// Main Trie Dictionary
function TrieDictionary() {
  const letterToIndexMapping = {
    "a": 1,
    "b": 2,
    "c": 3,
    "d": 4,
    "e": 5,
    "f": 6,
    "g": 7,
    "h": 8,
    "i": 9,
    "j": 10,
    "k": 11,
    "l": 12,
    "m": 13,
    "n": 14,
    "o": 15,
    "p": 16,
    "q": 17,
    "r": 18,
    "s": 19,
    "t": 20,
    "u": 21,
    "v": 22,
    "w": 23,
    "x": 24,
    "y": 25,
    "z": 26,
  }

  this.root = new TrieEntry();

  this.insertWord = (word) => {
    const wordChars = word.toLowerCase().split("");
    let currWord = "";

    let currSlot = this.root;
    for (const char of wordChars) {
      currWord += char;
      // traverse our root adding each char.
      const idx = letterToIndexMapping[char] - 1;
      const arraySlotForChar = currSlot.words[idx];
      if (arraySlotForChar) {
        currSlot = arraySlotForChar;
      } else {
        currSlot.words[idx] = new TrieEntry(currWord);
        currSlot = currSlot.words[idx];
      }
    }
  }

  this.searchWord = (word) => {
    const wordChars = word.toLowerCase().split("");

    let currSlot = this.root;
    for (const char of wordChars) {
      const idx = letterToIndexMapping[char] - 1;
      const arraySlotForChar = currSlot.words[idx];
      if (!arraySlotForChar) {
        break;
      }
      currSlot = arraySlotForChar;
    }
    return currSlot.word === word;
  }

  this.printDictionary = () => {
    const printRecursively = (entry) => {
      if (!entry) return "";

      for (const en of entry.words) {
        if (en) {
          console.log("en: ", en);
          console.log("--------------------");
        }
        printRecursively(en);
      }
    }

    printRecursively(this.root);
  }
}
```

### Why Trie? A Performance Benchmark Comparison Between Trie and Linear Search

Feel free to run the code directly on your machine if you'd prefer a more hands-on approach.

#### 1. Dictionary Population (1049938 words)

Adding words to our Trie is a breeze. Here's the javascript code sample:

```javascript
const trieDict = new TrieDictionary();
const wordsDictionary = ["apple", "banana", "orange", /* ...a million more words */ ];

const start = new Date();
for (const word of wordsDictionary) {
  trieDict.insertWord(word);
}
const end = new Date();

const elapsedTime = (end - start) / 1000;
console.log(`Trie Population Time: ${elapsedTime} seconds`);
```

```bash
Dictionary population (1049938 words) timestamp start:  1699963909921
Timestamp after population:  1699963911482
Trie Population Time:  1.561
------------------------------------------------------------
```

In a mere 1.561 seconds, our Trie is ready to rock and roll with over a million words. Impressive, isn't it?

#### 2. The Great Search Showdown

Now, let's pit Trie against the traditional linear search in a battle for supremacy. Our contenders: Trie vs. Linear Search!

```javascript
const wordsToSearch = ["apple", "programming", "debugging", /* ...4,829 more words */ ];

// Linear Search
const linearSearchStart = new Date();
for (const word of wordsToSearch) {
  // ... linear search logic
}
const linearSearchEnd = new Date();

// Trie Search
const trieSearchStart = new Date();
for (const word of wordsToSearch) {
  trieDict.searchWord(word);
}
const trieSearchEnd = new Date();

// Calculating and Displaying Results
const linearSearchTime = (linearSearchEnd - linearSearchStart) / 1000;
const trieSearchTime = (trieSearchEnd - trieSearchStart) / 1000;

console.log(`Linear Search Time: ${linearSearchTime} seconds`);
console.log(`Trie Search Time: ${trieSearchTime} seconds`);
```

Drumroll, please! The results are staggering:

- **Linear Search Time:** 8.839 seconds
- **Trie Search Time:** 0.004 seconds

Yes, you read it right! Trie search takes a mere fraction of a second, showcasing a jaw-dropping 2200X performance boost!

### Use-Cases: Trie's Playgrounds

#### 1. Autocomplete Awesomeness

Ever wondered how autocomplete in search bars works seamlessly? Trie is the wizard behind the curtain, swiftly predicting your next word with unparalleled speed.

#### 2. Spell Checking Sorcery

Trie is your vigilant guardian against typos and spelling mishaps. It detects errors with the swiftness of a well-optimized algorithm, making corrections before you finish typing "debug."

### Wrapping it Up: Trie and the Future of Performance

In the blink of an eye, Trie has transformed the landscape of our search experiences. With its unparalleled speed in word insertion and instant searches, this data structure emerges as a strategic asset for software optimization.

As you navigate through the complexities of code, consider the Trie as a reliable companion, streamlining your path through the intricate web of linguistic data.

Before we part ways, contemplate this: How might integrating Trie elevate the efficiency of your software projects? Share your insights in the comments below! Stay tuned for our upcoming tech discussions, where we'll unravel more coding intricacies.

Wishing you seamless coding journeys!


Unveiling the Trie: A Masterstroke for Efficient String Searches

If you’ve been following me, you might recall a harrowing tale of a developer coming to grips with recursion. The aptly titled 'Decoding Recursion: The Concept That Had Me Stumped'. But your cogitation and feedback suggest we dig a tad deeper. Brave ones have emerged requesting a practical walkthrough of recursion. In this sequel, we'll take a hands-on approach to recursion using the call stack/heap.

Let's hoist the mainsail and dive in.

### Under the Hood: What Happens When Functions Run?

So, matcha latte in hand, (or is it an afternoon beer?), let’s unravel what’s going on 'under the hood' when functions are involved. Every function in its operation has an allocated memory space. Avoiding the technical jargon for the sake of our shared sanity, let's visualize this as tiny compartments in your computer's brain.

When a function runs, it's like the computer opens that compartment and dumps everything the function needs inside – the variables, calculations, and that little reminder of your lunch break at 12 pm.

This "compartment" goes by a couple of names in the programming world: Stack and Heap. While they are both for storage, they differ slightly in usage. The stack is used for static memory allocation and the heap for dynamic memory allocation.

### Enter Recursion: A Practical Look

Since we're all here for recursion, let's take a prime example - factorial computation. A factorial is the product of a number (n) and all the integers below it. Remember 5! (factorial) equaling 5x4x3x2x1? Yes, that one.

In code form, a basic recursive function for a factorial would look something like (javascript this time, cause turns out, it has a much larger audience):

```javascript
function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
```

Now, let's visualize this on the call stack.

Every recursive call will add a layer to the stack. It's like a pile of dishes. The first call (n=5) is the first plate. Then n=4, then 3, 2, and finally 1. After that, the result bubbles up, washing the dirty dishes one by one from the top until you reach the clean plate at the bottom, i.e., the final answer.
Remember that in heaps/stacks, data is added in a first come last serve basis.
Here's a visualization:

| Heap         | Result | Code explanation                                                                        |
|--------------|--------|-----------------------------------------------------------------------------------------|
| n==1         | 1      | base case: (n==1) return 1;                                                             |
| n==2         | 1 * 2  | n is 1 (n * factorial(n-1) which comes from previous call above. result then becomes 2. |
| n==3         | 2 * 3  | n is 2, which again comes from previous call above. the result becomes 6.               |
| n==4         | 6 * 4  | n is 6, which again comes from the call above. the result becomes 24.                   |
| n==5         | 24 * 5 | n is 24, the result becomes 120.                                                        |
| final result | 120    | This is what is finally returned. 120.                                                  |


### Stack Overflow: Recursion's Gotcha!

Stack overflow – it isn't just a popular website, folks; it's recursion's Achilles heel. This happens when our recursion burrows too deep, causing the application to run out of memory space. This is because every OS assigns a running program a fixed memory allocation (i.e. 4MB worth of space). If you exhaust this space, you then might get a stack overflow /segmentation fault error. There goes the stack of dirty dishes tumbling down!

This potential drawback highlights how deep understanding of recursion can help developers optimize for performance.

### Wrapping It Up

There you have it - a code soup stirred with the call stack/heap and topped off with a sprinkle of recursion. Hopefully, this has helped demystify the concept a bit. But who knows? Perhaps our odyssey is just starting - linked lists, binary trees, sorting algorithms - all served with that recursion spice, are waiting!

Remember, fellow devs, recursion is a powerful tool and understanding how it works at every level aids in writing better, cleaner, more intuitive and more efficient code... even if it stumps us occasionally!

As always, sail through your coding voyage, one recursion at a time.



Unraveling Recursion: A Practical Look at the Call Stack and Heap

Microservices might be the heroes of scalable and reliable applications today, but let's shift gears and talk about a concept in the software development landscape that is as mind-bending as it is powerful: recursion.

As someone who enjoys the adrenaline rush of conquering coding challenges, I've come across various concepts that are the bread and butter of computer science. Some felt like meeting an old friend on the first day of school—familiar and comforting. Others were like that one high school math problem that kept me up at night. Enter recursion.

Recursion, to put it simply, is like a mythic serpent that swallows its own tail—a function that munches on itself to get to a result. My initial thought was, "Why suffer through this mind-boggling feat when a good ol’ loop could suffice?" But then, as I chewed over recursion, the mist started to fade.

### Imagine This...
Let's play with recursion's call stack visualization. Suppose a group of kids are playing with a neat stack of blocks. Each block has a unique number. The rule is: a player can only place a block on the stack if it decreases the previous number by one. The game starts with 10 and ends with 1—a stack of decrescendoing integers.

So, what does this have to do with recursion? Each block placement is akin to a function call in recursion. You place one block (function call), then another (another call), and another, till you reach the edge case — in our scenario, the number 1 block. That's when the players start to cheer and pass the stacks backwards, unwinding them while they execute some extra celebration (in our case, processing returns).

### Dividing to Conquer
Remember those divide-and-conquer strategies in ancient warfare history? They work magic in recursion too. A problem must be conquerable by breaking it down into smaller, more manageable versions of itself.  Simply take down towers one by one until the main castle surrenders.

### A Quick Dive Into Code
Let's demonstrate recursion with a problem that even I, a seasoned loop-lover, found elegant in its recursive cloak — a classic problem: calculating the factorial of a number.

The factorial of a number n (denoted as n!) is the product of all positive integers up to n. For instance, the factorial of 4 is 4! which equals 4 * 3 * 2 * 1 = 24.

A looping method would have us running circles. Here's a python example (python because, from my perspective, is closest to English):

```python
def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result
```

But let's sprinkle the magic dust of recursion:

```python
def factorial_recursive(n):
    if n == 1:
        return 1
    else:
        return n * factorial_recursive(n - 1)
```

This second snippet embraces the soul of recursion. We define an edge case — our base condition that stops the infinite tumble down the rabbit hole (n == 1). The function then keeps calling itself, shrinking the problem down each time (n - 1), till it hits that edge case. And then the unwinding begins, with each call resolving and returning its piece of the puzzle, eventually giving us our answer.

### Why Bother With Recursion?
Sure, recursion might seem like overkill for simple problems that a loop can fix. But consider the elegance of solutions it provides for more complex issues like tree traversals, algorithmic problem solving such as the Towers of Hanoi, or graph searches. Sometimes, recursion is not just a solution; it's the most intuitive one.

### Closing Thoughts
Once I got past the intimidating facade of recursion, I found a beautiful and streamlined way of solving certain kinds of problems. Just like my transition from being a REST advocate to appreciating the swiftness of gRPC, embracing recursion has opened up new pathways in my coding journey.

If you're still feeling the heebie-jeebies about recursion, you're not alone. Take it from someone who was once stumped by the concept: the enigma of recursion is worthy of exploration. With each recursive function we write, we're training our minds to see not just the stack of problems but the stack of solutions waiting beneath. Happy recursing!


Decoding Recursion: The Concept That Had Me Stumped

Showing posts from coding-challenges tag

Autocomplete Demystified: A Common Use-Case of Trie

Unveiling the Trie: A Masterstroke for Efficient String Searches

Unraveling Recursion: A Practical Look at the Call Stack and Heap

Decoding Recursion: The Concept That Had Me Stumped