Q. Merge Sort

ALGORITHM:-

1.  break  array  into  arr[low..mid]  and  arr[mid+1..high]  until  there  is  1  element  left
2.  merge  these  both  arrays

#include<stdio.h>

void merge(int* arr,int low,int mid,int high)
{
    int b[1000];int i_b=low;
        int i=low,j=mid+1;

while(1)
{
   {
        if(i>mid)
        {
                for(int k=j;k<=high;k++)
                b[i_b++]=arr[k];
             break;
        }
     
        if(j>high)
        {
                for(int k=i;k<=mid;k++)
                b[i_b++]=arr[k];
           break;  
        }
 
   }
     
        if(arr[i]>=arr[j])
        {
        b[i_b++]=arr[j];j++;  
        }
        else
        {
        b[i_b++]=arr[i];i++;
        }    
}
for(int k=low;k<=high;k++)
arr[k]=b[k];
}



void mergeSort(int* arr,int low,int high)
{
if(low==high)
return;
int mid=(low+high) /2;
mergeSort(arr,low,mid);
mergeSort(arr,mid+1,high);
merge(arr,low,mid,high);
}


int main()
{
        int arr[10]={2,3,1,7,4,8,5,6,10,9};
        //int arr[10]={10,9,8,7,6,5,4,3,2,1};
        mergeSort(arr,0,9);
        for(int k=0;k<10;k++)
        printf("%d\t",arr[k]);
        return 0;
}

Q. Minimum Number of Jumps to reach out of Array starting from first element

Here  at  position  a[i]  we  can  jump  from  a[i]  to  a[i+a[i]]  positions

INPUT:  {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};

OUTPUT:  2  i.e  1->3->9

METHOD  1  DP

DP  can  be  used  as  reaching  i  th  index  we  require

 a[i]=a[j]+j  where  j <= i

so  dp[i]=dp[j]+1;  where  i th  index  stores number  of  jumps  to  reach  a[i]

#include<stdio.h>
int max(int* dp,int n)
{
int max=0;
for(int i=0;i<n;i++)
if(dp[i]>max)
max=dp[i];
return max;
}
int main()
{
int n=11;
int arr[11]={1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
int dp[11]={0,0,0,0,0,0,0,0,0,0,0};
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(i==j+arr[j])
{dp[i]=dp[j]+1;break;} }
}
if(dp[n-1]!=0)
printf("%d",dp[n-1]);
else
{
printf("%d",max(dp,n)); }
}

Time  =O(n^2)
Space=O(n)  for  dp  array

METHOD  2  GREEDY

Here  we  can  also  use  greedy  approach  as  we  can  see  we  may  choose  max{j+a[j]}  as  our  next  move  i.e  we  can  reach  destination  as  easy  as  possible

#include<stdio.h>
int max(int* arr,int low, int high)
{
printf("%d   %d\n",low,high);
int max=0;
for(int i=low;i<=high;i++)
if(i+arr[i]>max)
max=arr[i]+i;
return max;
}
int main()
{
int n=11;
int arr[11]={1, 1, 2, 5, 1, 2, 2, 1, 1, 8, 9};
int jump=0;
for(int i=0;i<n;)
{
//printf("%d\t",i);
i=max(arr,i+1,i+arr[i]);
jump++;
if(i>11)
break;
}
printf("%d",jump+1);
}

Time=  O(n)

Please  suggest  any  updates.........

Q. N persons are standing in a circle and play a game which starts from 1. In this game we are passing each other baton and after count of D which ever person holds that baton is out from the game and then the game begins from the next person in the circle. Print the order in which the people gets out.

INPUT  N=5,  D=2;

OUTPUT:  2,4,1,5,3

First  2  gets  out  then  4  so  we  left  with  1  3  5
Game  starts  with  5  and  hence  1  gets  out  and  game  goes  like  that.........



Solution:-  We  are  initializing  an  array  with  size  N  with  a[i]=i;

Now  we  are  counting  (prevIndex+D)%length;  length--;  is  the  next  element  to  be  removed

length  is  updated  dynamically

And  the  element  removed  is  printed...

#include<stdio.h>

void remove(int*,int,int);

void remove(int *arr,int k,int n)
{
for(int i=k+1;i<n;i++)
    arr[i-1]=arr[i];
}


int main()
{
        int n=12;
        int d=2;
        int arr[n];
        int length=n;
        int v=0;
     
        for(int k=0;k<n;k++)
        arr[k]=k+1;  
     
     
        while(1)
        {
                if(length==1)
                break;
         
             if(v!=0)
                v=v+d-1;
                else
                v=v+d;
             
                if(v%length!=0 || v==0)
                v=v%length;
                else
                v=length;
     
     
        printf("%d\n",arr[v-1]);
     
        if(v!=0)
        remove(arr,v-1,length);
        else
        remove(arr,v,length);
     
        length--;
     
        if(v>length)
        v=0;
     
        }
        printf("%d",arr[0]);  
        return 0;
}

If  you  fell  asking  anything  please  tell  me  anytime....

Q. Basic fibonaci program using DP

This  is  the  first  program  for  understanding  DP

You  must  be  knowing  Fib(n)=Fib(n-1)+Fib(n-2)

Lets  see  the  function  calls  of  Fib(6)

Here  we  can  see  Fib(4)  is  called  two  times  and  same  goes  with  Fib(3)  and  other  function  calls.  So  we  can  reduce  our  complexity  by  using  arrays  for  storage....

