Author: dharam

Balanced Search Trees – AVL Tree

Introduction When we talk about balanced search trees, we specifically are talking about two things. A search trees. A height balanced tree. Here in this post we will consider a Binary Search Tree and will try to equip with features to self balance itself upon modifications. Before starting up with the logic and code part we need to understand the motive behind this kind of data structure and more precisely we need to understand the need of such a complex scenario. Apart from that we also need to understand what it means to be termed as balanced. What does balancing means? We sa...
Read More

Dynamic Programming – CrazyNumbers

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