Q: Find the greatest common divisor of 2 numbers a and b and also find 2 numbers x and y such that ax + by = GCD(a,b)

Sol:

Every number is divisible by 1, and so the least common divisor of a pair of numbers is 1. The more challenging problem is to find the Greatest Common Divisor (GCD), the largest divisor common to a set of given integers.

The naive way of finding the GCD is to find all divisors of one number and test each of these for divisibility on the second. Another way would be to find the prime factorization of both numbers and find product of all common factors. But, as you can see, these methods are more brute-force and will be computationally intensive.

Euclid’s algorithm for GCD computation was one of the earliest interesting algorithms in history. It is based of a couple of basic observations.

1. If b divides a, then GCD(a,b) equals b

2. If a = bn + k, then GCD(a,b) = GCD(b,k)

The first observation is pretty straight forward. If b divides a, then a = bn where n = 1,2,3.. and so GCD(a,b) = GCD(bn,b) = b

For the second observation, GCD(a,b) = GCD(bn+k, b) Any common divisor of a and b is now dependant on k, since bn is divisible by b.

From this you see that the algorithm is recursive. Replace the bigger integer by its remainder mod smaller integer. This basically cuts down the integer size to at least half for each step, and thus the running time of the algorithm is logarithmic number of iterations to the naive ones discussed above.

An outcome of Euclid’s algorithm is that you can find more than just the GCD(a,b). In fact you can also find two integers x and y such that

ax + by = GCD(a,b)

int GCD(int a, int b, int& x, int& y)
{
      int prevX, prevY;
      int gcd;

      if(b > a)
      {
      return GCD(b,a,y,x);
      }

      if(b == 0)
      {
            x=1;
            y=0;
            return a;
      }

      gcd = GCD(b, a%b, prevX, prevY);
      x = prevY;
      y = prevX - FLOOR(q/b) * prevY;
      return gcd;
}

Q: You are given two singly linked lists, such that they start from two different nodes (head) and then, a few nodes down the list, they meet at a common node and then share all the nodes henceforth until the tail. The task is to find the first common node.

Sol:

There are a few ways to solve this. The trivial solution would involve storing all the nodes of the smaller list and traverse each node in the bigger list, comparing each node to the already stored nodes. Instead of storing the nodes you can traverse the whole (smaller) list each time. It is clear however, the each of these are inefficient (time and space)

—————————————————————————————-

Here’s another way to do this. Much more efficient but requires modifying the original list

Let list L1 have ‘a’ number of nodes leading to the intersecting node and ‘k’ number do nodes afterwards;

a+k=len1 –> equation 1

Let list L2 have ‘b’ number of nodes leading to the intersecting node and ‘k’ number do nodes afterwards;

b+k=len2 –> equation 2

You can calculate len1 and len2 by traversing the list

subtracting the above 2 equations you get

a-b= len1-len2; –> equation 3

Now reverse List 2 and then traverse from the head of List 1 and count the number of nodes as you go, you will eventually reach the original head of List 2. Let the length you just computed be len 3

a+b = len 3 –> equation 4

You have 2 equations (3 and 4) and 2 unknowns (a and b)

a and b are the lengths of list from the head of each list to the intersecting node.

You can re-reverse List L2 to revert it to the original state

—————————————————————————————-

Sometimes you do not want to alter the start of list. In multithreaded applications, other threads could be reading from the list and Locking leads to performance issues. The following solution will solve the problem without actually altering the list

First, Traverse the 2 lists and find their lengths (L1 and L2). Traversing the longer list starting from its head until you move (L1-L2) nodes. At this point both the nodes are equidistant from the first intersecting common node. Now Traverse both the list one node at a time and compare the nodes at each step until you find a match. This matching node is the intersecting node.

—————————————————————————————-

Buffer Overruns is one of top sources of security issues today.  These are typically caused by trusting input data to a function that is external and is unchecked. Most of the times, this is unintentionally invoked by bad sloppy code. However, when done intentionally by a hacker, this can cause havoc. Some of the most common, buffer overrun prone functions include strcpy, memcpy, strcat etc… In unintentional buffer overruns, this mostly results in writing to memory not owned by your processes address space. In such cases this would end, in an access violation or a core dump, causing the program to be aborted in most cases.  However, these buffer overruns can be exploited to run arbitrary code on the machine, even code that is injected in by the attacker.

There are different types of buffer overruns.

