Introduction
This post is a continuation of the back tracking series. You can refer to other similar posts here. In this post we will be discussing the Knight's Tour Problem. The problem states that, given a N * M chessboard, a Knight's Tour is defined as the sequence of moves of a Knight, such that the Knight visits every square only once.
Does this sound similar?
Yes it is similar to finding the Hamiltonian Path as defined in this post.
Approach for solving the Knight's Tour problem
Here I define the backtracking approach to solve this problem. Let the Knight start from any location...

Read More
## Pair of Numbers to obtain given sum

Introduction
This problem is already defined in one of the previous post. You can read that to know the problem in more detail. The definition goes like this, find a pair of numbers to obtain given sum in an array. The task is to find two numbers in an array which when added will produce a desired sum.
Approach to find a Pair of Numbers to obtain given sum
As the theory is already mentioned in the previous post, let us directly jump to all possible solutions. Here I am defining three different solutions to this problem. And the idea is to build a basic understanding and then proposing the b...

Read More
## 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...

Read More
## 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...

Read More
## 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 ...

Read More