Wednesday, November 9, 2011

How smart are the smart pointers ?

Untitled document

smart_pointer is a blessing for a carefree programmer who wants to allocate memory in heap and forget about deleting it. Sounds great. Its really tough to track a pointer and carefully release the heap memory captured.

Also it relies on the fact that its easy to clear stack than heap. So, lets see how it works.

First lets see, how can we use a smart pointer class in our program and then we will go ahead to implement it. Please follow the comments for understanding.

We take an example class

class A

{

        public:

        //This variable is meant to track the

        // number of instances of the class that are existing.

        static int count;

        //Constructor

        A()

        {

                //New instance is created so increment.

                count++;

        }

        //Copy contstructor

        A(A& obj)

        {

                //New instance is created so increment

                count ++;

        }

        //Assignment operator

        A& operator =(A& obj)

        {

                //New instance is created so increment

                count ++;

        }

        ~A()

        {

                //Instance removed, so decrement the value.

                count --;

        }

        void display()

        {

                cout << "Its me \n";

        }

};

Now we look at the main function where we will be using the smart_ptr class.

int main()

{

        //This is how we create a smart_ptr object

        // see the pointer of type A is stored inside the

        // smart_ptr object

        smart_ptr<A> ptr(new A());

        smart_ptr<A> ptr1;

        //Testing assignment operator

        ptr1 = ptr;

        //Testing self assignment

        ptr = ptr;

        // Verifying how many instances of A are there.

        cout << "A::count = " << A::count << endl;

        //Using overloaded -> operator to call

        // member functions of class A

        ptr->display();

}

Now we implement the smart_ptr class, as per the usage. So, here it is.

template <class T>

class smart_ptr

{

        private:

               // The pointer which is managed

                // by the smart_ptr class

                T* m_ptr;

                //Keeps track of the number of references

                //the allocated memmory.

int ref_count;

        public:

                smart_ptr()

                {

                        m_ptr = 0;

                        ref_count = 0;

                }

                smart_ptr(T* ptr)

                {

                        m_ptr = ptr;

                        //increment the ref count

                        //as this is the first reference

                        ref_count = 1;                

                }

                smart_ptr(smart_ptr& obj)

                {

                        cout <<  "Copy Contstructor\n";

                        ref_count++;

                }

                //Assignment  operator overload

                smart_ptr* operator =(smart_ptr& obj)

                {

                        if(&obj != this)

                        {

                                ref_count++;

                        }

                        else

                        {

                                cout << "Self assignment\n";

                        }

                }

                // Destructor

                ~smart_ptr()

                {

                        cout << "Deleteing the smart_ptr instance\n";

                        // Decrement the reference count as

                        // the instance is released

                        ref_count --;

                        if(ref_count == 0)

                        {

                                // Delete the pointer

                                // as there are no references to it.

                                delete m_ptr;

                        }

                }

                T* operator ->()

                {

                        return m_ptr;

                }

};

Tuesday, October 11, 2011

A Gram of Anagram


Last week attended an interview, and this was the question the interviewer came up with to test my problem solving.

" Give a logic to generate valid anagrams of a word, provided you have a dictionary to confirm the validity"

After a while of scribbling on the blank paper I came up with the following answer.

If I take a dictionary as a Hash Map as every word is unique and the Key is a binary(or Hex) representation of the word. Then if I have a word I can easily find the meaning of it with O(1) complexity.

Now, if we have to generate all the valid anagrams, we need to verify if the generated anagram is in the dictionary, if it is present in dictionary, its a valid one else we need to ignore that.

I will assume that there can be a word of max 100 characters(or more but there is a limit).

So any word we take it as a sequence of indexes like a word "hello" can be represented like "1234". Now the anagrams of "1234" are "1243", "1242" ..etc

The only thing we need to do is to store all such combinations of indexes for a particular number of characters. This is an one time task. And then words can be generated from the combinations by picking the characters from the index.Hence we get the anagrams.

To verify if the anagrams are valid or not, just index into the dictionary and validate.

The only thing need to be handled is the duplicates.That can be done easily. As an when we need to compare with the previous ones that has been searched in dictionary.

And I said the solution emphasizes on performance.

I don't know if this is the answer the interviewer was expecting or something else but I can guess it now as I did not get any response for further rounds.

Really need to work on my problem solving skills.