Just  where  there  is  returning  condition i.e Fib(0)=0,,  we  make  Fib[0]=0

and  make  Fib[n]=Fib[n-1]+Fib[n-2]  we  can  avoid  unecessary  calls  to  functions  again  and  again.....

#include<stdio.h>
int main()
{
int n=12;
int fib[12];
fib[0]=0;
fib[1]=1;
for(int k=2;k<n;k++)
{
fib[k]=fib[k-1]+fib[k-2];
}
printf("%d",fib[n-1]);

Please  tell  me  for  any  other  updates in  this  article

Q. Find the maximum sum subarray such that no 2 elements are contiguous

INPUT  {5,4,10,40,50,35}
OUTPUT  5+40+35=80

This  thing  is  used  when  basically  we  are  getting  a  recursive  function  and  DP  helps  us  in  reducing  complexity.

We  can  see  here  F(j)={arr[j]+F(j-2)}  as  we  cant  have  consecutive  elements  so  we  take  sum  till   j-2

where  F(i)=  max  subarray  formed  till   the  ith  index  of  array

#include<stdio.h>

int main()
{
 int n=6;
 int arr[6] = {5,4, 10, 40, 50, 35};
 //int arr[5]={3,2,7,10};
 int dp[5];
 dp[0]=arr[0];
 dp[1]=arr[0]>=arr[1]?arr[0]:arr[1];

 for(int k=2;k<n;k++)
 {
 int sum=arr[k]+dp[k-2];
 dp[k]= sum>dp[k-1]?sum:dp[k-1];
 }
 printf("%d",dp[n-1]);
}

I  know  I  may  be  bad  at  explaining  things  so  please  tell  me  if  you  are  unable  to  understand  I  will  try  to  make  content  mare  explainable..

Also  please  tell  if  my  code  is  failing  at  some  point 

Q. Connect nodes of tree at same level with next pointer

Here  we  have  a  single  difference  in  structure  of  a  link  list  and  that  is  we  have  next  node  in  this  and  we  have  to  connect  the

Like  in  the  above  tree  we  need  to  connect

2->3
4->5->6
7->8

Here  is  the  working  code  below  for  this.  It  is  basically  a  level  order  traversal  only

#include<iostream.h>
#include<queue>
#include<vector>
using namespace std;
struct node
{
    int info;
    struct node* left;
    struct node* right;
    struct node* next;
};
node* newNode(int data)
{
    struct node* temp = new node;
    temp->info = data;
    temp->left = NULL;
    temp->right = NULL;
    temp->next=NULL;
  return (temp);
}
int breakCondition(vector<node*> temp)
{
for(int k=0;k<temp.size();k++)
{
node* temp1=temp.at(k);
if(temp1->left || temp1->right)
return 1;
}
return 0; }

int main()
{
struct node *n1 = newNode(1);
    n1->left        = newNode(2);
    n1->right       = newNode(3);
    n1->left->left  = newNode(4);
    n1->left->right = newNode(5);
    n1->right->left  = newNode(6);
    n1->left->right->left = newNode(7);
    n1->left->right->right = newNode(8);
 
    std::queue<node*> Q1;
    vector<node*> v;
    v.push_back(n1);
    Q1.push(n1);
 
 
while(1)
{
if(breakCondition(v)==0)
break;
v.clear();
    while(!Q1.empty())
    {
     node* temp=Q1.front();
   
     if(temp->left!=NULL)
     v.push_back(temp->left);
if(temp->right!=NULL)
     v.push_back(temp->right);
   
     Q1.pop();
   }
 
 
   for(int k=0;k<v.size();k++)
  {
node* temp2=v.at(k);
Q1.push(temp2);
cout<<temp2->info;   }
  cout<<endl;
    for(int k=0;k<v.size()-1;k++)
  {
node* temp=v.at(k);
node*temp1=v.at(k+1);
temp->next=temp1;    }
 
}
node*temp=n1->left->right->left;
temp=temp->next;
cout<<"Next  pointer  to  temp  is"<<"  "<<temp->info<<endl;
return 0;
}

Q. Reverse the group of k nodes in a link list

INPUT:  1->2>3->4->5->6->7->8     K=2

Then

OUTPUT:  1->0->3->2->5->4->7->6->8

METHOD  1

In  this  method we  are  maintaining  an  array  of  size  k  and  then  putting  first  value  at  index  k  and  second  at  k-1  and  so  on........

Then  we  are  putting  value  back  at  link  list..

Here  is  the  working  code  of  it  using  array.

http://ideone.com/pfo26l

Time  Complexity=  O(n)
Space  Complexity=O(k)

METHOD  2

 It  is  a  really  tricky  method  for  coding.  It  is  asked  to  code  many  times  in  interviews.  But  neglecting  this  question  is  not  a  good  option .One  must  practice  this  one  before.

Inplace  method  of  doing  this  question  and  link - link  swap  for  reversing..

http://ideone.com/oLMHyQ

Let  us  see  the  main  code  of  this.....

node* reverse(node* start,int k)
{

node *curr=start,*prev,*next,*end;
int i=0;
prev=end;
end=start;
if(curr==NULL)
return NULL;

while(i<k &&  curr!=NULL)

{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
i++;
}
end->next=reverse(curr,k);
return prev;
}