Tuesday, January 31, 2012

Compiler's implementation of New and Delete operators

Digging deeper into the implementation of New and Delete operators,  raises couple of question as listed below.
  • Under what circumstances a bad_alloc exception is thrown.
  • What if there is an exception thrown inside a constructor.
  • Who releases the heap memory allocated for the object, when constructor fails.
  • Is it possible to reuse a chunk of memory on the heap to reconstruct the object.
  • How to distinguish whether the exception is due to heap allocation error or due to a failing constructor.

Rather trying to answer these questions individually, it's better to explore compiler implementation of  " new " and " delete " operators which eventually answers the above questions.

 Consider CellPhone,a class declaration below

     class CellPhone
         long IMEI ;
         char* DeviceName ;
         CellPhone(int ID, char* Name)
             IMEI = ID ;
         void* operator new ( size_t size );
         void operator delete (void* buffer);

The below instruction creates an instance of this class on the heap through " new " operator.

  CellPhone* PhoneObject = new CellPhone(900,"NOKIALUMIA") ;

New Operator
The "new" operator instantiates an object on the heap in two steps.

1) Allocate the required amount of  memory for the object, on heap
2) Call constructor of the class to initialize the object.

Instantiating the object on heap
To allocate memory on the heap "new" operator uses a function " operator new " as shown in the class declaration. This function allocates memory specified by " size_t " parameter on heap for the object and returns a " void* " pointer. And if the memory allocation fails, run-time will throw a " bad_alloc " exception.

      void* CellPhone::operator new(size_t size) throw (const char*)
        void* buffer = malloc(size);    
        if(buffer = NULL) throw "Not enough memory to allocate for the object";
        return buffer ;

The above function can be overloaded by the developer to provide custom implementations and excemption details.

Initializing the object by calling constructor 
Run-time achieves this functionality through " Placement new " operator which basically receives  " void* " pointer returned by " operator new " function, allocated on the heap and calls constructor of the  class to initialize the object as shown below.

Calling operator new function.
    void* buffer = operator new(sizeof(CellPhone)); // ----------->1

Typecast void* pointer to class specific pointer.
  CellPhone* PhoneObject = dynamic_cast<CellPhon*>(buffer);//Simple  static cast also would do.

Constructing the object at the allocated space using " placement new " operator.
       new(PhoneObject)CellPhone(900,"NOKIA LUMIA"); //------------> 2
    catch(exception& e)
        cout << e.what();
        operator delete( PhoneObject );
        throw "Exception inside constructor";
    void CellPhon::operator delete (void* buffer)
       buffer = NULL ;    

The above programming structure clearly explains, how the exceptions from constructor is handled. The " placement new " operator shown in instruction #2 receives pointer to the buffer allocated as shown in instruction #1 and tries to construct the object at that location.
During this process if there is any exception thrown inside the constructor it is caught and the allocated memory is released back to heap using " operator delete ( ) " function, which is a compliment of " operator new ( ) " function.
With the above implementation user would be clearly able to distinguish whether the " new " operator failed due to "heap allocation error " or due to " exception thrown " inside the constructor.

I hope this article was helpful in demystify obscure implementation details of  "New" and "Delete" operators. Suggestions and comments if any is appreciated.

Thursday, January 19, 2012

Code Sprint - 2 , Algorithmic Problems

This post is for all the self proclaimed geeks who love resolving complex algorithmic problems. Below are the questions  from  code sprint 2 an online coding contest. Time to overclock your brains. Happy coding.

The Living History
Coin toss
You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads. What is the expected number of additional tosses needed until you get N consecutive heads? Input: The first line contains the number of cases T. Each of the next T lines contains two numbers N and M. Output: Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places. Sample Input : 4 2 0 2 1 3 3 3 2 
Sample Output : 6.00 4.00 0.00 8.00

This is an approximation solution type problem. Please read about this type of problem at the bottom before attempting. Given n, print a permutation(p) of (0,1,2...n-1) From the permutation p, you can create n-1 (x,y) coordinates, where x and y are consecutive pairs in the permutation. You are also given the n x n square matrix V. For each coordinate, you can find an associated value in the matrix V. (x and y are 0-indexed) 
Task : Given n and V, find the permutation p that maximizes the sum of the associated values of the consecutive pair coordinates Constraints: n <= 50 Input: First line contains n Next n lines contains n integers, forming the matrix V 
Output : Space separated permutation of (0,1,2....n-1)