• Static Buffer Overruns: These type of buffer overruns occur, when a buffer that is declared on the stack is overwritten by copying more data than the buffer can hold. It so happens, that the variables (buffer in this case) declared on the stack are located next to the return address of the function’s caller. As I mentioned above, this usually occurs when user input is unchecked, e.g. strcat.  And because the return address is next to the buffer on the stack, overwriting the buffer, means overwriting the return address, which is what gets executed with the function returns.  An attacker can carefully exploit the overrun in such a way the data that is overwriting the return address, is an address of a function that he wants to execute.
• Heap Overruns: Like Stack Overruns, Heap overruns can also cause memory and stack corruption. But unlike contrary developer belief, although heap overruns are harder to exploit, they are definitely exploitable.
• Array Indexing Errors (Overruns and Underruns): These type of errors are less exploited compared to static buffer overruns. You can think of an array as a block on memory (buffer) that you can index into and then read/’write’ from that location. Bad array implementation do not check indices well before access the memory locations. Sloppy code like this can be exploited to run arbitrary code and create havoc. (Well, in some cases you may never ever now that your machine is freely accessible and controlled by the attacker ). Again, unlike contrary developer belief, don’t be fooled that only memory past the end of the array can be exploited.
• Format Strings Exploits: These type of exploits are not exactly buffer overruns, but they lead to the same class of problems. These errors are usually caused in functions that take in variable number of arguments, because there isn’t a good way for the function to determine the number of arguments passed into these functions. (printf family in the CRT). The %n type field for printf represents the number of characters successfully written so far to the stream or buffer. This value is stored in the integer whose address is given as the argument. So, this can basically be used to write into memory of the processes address space. But how can an attacker inject such code? The answer lies to the way the sloppy programmer writes code ala printf(input), rather than printf(”%s”, input). The latter prevent the user from using his own format, since its already defined, unlike the earlier case, where the input can be manipulated to create the format string.

In the next posts, I will go over examples of exploiting each of these examples and best practices to prevent such exploits from happening in the first place.

• Foo* const ptr: ptr is a const pointer to a Foo Object. The Foo object can be changed using the pointer ptr, but you can’t change the pointer ptr itself.
• const Foo* ptr: ptr points to a Foo object that is const. The Foo object can’t be changed via ptr.
• const Foo* const ptr: ptr is a const pointer to a const Foo object. Neiher can the pointer ptr be changed, nor can you change the Foo object using ptr.

Reading the declaration right to left is a easy way to remember what they mean.

As the name suggests, a copy constructor is called whenever an object is copied. This happens in the following cases:

• When an object is create from another object during initialization (Class a = b)
• When an object is created from another object as a parameter to a constructor (Class a(b))
• When an object is passed by value as an argument to a function (function(Class a))
• When an object is return from a function (Class a; … return a;)
• When an exception is thrown using this object type (Class a; …. throw a;)

Whenever an object copying scenario like the ones above is encountered, the copy constructor is invoked. A copy constructor can be either user defined or compiler defined. If the user does not define a copy constructor, then the default compiler defined copy constructor will be invoked during object copy scenarios. The default copy constructor is a bit-by-bit (member wise) copy. But often you will encounter situations where this is not desirable since this is just a shallow copy and sometimes you do not want an exact copy or you may want to do some custom resource management. 

Class t1;
Class t2=t1; // Copy Constructor is invoked
Class t3;
t3=t1; // Assignment Operator is invoked

In the Code snippet above, the constructor is invoked twice, during the creation of objects t1 and t3. (Creation of t2 invokes the copy constructor). The destructor is invoked 3 times though. In cases like these, if the constructor allocates memory and the destructor frees it, you will see the t2’s destructor will try to delete already deleted memory, if t1 is destroyed before t2 or vice-versa. Meaning, you are hosed. To prevent this, a user defined copy constructor needs to be provided. which doesn’t do a simple bit-by-bit but rather assigns memory specifically for the object and does a deep copy if required.

To define a copy constructor for a class T, a constructor of the following format needs to be defined.

Class T
{
…

    T(const T& t)
…
}

You need a reference because if it were T(T t), it would end in a infinite recursion. (Was that an oxymoron?). const because you are not changing the object in the constructor, you are just copying its contents

Some Rules of Thumb:

• Don’t write a copy constructor if a bit-by-bit copy works for the class
• If you defined your own copy constructor, it probably because you needed a deep copy or some special resource management, in which case, you will need to release these resources at the end, which means you probably need to define a destructor and  you may also want to think of overloading the assignment operator (beware of self-assignment)

Constructors do not have return type and so they cannot return error codes. How are errors or exceptions handled in constructors? What if the calls that you make in the constructor can actually throw exceptions? How do you let the caller know something bad happened in a constructor?

There are a few ways to do robust error/exception handling in constructors

