# Algorithms

This category contains all the posts related to Algorithms. For e.g.: Sorting, Hashing, Searching, Tree Traversals, Graph Theory etc.

## Solution to find Interleaving of Strings

Introduction This post is an enhancement over one of the previous posts where the task was to find if a given string C is an interleaving of strings A and B. To know more about the problem description, please visit the previous post Solution The previous solution is a iterative solution which requires lot of space. Here we will discuss a recursive solution. Hopefully with small code foot print. Before we jump into the code, let us understand the idea behind the solution. Here are the example Strings A, B and C A -> abcd B -> ade C -> abadcde The recursive algorithm...

## Count Word Frequency in Stream

Introduction Continuing our discussions on Tries, here is another practical problem which is used in many text processing scenarios. Counting word frequency in stream translates to a scenario where you are given a list of words (dictionary). Now, there is an infinite stream of characters coming in. Your task is to print the frequency of words appearing in the stream. To know more about the basics of building a Trie, please visit my previous post Example Problem for counting word frequency in stream Let us say we have a dictionary which contains the following words aca cat hell...

## Maximum path sum in a triangle

Problem Statement Finding the maximum path sum in a triangle is a very common programming problem. You are given a triangle of numbers which can be represented as below. You are allowed to start from the top of the triangle and move to either of the two number below it. As we move down from the top to the bottom in multiple ways, we keep adding the numbers for each node we visit. The goal is to maximize the sum . A more formal problem statement can be found on the Project Euler website. How to approach the problem At any point you have two choices you can go to the number below the current ...

## Solving the N Queen Problem

Introduction The N Queen Problem is one of the best problem used to teach backtracking and of course recursion. Backtracking is a general algorithm which finds all complete solutions to a problem by building over partial solutions. In this process, the problem might reach to a partial solution which may not result into a complete solution. Such partial solutions are effectively rejected by the backtracking algorithm. To know more about backtracking please visit the Wikipedia article. The classic case of N Queen problem In this problem, you are given an empty chess board of dimensions N *...

## Building an autocomplete system using Trie

Introduction Few days back I wrote a post about the Trie data structure. This post is a continuation to it, and intends to introduce some practical problems which Trie solves. An autocomplete system is a perfect use case. Many of the websites use this feature to help there users with suggestions & autocomplete. Also, in this post we will define a Trie interface and then work through this problem statement. An autocomplete system using Trie As we know from the previous text that a Trie is a tree like data structure which stores words such that the search for a word is proportional to ...