There are N points on X-Y plane with integer coordinates (x i , y i ). You are given a set of polygons with all of its edges parallel to the axes (in other words, all angles of the polygons are 90 degree angles and all lines are in the cardinal directions. There are no diagonals). For each polygon your program should find the number of points lying inside it (A point located on the border of polygon is also considered to be inside the polygon). Input: First line two integers N and Q. Next line contains N space separated integer coordinates (x i ,y i ). Q queries follow. Each query consists of a single integer M i in the first line, followed by M i space separated integer coordinates (x[i][j],y[i][j]) specifying the boundary of the query polygon in clock-wise order. Polygon is an alternating sequence of vertical line segments and horizontal line segments.
Polygon has M i edges, where (x[i][j],y[i][j]) is connected to (x[i][(j+1)%M i ], y[i][(j+1)%M i ].
For each 0 <= j < M i , either x[i][(j+1)%M i ] == x[i][j] or y[i][(j+1)%M i ] == y[i][j] but not both.
It is also guaranteed that the polygon is not self-intersecting.
Output : For each query output the number of points inside the query polygon in a separate line.

Sub-sequence Weighting
A sub-sequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [ (a 1 , w 1 ) , (a 2 , w 2 ) ,...,(a N , w N )]. For a sub-sequence B = [ (b 1 , v 1 ) , (b 2 , v 2 ) , .... ,(b M , v M ) ] of the given sequence : We call it increasing if for every i ( 1 <= i < M ) , b i < b i+1 .
Weight(B) = v1 + v2 + ... + vM .
Task : Given a sequence, output the maximum weight formed by an increasing sub-sequence 
Input : First line of input contains a single integer C. C test-cases follow. First line of each test-case contains an integer N. Next line contains a 1 , ... , a N separated by a single space. Next line contains w 1 , ... , w N separated by a single space. 
Output : For each test-case output a single integer number: Maximum weight of increasing subsequences of the given sequence.

Crab Graphs
A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the legs.( 1 <= K <= T, where T is given) Given an undirected graph, you have to find in it some vertex-disjoint sub-graphs each one of which is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized. Note: two graphs are vertex-disjoint if they do not have any vertex in common. 
Input : First line of input contains a single integer C. C test-cases follow. First line of each test-case contains three integers N, T, and M (the number of nodes, max number of feet in the crab graph, and number of edges, respectively). Each of next M lines contains two space separated v 1i , v 2i meaning that the there is an edge between vertexes v 1i and v 2i . Note that the graph doesn't have parallel edges or loops. 
Output : For each test-case, output a single integer indicating the maximum number vertices which can be covered by some vertex disjoint sub-graphs of graph which are crabs

Picking Cards
There are N cards on the table and each has a number between 0 and N. Let us denote the number on the ith card by c i . You want to pick up all the cards. The ith card can be picked up only if at least c i cards have been picked up before it. (As an example, if a card has a value of 3 on it, you can't pick that card up unless you've already picked up 3 cards previously) In how many ways can all the cards be picked up? Input: The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by integers c i ,...,c N on the second line. Output: Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007. 

Count strings
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'.
We define R to be a valid regular expression if: 1) R is "a" or "b" 2) R is of the form "(R1R2)" where R1 and R2 are regular expressions 3) R is of the form "(R1|R2)" where R1 and R2 are regular expressions 4) R is of the form "(R1*)" where R1 is a regular expression.
Regular expressions can be nested, and will always have two elements in the parenthesis. ('*' is an element, '|' is not; basically, there will always be pairwise evaluation) Additionally, '*' will always be the second element; '(*a)' is invalid.
The set of strings recognised by R are as follows: 1) If R is "a", then the set of strings recognised = {a} 2) If R is "b", then the set of strings recognised = {b} 3) if R is of the form "(R1R2)" then the set of strings recognised = all strings which can be obtained by a concatenation of strings s1 and s2 where s1 is recognised by R1 and s2 by R2. 4) if R is of the form "(R1|R2)" then the set of strings recognised = union of the set of strings recognised by R1 and R2. 5) If R is of the form "(R1*)" then the the strings recognised are the empty string and the concatenation of an arbitrary number of copies of any string recognised by R1.
Task : Given a regular expression and an integer L, count how many strings of length L are recognized by it. Input: The first line contains the number of test cases T. T test cases follow. Each test case contains a regular expression R and an integer L. Output: Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.

