Rectangle Intersection – Find the Intersecting Rectangle

Q: Rectangle Intersection – Find the Intersecting Rectangle

In the last post, we looked into methods to determine whether or not two given rectangles intersect each other. Lets go one step ahead this time and find the intersecting rectangle.

As in the previous post, I am basing the struct off of the Windows co-ordinate space, where the origin is on the top left of the screen. The x-axis moves towards the right and the y-axis moves towards the bottom.

bool Intersect(RECT* r3, const RECT * r1, const RECT * r2)
{
    bool fIntersect =  ( r2->left right
                                && r2->right > r1->left
                                && r2->top bottom
                                && r2->bottom > r1->top
                                ); 

    if(fIntersect)
    {
        SetRect(r3,
                     max(r1->left, r2->left),
                     max(r1->top, r2->top),
                     min( r1->right, r2->right),
                     min(r1->bottom, r2->bottom));
    }
    else
    {
        SetRect(r3, 0, 0, 0, 0);
    }
    return fIntersect;
}

First, determine whether or not the two Rectangles intersect each other, Then use the SetRect method (which basically creates a RECT with the given points) and create the intersecting Rectangle

SetRect(r3,
    max(r1->left, r2->left),
    max(r1->top, r2->top),
    min( r1->right, r2->right),
    min(r1->bottom, r2->bottom));

Since the algorithm is pretty straightforward, I am not going to include more detailed analysis in this post, unless I get enough request comments or email

NOTE: For all invalid rectangles passed to the function, the return value is always [0,0,0,0]. You can also choose to return error codes after checking for validity.

Rectangle Intersection – Determine if two given rectangles intersect each other or not

Q: Rectangle Intersection: Determine if two given rectangles intersect each other or not

Definitions:

Intersect: Two Rectangles intersect each other if the share a common area.

Assumptions:

• Both the rectangles are aligned with the x and y axes.
• Rectangles just touching each other are considered as non-intersecting.

First let’s create a data structure for use in our problem. Rectangle Intersection algorithms are usually used in graphics problems. Depending on the precision needed to represent the co-ordinates, you may choose the required data type. In this case, I am going to use a LONG.

I am also basing the struct off of the Windows co-ordinate space, where the origin is on the top left of the screen. The x-axis moves towards the right and the y-axis moves towards the bottom.

struct
{
    LONG    left;
    LONG    top;
    LONG    right;
    LONG    bottom;
} RECT; 

bool IntersectRect(const RECT * r1, const RECT * r2)
{
    return ! ( r2->left > r1->right
        || r2->right left
        || r2->top > r1->bottom
        || r2->bottom top
        );
}

The above algorithm finds the conditions at which the rectangles do not intersect and then negates the values to get the result. There is a straight forward way of doing the same algorithm, but it requires far more conditions than the one above. Consider the diagram below

  S1   |         S2          |   S3
       |                     |
    TOP|LEFT                 |
-----------------------------------
       |                     |
       |                     |
       |                     |
  S4   |         S5          |   S6
       |                     |
       |                     |
-----------------------------------
       |                RIGHT|BOTTOM
       |                     |
  S7   |         S8          |   S9

This is an illustration of one of the rectangles (R1). The top left corner of R2 can like in any of the 9 segments, S1 through S9. Based on each of these cases, and depending on the position of the other vertices, it can be determined whether the two rectangles R1 and R2 intersect each other. E.g. If R2’s top left corner is in S1, the bottom right corner needs to be in S5 or beyond (S5,S6,S8,S9) for the rectangles to intersect. Or if the top left corner of R2 is in S5, it is an automatic case of intersection. Clearly, in this case there are a lot of cases to consider and therefore and lot of conditions to check.

The conditions where the rectangles do not intersect, is where the bounds of one Rectangle is beyond the bounds of the other. The conditions are pretty straightforward as shown in the code above. Negating this value solves the original problem.

There is one more conditions (negation) that can be avoided by changing the inner condition. I will leave that as an exercise for the reader.

NOTE: For all invalid rectangles passed to the function, the return value is always false. You can also choose to return error codes after checking for validity.

Shuffling – Shuffle a deck of cards – Knuth Shuffle

Q: Shuffling – Shuffle a deck of cards – Knuth Shuffle

Shuffling is a process where the order of elements in a data set is randomized to provide an element of chance. One of the most common applications of this is to shuffle a deck of cards.

