Tuesday, September 24, 2013

How to find median in order of log n ?

Median in an infinite series of integers

Solution: Use 2 heaps: One MaxHeap and one MinHeap.

1) MaxHeap contains the smallest half of the received integers
2) MinHeap contains the largest half of the received integers

The integers in MaxHeap are always less than or equal to the integers in MinHeap. Also, the number of elements in MaxHeap is either equal to or 1 more than the number of elements in the MinHeap.

In the stream if we get 2n elements (at any point of time), MaxHeap and MinHeap will both contain equal number of elements (in this case, n elements in each heap).

Otherwise, if we have received 2n+1 elements, MaxHeap will contain n+1 and MinHeap n.

Let us find the Median: If we have 2n+1 elements (odd), the Median of received elements will be the largest element in the MaxHeap (nothing but the root of MaxHeap). Otherwise, the Median of received elements will be the average of largest element in the MaxHeap (nothing but the root of MaxHeap) and
minimum element in the MinHeap (nothing but the root of MinHeap). This can be calculated in O(1).

Inserting an element in heaps can be done O(logn). Note that, any heap containing n+1 elements might need one delete operation (and insertion to other heap) as well.

Total Time Complexity: O(logn).

Suppose we have sequence like : 1,9,2,0 then construction of heaps:

Insert 1: Insert to MaxHeap.

MaxHeap: {1}, MinHeap:{}

Insert 9: Insert to MinHeap. Since 9 is greater that 1 and MinHeap maintains the maximum elements.
MaxHeap: {1}, MinHeap:{9}


Insert 2: Insert MinHeap. Since 2 is less than all elements of MinHeap.
MaxHeap: {1,2}, MinHeap:{9}

Insert 0: Since MaxHeap already contains more than half; we have to delete the max element from MaxHeap and insert it to MinHeap. So, we have to remove 2 and insert into MinHeap. With that it becomes:
MaxHeap: {1}, MinHeap:{2,9}
Now, insert 0 to MaxHeap.


Via Narasimha Karumanchi Sir :

Saturday, September 7, 2013

Monday, September 2, 2013

stack programme using structure in C

#include<stdio.h>
#include<stdlib.h>
#define structsize 10
struct stack
{
    int top;
    int item[structsize];
};
void push(struct stack *ps)
{
    int element;
    printf("\npush an element:");
    scanf("%d",&element);
    if(ps->top==(structsize-1)){

    printf("overflow\n");
    exit(0);
    }
    else
    {
       
    ps->item[++ps->top]=element;

    }

}
void pop(struct stack *ps)
{
    int element;
    if(ps->top==-1){
    printf("underflow flow\n");
    exit(0);   
    }
    else
    {
       
    element=ps->item[ps->top];
    ps->top--;
    printf("\npoped element is :%d",element);
    }

}
void display(struct stack *ps)
{
    int i;
    printf("\ncurrent stack is:\n");
    for(i=0;i<=(ps->top);i++)
    {
        printf("\n %d",ps->item[i]);
    }
}
int main()
{
int arr[50],ch;
struct stack s;
s.top=-1;
while(1)
{
printf("\n\nEnter \n1: push\n2:pop\n3:print stack \n4:exit \n\n enter choice:");
scanf("%d",&ch);
    switch(ch)
    {
        case 1:push(&s);
            break;
        case 2:pop(&s);
            break;
        case 3:display(&s);
            break;
        default:exit(0);
    }

}

return 0;
}

Sunday, September 1, 2013

How to find execution time of program in C??

We always eager to know that how much time my program takes to give me output. As a good programmer you always worry about the time complexity. If you print your execution time along with output then you can check your execution time for different test cases. It's really exiting.


#include<stdio.h>
#include<time.h>
int main()
{
clock_t begin, end;
begin = clock();
double time_spent;

/*
     write your code
*/

end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("\n execution time for sorting: %f seconds ",time_spent);

return 0;

}