heap sort

#include<iostream.h>

#include<conio.h>

int a[]={6,5,3,1,8,7,2,4};

int n=sizeof(a)/sizeof(a[0]);

void heapify(int k)

{

      for(int i=1;i<=k;i++)

      {

            int val=a[i];

            int pos=i;

            int parpos=(i-1)/2;

            while(parpos>=0 && val>a[parpos])

            {

                  a[pos]=a[parpos];

                  a[parpos]=val;

                  pos=parpos;

                  parpos=(parpos-1)/2;

            }

      }

}

void heapsort()

{

      for(int i=n-1;i>=0;i--)

      {

            heapify(i);

            int temp=a[i];

            a[i]=a[0];

            a[0]=temp;

      }

}

void display()

{

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

            cout<<"  "<<a[i];

}

void main()

{

      clrscr();

      heapsort();

      display();

      getch();

}

merge sort

#include<iostream.h>

#include<conio.h>

int array[50];

int n;

void mergesort(int ,int,int);

void merge(int low,int high)

{

      int mid;

      if(low<high)

      {

            mid=(low+high)/2;

            merge(low,mid);

            merge(mid+1,high);

            mergesort(low,high,mid);

      }

      else

            return;

}

void mergesort(int low,int high,int mid)

{

      int i,j,k,c[50];

      i=low;

      j=mid+1;

      k=low;

      while((i<=mid) && (j<=high))

      {

            if(array[i]<array[j])

                  c[k++]=array[i++];

            else

                  c[k++]=array[j++];

      }

      while(i<=mid)

            c[k++]=array[i++];

      while(j<=high)

            c[k++]=array[j++];

      for(i=low;i<k;i++)

            array[i]=c[i];

}

void display()

{

      cout<<"\n\ncontent of array is :\n";

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

            cout<<"   "<<array[i];

}

void main()

{

      clrscr();

      cout<<"Number of elements :";

      cin>>n;

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

      {

            cout<<"\nEnter element "<<i+1<<" : ";

            cin>>array[i];

      }

      merge(0,n-1);

      display();

      getch();

}

quick sort

#include<iostream.h>

#include<conio.h>

int n;

int array[60];

int quick(int left,int right)

{

      int loc=left;

      while(1)

      {

            while(array[loc]<=array[right] && loc!=right)

                  right--;

            if(loc==right)

                  return loc;

            else

            {

                  int temp=array[right];

                  array[right]=array[loc];

                  array[loc]=temp;

                  loc=right;

            }

            while(array[loc]>=array[left] && loc!=left)

                  left++;

            if(loc==left)

                  return loc;

            else

            {

                  int temp=array[left];

                  array[left]=array[loc];

                  array[loc]=temp;

                  loc=left;

            }

      }

}

void quicksort()

{

      int lower[10],upper[10];

      int top=0,beg,end,loc;

      if(n>1)

      {

            lower[top]=0;

            upper[top]=n-1;

      }

      while(top!=-1)

      {

            beg=lower[top];

            end=upper[top];

            top--;

            loc=quick(beg,end);

            if(beg<loc-1)

            {

                  lower[++top]=beg;

                  upper[top]=loc-1;

            }

            if(loc+1<end)

            {

                  lower[++top]=loc+1;

                  upper[top]=end;

            }

      }

}

void display()

{

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

            cout<<"  "<<array[i];

}

void main()

{

      clrscr();

      cout<<"Number of elements : ";

      cin>>n;

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

      {

            cout<<"Enter element "<<i+1<<"  :  ";

            cin>>array[i];

      }

      quicksort();

      display();

      getch();

}

Find 2 elements in an array such that their sum is equal to a given number. o(nlogn)

#include<iostream.h>

#include<conio.h>

void main()

{

      clrscr();

      int n,val,i,j;

      int array[]={10,20,30,40,50,60,70,80};

      n=8;

      cout<<" \n\nEnter the value :";

      cin>>val;

      int flag=0;

      i=0,j=n-1;

      while(i<j)

      {

            if(array[i]+array[j]==val)

            {

                  cout<<"\n"<<array[i]<<" + "<<array[j]<<" = "<<val;

                  flag=1;

                  i++;

                  j--;

            }

            else if(array[i]+array[j]>val)

                  j--;

            else

                  i++;

      }

      if(flag==0)

                  cout<<"\nNo such elements";

      getch();

}

PROGRAMMING INTERVIEWS

All those who are preparing for amazon / google / microsoft or any other IT giants like these where there are hardcore programming rounds, must go through few of the most frequently asked and brain teasing programming problems.

I'll be sharing a lot of questions and will also provide solutions to these, but i will suggest you all to try solving the question on your own, come up with your own logic, own approach of solving the question because many a times in interviews solutions doesn't matter but the way you approach the problem sums it all for the interviewer.

"It's the journey and not the destination that matters". This quote goes perfectly with these organisations. You'll be asked to solve a problem within a time-complexity and this is the catch, they are not looking for brute force technique but they want you to come up with an algorithm of your's to solve the problem within the mentioned time complexity and for this you require a high aptitude and a very good understanding of the problem.

I'll suggest that you should try to work out the problem manually on a paper to gain a better understanding of the problem. Take a small subset of the problem and while working out the problem identify the special cases, which will really help you while coding the solution.

I'll list all the questions that i have collected from different websites at a single place, so that you guys don't have to hover from website to website to catch up all questions.