Mathematically, the shuffling problem, is basically a problem of computing a random permutation of N objects, since shuffling a deck of cards is basically subjecting a deck of cards to a random permutation.

Card shuffling algorithms are used in computer games, casinos, etc. Before we delve into the algorithms, let’s look into what are really trying to solve here. These are the kind of things that an interviewer will be looking into apart from the algorithm itself. The choice of algorithm and data structure chosen for this, needs to be based on where, who and how this is going to be used.

As I just mentioned, this is something used in the gaming industry (Computers, Video Games, Casinos etc…). This purpose of this algorithm is to introduce an element of chance into the data set (deck of cards) and make it impossible for the user to find a pattern and predict the occurrence of un-dealt cards. The size of the data set is small (52 elements), and so the complexity of the algorithm is usually not of high concern. A O(n^2), v/s an O(n lg n) v/s an O(n) for example would be a few milliseconds. Of course, a real bad implementation with O(n^n) would certainly be of concern, although I guess it is going to be difficult to come up with a O(n^n) algorithm in the first place.

It is important to look at problems with this angle. Sometimes, it takes too much time and effort to come up with a faster algorithm, and it the end it could end up providing very less value. The keyword here cost/benefit ratio.

OK, so we’ve learnt that the complexity of the algorithm we choose is not of high priority. What else? Since this is something that will be used in a casino, we need to eliminate the element of predictability. We don’t want people to be able to predict what the next card in the deck might be, even with a low probability.

The problem itself involves randomization, and we are definitely going to deal with random numbers. Some random numbers, have bias on some of bits in a number, e,g rand() has a bias on the upper bits in a number. We want to be avoiding such generators.

There are few basic well known solutions to this problem, the first of this is an O(n lg n) algorithm. I won’t be writing code for this, but I will go over the algorithm. The solution involves simple assigning a random number to each card, and sorting them in order of their assigned number. There is a chance that two of the cards are assigned the same number. This check can be checked each time you assign a number, or even better this can be checked when you sort the cards and redo it all over again, or redo the same problem on the smaller set usually 2 cards, if you have got more than 2 cards, actually even 2 cards, then you’ve chosen a bad random number generator.

The more elegant and faster of the two algorithms is also known as the Knuth Shuffle, popularized by Donald Knuth, in his book , The Art of Computer Programming. The algorithm was originally published by R.A. Fisher and F. Yates [Statitiscal Tables (London 1938, Example 12], in ordinary language, and by R. Durstenfeld [CACM 7 (1964), 420] in computer language. Here’s the algorithm in ordinary language.

Let X1, X2…. XN (In this case N=52) be the set of N numbers to be shuffled.

1. Set j to N
2. Generate a random number R. (uniformly distributed between 0 and 1)
3. Set k to (jR+1). k is now a random integer, between 1 and j.
4. Exchange Xk and Xj
5. Decrease j by 1.
6. If j > 1, return to step 2.

void KnuthShuffle(int* pArr)
{
    int rand;
    for(int i=51;i>=0;i--)
    {
        rand=GenRand(0,i);
        swap(pArr[i], pArr[rand]);
    }
}

GenRand(int min, int max) generates a random number between min and max.

For the mathematically oriented:

Traditional shuffling procedures turn out to be miserable inadequate. Reportedly, expert bridge players make use of this fact when deciding whether or not to finesse. At least seven “riffle shuffles” of a 52-card deck are needed to reach a distribution within 10% of uniform, and 14 random riffles are guaranteed to do so. [Aldous and Diaconis, AMM 93 (1986), 333-348] [Knuth, The Art of Computer Programming, Random Sampling and Shuffling]

Prime Numbers: Finding the first N Primes – Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm

Q: Finding the first N Primes
Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm

We have been using regular Computer Science procedures for improving efficiency here. It’s time to borrow some good old Math theorms now. The first of the techniques, that I am going to use is the Sieve of Eratosthenes

This is an algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number you wish to include in the table. Cross out all numbers >2 which are divisible by 2 (every second number). Find the smallest remaining number >2 . It is 3. So cross out all numbers >3 which are divisible by 3 (every third number). Find the smallest remaining number >3 . It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number).

Continue until you have crossed out all numbers divisible by sqrt(n), The numbers remaining are prime.

This idea can be used easily to find all primes below a given number. But, how do you use this to find the first N primes. Here’s a quick idea, Use Erdos Prime Number Theorm. You use this to find a Cap, which is the number until which you need to check to get N primes.

