interview questions

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

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

Closest Pair Points

Introduction A very interesting problem, indeed. I presume, not a complex one either. Here is what the problem statement looks like. "Given a set of N points in a plane, find the closest pair points". A question which is always asked in interviews in various forms, here we will not just look at the solution but will also understand the intuition behind the solution. In the adjoining image, we have five points (A, B, C, D, E) in the plane. As a result of the solution we need to return one pair which has the smallest distance between them. Of course there can be multiple such pairs, we a...
Read More

Pattern Finding – KMP Algorithm

Introduction Now that you are fully equipped with the Boyer Moore Algorithm and have a notion of Pattern Finding. I would suggest you to get deeper into pattern finding. You can read about the benefits of pattern finding in my previous post about Boyer Moore. This post will try to make you familiar with all the thought processes which you can use to exploit the known properties of texts and patterns using KMP Algorithm. However, Boyer Moore seems to be slightly intuitive, this one is a real geeky way of finding patterns. Knuth Morris Pratt Yes! this is what KMP stands for, you can learn ...
Read More

Cloning Linked List having Next and Random Pointer

Introduction This question was asked by a colleague, although it seems to be simple at first but with given restrictions like running time and space limitations, it becomes tricky. You need to be good with Linked Lists to crack the right solution. Here we try to define the problem in more detail. Given a Linked List where each node contains two pointers next and random. The next pointer points to the immediate next node and the random pointer points to any random node in the linked list. Clone the linked list and return the head of the clone. There are definitely certain conditions impos...
Read More