When we store time stamp in database the column can be of type DATE TIME YEAR TO SECOND .

It Will contain day of month, month, year, time in seconds. But usually the scenarios that we Will be handling Will be pull all the data that happened this year or pull all the data that happened on particular date

on these scenarios we need to extract the columns from time stamp data.

here is the list of keywords

Day
Month
Year
Date

select DAY(activity_date) from table .

select MONTH(activity_date) from table.

select YEAR(activity_date) from table.

select DATE(activity_date) from table

say the timestamp is
2014-03-05 13:17:40

queries will return

5
3
2014
03/05/2014

In my past post , i explained the insertion sort with c++ code

http://shrinathsuccess.wordpress.com/2014/03/09/insertion-sort-c/

The major overhead in the insertion sort algorithm is swapping. For each element we are performing j-i swaps if the sequence is in descending order. Swaps are much costlier and we also need a new variable involved for swapping. If we could reduce the number of swapping then we will hit with the better performance.


#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
        cout << "Enter number of elements" << endl;

        int n,i,j;
        cin >> n;
        int a[n];
        int c = 0;
        srand(time(NULL));
        for(i=n; i>0 ; i--)
        {
                a[c] = i;
                c++;
        }
        cout << "Array Before Sorting" << endl;
          for(int i=0 ; i<5; i++)
          cout << a[i] << endl;
        for(i=1 ; i<n ; i++)
        {
                int key = a[i];

                for(j=i ; j>0 ; j--)
                {
                        if(a[j-1] > key)
                        {
                                a[j] = a[j-1];
                        }
                }
                a[j] = key;
        }

        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

TRIAL :

5 4 3 2 1

i = 1
key = 4
j = 1 , 1> 0

if(a[0] > key) => if(5 > 4)
a[1] = a[0] => 5 5 3 2 1

j=0 ; 0>0 – false
end of inner for loop
a[0] = key => 4 5 3 2 1
i=2
key = 3
j = 2

i = 2
key = 3
j = 2 ; 2 > 0
if(a[1] > key) => if(5 > 3)
a[2] = a[1] => 4 5 5 2 1

j=1 ; 1>0
if(a[0] > key) => if(4 > 3)
a[1] = a[0] => 4 4 5 2 1

j=0 ; j>0 – false
a[0] = 3 => 3 4 5 2 1

and the loop goes on like this ….

Instead of swapping the elements we perform assignment operation and at the end of the loop we assign the key back to the right place.

Special thanks to Nithin for pointing this out – https://www.facebook.com/nithin.kalathingal.5

WHAT IS LINKED LIST :

Linked list is a data structure which contains a set of elements linked to its successor.

WHERE TO USE LINKED LIST :

When there is a need of lot of insertions and deletions , linked list is preferred over Array .

One simple example is this : Say we have array of 1000 numbers . 2 to 1001 . Now we need to insert 1 at the beginning of the array. Its not so simple, we need to shift all the numbers from 2 to 1001 one step right for inserting one element at the beginning.

Linked list over comes this problem. Just allocate memory and play with pointers to give connections. 1 will be inserted at the beginning.

WHERE NOT TO USE LINKED LIST :

There are certain scenarios where in we need more number of searches than insert and delete. On such occasion arrray gives us a better result.

HOW TO IMPLEMENT LINKED LIST :

In this post we will be discussing 12 basic set of items on linked list

1. Structure of Linked List

2. Creating One node Linked List

3. Creating 3 Node Linked List

4. Creating N Node linked List

5. Inserting a node at front of linked list

6. Inserting a node at end of linked list

7. Inserting a node at N point of linked list

8. Deleting first element from list

9. Deleting last element from list

10. Deleting random element from list

11. Searching linked list

12. Copying Linked list

STRUCTURE OF LINKED LIST

                       Structure Of Linked List

A linked list contains data element along with the pointer which points to the next element.

struct node
{
     int data;
     struct node* next;
};

Creating One node Linked List:

                                         Single Node Linked List

Lets create a simple one node linked list . For creating a node , we need to follow three steps.

  1. Create a new node pointer
  2. Allocate memory and insert element
  3. Point the pointer to appropriate position
#include  // for cout
#include  // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);

int main()
{
        // create head pointer
        struct node* head = NULL;

        // allocate memory to it
        head = (struct node*) malloc(sizeof(struct node));

        // insert the data
        head->data = 1;

        // point the next pointer
        head->next = NULL;

        // printing the list
        print_ll(head);
        return 0;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

Output of single node linked list

CREATING 3 NODE LINKED LIST

                                    three_node_ll

Now, we know the size of linked list. So, lets create a function that will build 3 nodes in a linked list.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* three_node_ll();

int main()
{
        // call the function to create the list
        struct node* head = three_node_ll();
        // printing the list
        print_ll(head);
        return 0;
}

struct node* three_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;
        struct node* third = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));
        third = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 1;
        head->next = second;

        second->data = 2;
        second->next = third;

        third->data = 3;
        third->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