float FindPrimeCap(int x)
{
    float flX = (float) x;
    float flCap = 1.0f;
    for(float f=2.0f; flCap

FindPrimeCap uses Erdos Prime Number Theorm. Since this is asymptotic, it is not accurate enough for small numbers.
However, timing this code showed that this method was faster than all of the previous method we discussed.
In fact more prime were found in lesser time, using this method compared to the previous ones.

In a later post, We will analye the performance of all the methods we have discussed so far

Prime Numbers: Finding the first N Primes – Part 3 Prime Divisors

Q: Finding the first N Primes

In the last post we looked into making some improvements over Trivial Approaches

Lets look at ways into how we can make this faster. The improvements made in the last post where basically about skipping everyone second and third number, and not skipping divisors that are multiples of 2 and 3. This holds true, because, if the number were a multiple of 2 or 3, it would be dealt with in the first place, where we skipped all numbers that were multiples of 2’s and 3’s. Now this idea can be extended to number upto 5, 7, 11 and so one. The general way to do this will be to store the primes already found and only use these primes are divisors.

void GetPrimesPrimeDivisiors(int n)
{
    int* prime = new int[n];
    prime[0]=2;
    int count=1;
    int j=3;
    while(count

Prime Numbers: Finding the first N Primes – Part 2 Skipping Multiples

Q: Finding the first N primes.
In the last post, we looked into some trivial approaches. How can we make this faster?

Most of the work in problems like these (Finding matches) are spent in the core problem itself (Finding the match), in this case, Primality test. So lets look into how we can avoid this? One simple approach is to not do primality checks for even numbers

void GetPrimesSkipEven(int n)
{
    // Start from 5
    int j=3;
    // Set count to 1
    // 2 is already a prime
    int count = 1;
    while(count

Improvements In GetPrimesSkipEven:

1. Every second number (even) is not tested for primality
2. In primality test, division test are reduced by half, since we do not divide by even numbers any more (i+=2)
3. Modulo divisions are replaced by bit operators (i%2) == (i&1)

How can we get better,

void GetPrimesSkipSecondThird(int n)
{
    // Start from 5
    int j=5;
    // Set count to 2,
    // already 2 primes have been found (2 and 3)
    int count = 2;
    while(count

Improvements In GetPrimesSkipSecondThird:

1. Every second and third number is not tested for primality
2. In primality test, division test are reduced around 60%, since we do not divide by numbers divisible be 2 or 3
   Skip incrementing i by 2 or 4 (alternatively)
3. Modulo divisions are replaced by bit operators (i%2) == (i&1)

In a later post, we will look into the speeds of all these, but to those curious ones out there, I am list faster algorithms as we go by

Prime Numbers: Finding the first N Primes – Part 1 Trivial Approaches

Q: Finding whether or not a number is prime?

Sol: There are several ways to solve this problem. Lets look into some of the more trivial approaches as usual and try to improve on these as we move along.

By Definition, a prime number is a positive integer having exactly one positive divisor other than 1. Therefore the straightforward way to do this will be to check divisibility of the given number starting from 2 to the given number.

There are some easy ways to improve upon this basic approach.

1. You do not have to check for all numbers upto n. Some would argue that checking upto n/2 would suffice, since anything greater than this will not divide the given number as a whole number
2. Actually, you will not even need to go upto n/2. Checking upto sqrt(n) would suffice. This is because anything if there was a number greater than this that would actuall divide the divide the given number, you would have already visited the factor since that number will be less than or equal to sqrt(n). E.g If 91 was the given number, you would not have to check for numbers greater than 9. This is beacause although 13 divides 91, this would already have been found since you would have checked 7 prior to this and this is less that 9 (floor(sqrt(91))

void GetPrimes(int n)
{
    // Start from 3
    int j=3;
    // There is already one prime (2), so set count=1
    int count = 1;
    while(count

Linked List: Detect a Cycle in a linked list and Fix the cycle

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.

In the Previous posts, we discussed several ways to find cycles in a list, starting from some O (n^2) trival solutions, to the classic Flyod’s Cycle Finding Algorithm (also known as the Hare and Tortoise approach, or the 2 pointer approach) and a asymptotic faster variant, to a list reversal technique (which I havent seen being used anywhere). There are a few O(n lg n) solutions which I did not mentoin here. (If there is enought interest I will post this).

Lets look into a way to fix this cycle. Of Course, there are trivial O(n^2) solutions for this, but I will not go through this. I will discuss an O(n) solution in this post

Sol 6: Fixing the Cycle

A combination of the two O(n) cycle detecting algorithms (2 pointer approach and list reversal methods) will be used for this solution. Let’s look into an illustrative solution

Fig (i) is how the orignal list (with a cycle) will look like. The goal is to fix the cycle. This can be done by finding N3 and setting N3->Next to NULL. The question is how to we find this.

N0 is the head.

Run one of the Two-Pointer cycle finding methods that I disscussed before on this list. The two pointers will meet somewhere inside the loop (3-4-5-……10-11-3). Lets call the node that the

pointers meet as N1. Once the two pointers meet, hold one of the pointers(P1) at N1 and let the other other pointer(P2) traverse the cycle once, while keeping a count of the number of

nodes in the cycle. Let the number of nodes in the cylce be x. Now, point pointer P2 to the head of the list (N0) and run the traverse the list until you find N1 while keeping a count of

the number of nodes from the head N0 to N1. Lets this number be y.

N0            N2
0--->1---->2---->3---->4---->5---->6
                 |                  |
                 |                  |
            N3  111—->2—->310—->9—->8 N1

      Fig (ii)

After reversal get a count of nodes from N0 to N1. Let this number be z.

The idea is to get the number of nodes from N0 to N2. Once we have this, we can get the address of N2 and then traverse the list in the loop, until we find a Node whose next is N2 and then set it to NULL.

To solve this:

Our Variables:
Number of Nodes from N0 to N1 before reversal = y
Number of Nodes from N0 to N1 after reversal = z
Number of Nodes in the loop = x
Numver of Nodes from N0 to N2 = k

We need to solve for k. We have the following equation at hand.
y + z = 2k + x (This equation could differ slightly if the number of nodes caluclated were inclusive of the nodes or not)
k = (y + z – x) / 2

I will put the code in a later post.

Linked List: Detect a Cycle in a linked list – List Reversal

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a few soIutions prior to this. Lets look into an easy but not so commonly used solution.

Sol 5: Find Cycle through List Reversal

We’ve looked into some classic approaches of Linked List Cycle Finding Methods (Hare and Tortoise) in the previous posts. Lets see a more easier straightforward approach. I am a bit surprised this is not a usually used method.

The idea is pretty simple. Reverse the list!!. If you meet the head in the process of reversal, you’ve got a cycle. Below is some sample code for this. The exit condition, when you do not find a cycle is when you reach the tail node. Either ways the list needs to be reveresed again, so that we leave the list in its initial state.

void LinkedList::IsLooped1() {
LNode* prev=NULL;
LNode* current=NULL;
LNode* tmp=head;

while(tmp) {
    prev=current;
    current=tmp;
    tmp=tmp->next;
    if(tmp==head)
      cout < < "Found Loopn";
    current->next=prev;
}
head=current;
Reverse(); //Leave list in original state

}

Linked List: Detect a Cycle in a linked list – Two Pointers Approach (Faster)

Q: Find whether or not there is a cylcle in a linked list? If so, Fix the cycle.
There are several solutions to this problem. I already discussed a couple of soIutions before. Lets look into more commonly used (classic) solutions

Sol 4: Two pointer approach (Faster)

In the last post we discussed about the regular two pointer approach and a bit about its background. Lets look into how we can make it a bit faster.

What can you do here to make it faster. In the regular approach, the faster pointer goes 2 nodes at a time and the slower pointer goes 1 node per iteration. You cannot really change the speed of the slower pointer, because you definitely need to check every node at least once. But what about the fast pointer? Why just have it go 2 nodes per iteration? Why not 3 or more? And what improvements can you get here? Well. the faster it goes the lesser, the number of assigments and null checks when you traverse the faster pointer. This will be helpful, especially when the cycle (loop) is large. But how can fast do can you go. Since you don’t really know, you could do an exponential advancement. What this means is that, start with 2 nodes per iteration, and see if the slower pointer meets it. If not, traverse 4 nodes in the next iteration, and then 8, 16, 32…

Here’s some sample code that illustrates this.

void LinkedList::IsLooped2() {
    LNode* first=head;
    LNode* second=head;
int i=0;
int k=1;
while(first) {
    first=first->next;
    i++;
    if(second==first) {
            cout < < "Found Loopn";
            return;
    }
    if(i==k) {
        second=first;
        k*=2;
    }
}

}