Monday, January 9, 2012

Backup Your Life , Before it Dies...

I am very delighted as I started writing my first blog article of 2012. Happy new year to one and all. I thought for a while on what is going to be the topic for this article, as I wanted it to be quite unique, non technical, informative to readers. So, there strikes a question which always haunted me... 

Is It Possible to Backup Life ?


Days, months, years are passing by as quick as 5 minutes snooze of morning alarm, which you never feel. Hundreds of people that we meet, hangouts with friends, events that we participate in, numerous social engagements, the places that we visit, images that we capture, sports that we play, seminar that we present, innovations that we make, heights that we achieve and the list just goes on.
But we tend to forget all these very quickly, people are lost in day-today engagements, an aggressive life style where things change very drastically.

I always thought, how good it will if I could remember or document all those things which I do everyday, and could exactly recount what I was doing on a particular day of the year when asked.. and the list just doesn't end here , it grows even further with many more wishes like,
  • Whom all I met in the years passed.
  • What problems I worked on.
  • What all the topics which grabbed my attention.
  • Which all the places that I have visited.
  • The sports that I played.
  • Images that I captured.
  • Parties that I attended. 
How can I backup all these information in a structured way ?
If I were thrown this question a couple of years back probably I would have had no answer. But now certainly we can address these questions by leveraging the power of web services. In the recent days web has evolved beyond our expectations, with could computing and easy access to internet one could reap the benefits of web services without any hassle.

Below is the brief description of how we can make use of free web services and applications to address all the issues mentioned above, and precisely " How can be backup our lives ".

People whom I met. 
Social networking sites like Twitter, Facebook, LinkedIn will fit the bill in addressing this concern. With the boom in social networking one can keep in touch his friends effortlessly. Now a days people from internet community are found at-least on one of the social networking site, and this is enough to keep in touch with the person of interest.

Building circles based on my profession and interests.
" Google Plus " is the answer. As most people say Google Plus is for geeks, being a networking site, G+ is heading in right direction in bringing like minded people from every corner of the world. And it  doesn't even expect that the participating members to be friend of each other.
Google Plus is a huge stream of free flowing information source which anyone can listen to. You just need to circle all the people, pages which you are interested in and they will keep you updated about latest technological innovations as you listen to their streams.

Articles which grabbed my interest.
A simple one word answer " Tweet " , tweet more, tweet all those articles which you found interesting. Unknowingly you are backing up all those articles of your interest and in future if you look back you end up having a well structured catalog of articles which you can refer back to.

Places that I have visited.
"Google Latitude" is the perfect application which you can use to keep record of all the places that you visit. Each time you visit a new place, mark it on Google latitude with the help of GPS, that's all. The records are saved in your Google account, ready to be referred back at any point in future.

Pictures that I have captured.
Online photo stores like Picasa, Flicker, Tumblr, will assist in keeping your pictures safe and lets you share your photographs with your friends, and get feedback on them. With the help of these applications you can let the world know that hidden artist within you. 

I want to keep my articles and notes safe for future reference.
Use " Evernote ", a quick note taking and documenting application which is platform and device agnostic, which can be used from anywhere and you are ensured that always you get the most updated data. No matter from whichever device you have edited the information it is all there synched on all the devices.

I want a Document repository which I could share with others.
" Dropbox " is the perfect application for you. Dropbox allows users to backup documents online which is ready to be extracted from anywhere and on any device. Dropbox also allows you to share some selected documents with your friends and hence helps in synchronizing between multiple people working on same documents.

Where can I backup my hobby projects.
"GitHub" a web hosting service for software projects. You can create your repository on this server and backup your code. You can also share repository with team members and it assists in combined efforts of a software development team.

And lastly....

I'm interested in knowing what is happening in others life
After all this is a basic instinct of human race. I don't need to mention the web service for this purpose, but this article would be incomplete if I don't mention it. Use " Facebook ", to be connected with people. That's all and the rest you only know.

With this, we have come to the end of this article. I hope following these would certainly help in backing up ones Social engagements, interests, views, skills, facts, desires, hopes, memories and what not. and hence you can " BACKUP YOUR LIFE".