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
## Ring wise Matrix Rotation

Introduction
Matrices have always been of interest in the field of encryption, specifically matrix rotations which leads to a symmetric as well as asymmetric cryptography. To learn more about regular matrix rotation please check my recent posts on the subject. This however is a fancy Ring wise Matrix Rotation and is no where related to the regular rotation of matrices.
Problem Statement
You are given a M*N grid with the restriction that the minimum of M and N is an even number. Rotate each of the rings by a distance K. We can choose the direction of rotation to be either clockwise or anti-c...

Read More