Problem Statement
We are interested in finding the count of all N digit crazy numbers. Let us define a crazy number. A crazy number is a number where the magnitude of its consecutive digits differ by 1.
For e.g.: Here is a list of all 2 digit crazy numbers:
The total number of 2 digit crazy numbers is 17. You can notice that in all the numbers the digits differ only by 1.
Similarly for three digit numbers the count reaches 32. For four digit numbers it becomes 61 and very soon it increases exponentially to 924903595810 for a 40 digit number.
It might look like the a problem wh...

Read More
## Huffman Decoding

Introduction
Huffman coding is an encoding mechanism by which a variable length code word is assigned to each fixed length input character that is purely based on their frequency of occurrence of the character in the text to be encoded.
It is common to assign shorter codes to more frequent characters and the less frequent characters are assigned longer code words. A code word is a binary string (a sequence of zeroes and ones).
A Huffman tree is made for an input string and characters are decoded based on their position in the tree. The decoding process is as follows:
We start from t...

Read More
## Merge Point of two Linked Lists

Problem Statement
This is another interview question which can be linked to the Cycle Detection in Linked List question. In fact this is an extension of the Cycle Detection problem and requires an extra tweaking.
Here is a diagram explaining the the problem of finding the merge point of two linked lists
In the above diagram, the head of one linked list is node 1 and the head of another linked list is node 5. The merge point is node 4. We would like to write a program to find node 4 given both the heads.
Approach
There are multiple ways of solving it, here I list three of them:
Br...

Read More
## Finding loop in Linked List

Problem Statement
You are given a singly linked list which may or may not contain a loop. The task at hand is to find if the loop exists. Here is a diagrammatic representation of a loop in a singly linked list.
[caption id="attachment_3617" align="aligncenter" width="688"] Finding loop in LinkedList[/caption]
It is pretty clear that there is a loop which starts at the node 3 and there are 10 nodes which make the loop. In this case we need to print a YES. If it had been a singly linked list without the node 12 connecting to node 3, we would have printed a NO.
Approach to Finding loop i...

Read More
## Pattern Search in Grid

Problem Statement
Given a huge grid G with M rows and N columns and a pattern P with m rows and n columns. The task at hand is to perform a pattern search in grid, and print YES if the pattern grid P exists in the grid G otherwise print NO
[caption id="attachment_3611" align="aligncenter" width="960"] Pattern Search in Grid[/caption]
Its a simple string search but requires special attention to the boundary cases. Here is a list of them
We only need to test the grid G for M-m rows, because anything below row R-r cannot accommodate the pattern of size r.
We only need to test the gr...

Read More