three_node_output

CREATING N NODE LINKED LIST

In the previous case, we know the definite size of linked list . But , now we need to build a list based on the input given by the user. Hence , we need to write a generic function which will insert the numbers into list dynamically.It is easy to push elements at the front of the list . It comprises of 3 steps.

  1. Allocate memory for the new node and insert data into it.
  2. Point the next pointer to old head
  3. Change head to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
void n_node_ll(struct node*&,int);
int num_of_nodes;

int main()
{
        cout << "Enter number of nodes to be created " << endl;
        cin >> num_of_nodes;
        struct node* head = NULL;
        // call the function to create the list
        for(int i=0 ; i<num_of_nodes; i++)
        {
                n_node_ll(head,i+1);
        }
        // printing the list
        print_ll(head);
        return 0;
}

void n_node_ll(struct node*& head, int d)
{
        // allocate memory and insert data
        struct node* newNode = (struct node*) malloc(sizeof(struct node));
        newNode->data = d;
        // point next pointer to old head
        newNode->next = head;
        // point head to new node
        head = newNode;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

INSERTING NODE AT FRONT OF LINKED LIST

n_node_ll

Say, we have linked list with 2 elements . 4 and 3 . Now we need to push 5 into the list at the front .

As explained in the previous code , it will be done with same 3 steps.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_front(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();
        // inserting number 5 at the front
        insert_at_front(head,5);
        // printing the list
        print_ll(head);
        return 0;
}

void insert_at_front(struct node*& head,int d)
{
        struct node* current = head;

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to old head
        newNode->next = head;

        // change head of the list to new node
        head = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 4;
        head->next = second;

        second->data = 3;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

insert_at_front

INSERTING A NODE AT END OF THE LIST

insert_at_end

For adding the node at the tail end we need to follow these steps

  1. Iterate through the list and find the point the last element in the list
  2. Create new node and insert data to it
  3. Point the next pointer of new node to null since it is going to be the last element
  4. Link the old last element pointer to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_end(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();

        // inserting number 3 at the end
        insert_at_end(head,3);

        // printing the list
        print_ll(head);
        return 0;
}
void insert_at_end(struct node*& head,int d)
{
        struct node* current = head;
        while(current->next != NULL)
        {
                current = current->next;
        }

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to null since its the last element
        newNode->next = NULL;

        // change head of the list to new node
        current->next = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 5;
        head->next = second;

        second->data = 4;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

output_insert_at_end

 

 

 

 

WHAT IS INSERTION SORT :

Insertion sort is a sorting algorithm which sorts the input data by putting elements into the sorted array one at a time .

It compares the next element in the array and puts it in the right place .

                                   Insertion Sort Graph


WHY INSERTION SORT :

When there are couple of sorting algorithms available why should i hit insertion sort ???

When the number of elements to be sorted is much lower , insertion sort gives us a very good result compared to others. Hence use it when the data set is low.

HOW INSERTION SORT WORKS :

Lets take an input tape with 5 elements in descending order.

5 4 3 2 1

4 5 3 2 1

3 4 5 2 1

2 3 4 5 1

1 2 3 4 5

On each iteration , it takes one element at a time and compares with the next element and places it in the right position.

First Iteration we take 4 as Key element . compare it with 5 . Since 4 is lesser we swap 4 and 5.

Second Iteration we take 3 as Key element . compare it with 5. 3 is lesser than 5 . Swap it . Yes, 3 is lesser than 4 also . Hence continue the swap until you place the element in the right place.

CODE FOR INSERTION SORT :


#include <iostream>
using namespace std;
void swap(int &a, int &b);

int main()
{
        // initializing the variables
        int a[10000];
        int c = 0;
        int n;

        // insert elements in descending order
        cin >> n;
        for(int i=n ; i>0; i--)
        {
        a[c] = i;
        c++;
        }

        // print the array before sorting
        cout << "Array Before Sorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;

        // insertion sort logic starts here
        for(int i=0 ; i<n-1; i++)
        {
                int key = a[i+1];
                int pos = i+1;
                for(int j=i; j>=0 ;j--)
                {
                        if(a[pos] < a[j])
                        {
                                swap(a[pos],a[j]);
                                pos--;
                        }
                }
        }
        // insertion sort logic ends here. Printing the array after sort.
        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

void swap(int &a, int &b)
{
        int t;
        t = a;
        a = b;
        b = t;

}

EXPLANATION :

for(int i=0 ; i<n-1; i++)

Each time we need to pick an element and put it in the right place. Hence we need a loop that runs through an array.

int key = a[i+1];
int pos = i+1;

On each iteration we choose one element as key and place it in the right place.
Hence , we are choosing the element which is in i+1 place as key and noting down its position in variable pos.

for(int j=i; j>=0 ;j–)

This innner for loop helps to compare the previous elements . we need to check till the first element and place the key element at the right place.

if(a[pos] < a[j])
{
swap(a[pos],a[j]);
pos–;
}

This condition checks with the previous element . If it is greater then it swaps the element .

TRIAL

Lets run this program for 5 elements .

Now input tape contains 5 4 3 2 1

First Iteration :

i=0 , key = 4, pos = 1
j=0 , 0>=0 is true hence
if(4<5) swap(4,5); pos– => pos = 0
Now, input tape contains : 4 5 3 2 1

Second Iteration:

i=1, 1<5, key = 3 and pos = 2 j=1, 1>=0
if(3<5) – true swap(3,5); Now input tape contains 4 3 5 2 1 pos — => pos =1

j– => j=0
j=0; 0>=0
if(3 < 4) – true swap(3,4) pos– = > pos = 0
Now input tape contains 3 4 5 2 1

Simillary loop goes on sorting .

BEST , WORST AND AVERAGE CASES

The program given above is for worst case . since the elements are in descending order . In this case, we need to compare all the elements with 2 for loops . The time complexity will be quadratic

For Best case scenario put the elements in the sorted order.

 for(int i=0 ; i<5; i++)
        a[i] = i+1;

Eventhough the elements are in the sorted order, the outer for loop will be running for n comparisons. Hence the best case is O(N);

AVERAGE CASE :

Generate random numbers and insert it into array .

#include <stdlib.h>
 srand(time(NULL));
         for(int i=0 ; i<5; i++)
        {
                a[i] = rand() % 10 + 1;
        }

Even in this case, the time complexity goes quadratic.
Hence the insertion sort is suitable only for the nearly sorted low data elements.
Below table shows the best worst and average case analysis of the program.

N Best Worst Average
1024 0.004 0.008 0.008
2048 0.016 0.032 0.02
4096 0.048 0.116 0.084
8192 0.164 0.468 0.312
16384 0.62 1.92 1.248
32768 2.47 7.704 4.94
65536 9.8 30.372 19.876
131072 39.428 125.43 83.756

Sql Fundas

Posted: February 25, 2014 in Database
Tags: , , ,

sometimes we spend very hard time by using some weird inner joins, group by clauses and nested queries for retrieving set of data from our database.

Thumb rule : when finding the rows that you want is moving very hard , then try eliminating rows that you don’t want to be there.

one simple delete statement can do an awesome job that a group by and complex sub queries does.

so , always keep in mind that they are two approaches for getting the data.

1. finding what you want
2. eliminating what you don’t want

Vi Editor Shortcuts

Posted: February 12, 2014 in Linux
Tags: , , , , ,

As we are aware, VI editor works in two mode . One is the Command mode which runs when we press Escape button and give commands and the other one is the insert mode which runs when we press i and type something up.

For a single window option we can always press : and type our command to be executed. One common command is :se nu. Which is the set line number commmand . But, once you quit the window and come back . It will be gone forever.

For making the changes permanent we need to put the commands in .vimrc file. Just type cd to move on to your home folder and open the file .vimrc .

$cd
$vi .vimrc
set number

We can also set abbreviations in vimrc file. Some of the frequently used words can be set here.

For example : select * from

When writing queries we will be using select * from quite often . Hence just set the abbreviation in vimrc file as below

iab sel select * from

Once you type sel and hit a space , vi will replace it to select * from .

vimrc file will be invoked when the terminal is loaded. For the effects to be applied on the same terminal where we changed vimrc we need to give the source command

source .vimrc

Or we can just close the existing terminal and open a new one.

Setting the size of an Array

Posted: February 7, 2014 in Uncategorized

we need to be very careful while setting the size of an array . Especially, then we use those variables in looping and conditions.

Let us see one example where we are creating a char array and reading the files based on the char array value.

char param[200];
// get input values
while(param.eof())
{
// do some stuff
}

Due to some chage the in param value we have more than 10 fileds to be added in param . even if we are adding 10 entries to param the loop will end up in the infitie execution.

This is because the value in the char arr can store only upto 200 characters. Since we added some more values to param , the size of the param will cross more than 200 . Bcoz of that param.eof will never get matched and our application will be in running in infite loop.

Hence, we need to be careful while allocation memory to a char variable