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

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

Seed in Random Number Generation

Random Numbers Randomization is an awesome concept. Efficiency of most of the algorithms are proportional to how randomly the algorithm is implemented. Talking about one the best sort algorithms - Quick Sort. The efficiency depends on the choice of pivot and it is wise to choose a pivot randomly to get an even distribution of elements around it. Of course no one can beat my bad luck if my randomly chosen pivot misbehaves. But still you will be luckier and have a better running time and upper bound on the running time of this algorithm. This is not the only algorithm where randomization ...
Read More

Resource Management in Game

Introduction This post is the next in the game development series. In this post we will learn about Resource Management in the Game. After writing the game engine, now we can add some background to our game. We will try to add our menu as well and try to add navigation in the menu. Once that is done we will be able to move through the menu and choose various options. Without wasting much time, lets dive in. Objects in the Game There are many different type of entities in our game. They can be categorized into Screens and Actors and few more. You have absolute freedom to make it more gran...
Read More