1. Do as little in the constructor has you can. Then provide an Init() function in the constructor, which does the normal initialization stuff. The user can then call this function after creating an object. The problem here is, its up to the user to actually call the Init() function. The user could potentially miss this step, making this method error prone. However, there are a lot of places where this methodology is used. You are trying to eliminate error handling in the constructor by using this method
2. Another way to do this is by putting the object in a Zombie state. This is one approach you can take especially if you do not have the option of using exceptions. When you go with this option, you will also to do provide a function that will check the state of the object after construction. The downsides to this option is that, its up to the user to do these checks and the users will need to do this every time one attempts to create an object. It’s usually always better and cleaner to throw an exception instead. Use the Zombie option as a last resort.
3. The downsides to the above methods can be reduced by making the constructor private or protected, expose a CreateInstance() public method, and do all the error handling here rather than leave it to the user. But sometimes, its not possible to handle all the error conditions in a generic manner and you will need to throw an exception.
4. If an exception is thrown in the constructor, the destructor will not get called. So you need to handle and clean up as much as you can before you leave the constructor. The best way to do this is using the “resource allocation is initialization” technique. I will cover this topic separately in a future post. But the basic idea is to assign resource allocation and cleanup to other objects. Basically, you are trying to get allocation out of the way (indirect) so that you don’t have to do it explicitly. When you don’t allocate something directly, you don’t have to release it either because it will be done by the component or class who deals with it. E.g. If you need to allocate some memory or open up a file, You can use smart objects (smart pointer, auto_ptr, smart file handlers etc..) instead of calling new or fopen directly. When you do this, and if an exception is thrown in your constructor, the smart objects will automatically release the resources it acquired, as the stack unwinds. If you do not use the “resource allocation is initialization” technique, the user will need to wrap the statements in try/catch block and rethrow after cleaning up the mess, something like what the finally block does in Java or C#. Although this works in theory, it’s up to the user to make this work and it also always a source of errors and bugs (esp. memory and handle leaks) and is messy

As you have seen, there is no “one size fits all” rule to do error/exception handling in constructors. I have listed the most commonly used methods and one of these should work most of the time.

Swapping variables is a very common operation used it tons of algorithms like sorting etc. The most common and obvious technique is using of a temporary variable to swap values between two variables

void swap(int &i, int &j)
{
   int temp = i;
   i = j;
   j = temp;
}

Instead of writing a separate function for each data type, you could write a MACRO or templatize the function.

Swapping without using a temporary variable is an age old trick and there are a few ways to do this. You could use of the basic arithmetic operations like +,-,/,*

1: void swap(int &i, int &j)
2: {
3:     i=i+j;
4:     j=i-j;
5:     i=i-j;
6: }

The technique involves storing the sum of variables in one of them and then extracting it back by subtracting the other number. There are different variants to this technique. E.g, instead of starting by storing the sum, you could store the difference, product or the quotient. The last two could lead you to round-off and integer division errors. However all of them have one fundamental flaw. Its in line 3, and the issue is that this could lead to an overflow error.

This is another technique the gets you around these issues; the XOR Swapping technique

void swap(int &i, int &j)
{
     i = i ^ j;
     j = j ^ i;
     i = i ^ j;
}

This is an elegant technique and should work well with any primitive data type and you could write a simple MACRO like

define SWAP(i, j) (((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))

define SWAP(i, j) ( (i==j) || ((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))

Singleton Pattern: Part 3 Double Checked Locking

In the last post on Singleton Patterns, We looked into a thread safe mechanism to create singleton objects. The concept works well enough for most systems. However, when this becomes a hot section (heavily accessed) in your code, we will begin to hit performance problems. Here’s why: Lets say we have a high performant system, with 50-100 threads working around like magic, sharing tasks and running as fast as possible. Lets say that all the threads hit this hot section very often. This will result in the hot section being a real bottle neck, synchronizing and slowing down all the threads. Every thread enters this critical section and blocks every other thread from using this section. But is this really required? The ‘clever’ double locking system ‘tries’ to fix this problem.

Instead of locking down the critical section and blocking all the threads, this technique gives a chance for the threads to asynchronously check, whether or not it needs to enter this section in the first place. If it does (when instance != null), it then locks the section and proceeds in a normal thread safe manner where it does the second check. So the name, Double Checked Locking.

  class Singleton
  {
    private:
    static Singleton instance;


protected Singleton() 
{
}

public static Singleton CreateInstance()
{

  if(instance == null) //first check
  {
      // Use a mutex locking mechanism 
      //  that suits your system
      LockCriticalSection(); 
      if (instance == null) //second check
      {
        instance = new Singleton();
      }
      UnLockCriticalSection();
   }
   return instance;


}
}

Note: If you are using Java to implement this, beware that there are issues in Java’s memory model that prevent this technique from working correctly. This issue is however, fixed. So make sure you have the latest JDK if you plan to use this in your code. In a later post, I will go over the bug in JDK, more specifically in Java’s memory model that causes this problem.

A normal search across a BST (Binary Search Tree) would look like this

bool BinaryTree::Search (int data )
{
    Node *current = this->root;

while ( current != NULL ) 
{
    if (current->data < data)
    {
        current = current->left;
    }
    else if (current->data > data)
    {
        current = current->right;
    }
    else if ( current->data == data )
    {
        return true;
    }
}


return false;
}

 
static Node* Leaf;


bool BinaryTree::Search (int data )
{
    Node *current = this->root;

Leaf->data = data;

while ( current->data != lead->data ) 
{
    if (current->data < data)
    {
        current = current->left;
    }
    else
    {
        current = current->right;
    }
}

return (current != Leaf);


}