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;
}

Forming sum tree of a givn tree (nodes are to be replaced with the sum of values of their children)

INPUT:-

OUTPUT:-

Good  question  to  pratice  recursion  and  asked  in  many  interviews  to  check  the  concepts  of  recursion  and  trees.  

Here  is  a  C++  code  for  this

#include<iostream.h>

using namespace std;

struct node

{

    int info;

    struct node* left;

    struct node* right;

};

node* newNode(int data)

{

    struct node* temp = new node;

    temp->info = data;

    temp->left = NULL;

    temp->right = NULL;

  return (temp);

}

int sumTree(node* root)

{

if(root==NULL)

return 0;

int sum=root->info;

root->info=sumTree(root->left) + sumTree(root->right);

return root->info+sum;

}

void preorder(node* root)

{

if(root==NULL)

return;

cout<<root->info<<"        ";

preorder(root->left);

preorder(root->right);

}

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);

    preorder(n1);

    cout<<endl;

    sumTree(n1);

    preorder(n1);

    

return 0;

}

Diameter of a tree (longest leaf to leaf path)

I  do  not  know  what  was  GeeksforGeeks  algorithm  for  this  question.  I  did  not  get  a  bit  of  that.
But  this  is  my  code  which  has  passed  all  the  cases  from  interviewstreet.com.  You  can  yourself check   second  question  in   the  link  below

https://www.interviewstreet.com/recruit/test/start/sample


Here  is  my  code..  Hope  it  is  easily  understood

In  this  we  are  taking  that  both  the  leaves  have  common  source (which  may  be  root  or  any  other)
which  is  passed  into  the  function diameterOfTree()

Leaf  to  Leaf  path  from  that  node will  be  1+lh+rh

And  maximum  of  all  that  is  calculated

int maximum(int a,int b)
{
    if(a>=b)
        return a;
    else
        return b;
}  


int max=0;

int height(node* root)
{
    if(root!=NULL)
    {  
    int lh=height(root->left);
    int rh=height(root->right);
 
    return 1+maximum(lh,rh);
    }
    return 0;
}




int diameterOfTree(node * root)
{
    if(root!=NULL)
    {
    int temp=1+height(root->left)+height(root->right);
        if(temp>max)
            max=temp;
    diameterOfTree(root->left);
    diameterOfTree(root->right);
    }
    return max;
}

Q. Generate output array such that it contains product of all elements except itself without division operator

INPUT             { 5 ,4, 3, 2, 1 }

OUTPUT          {24,30,40,60,120}

as a[0]=(4*3*2*1)=24
    a[1]=(5*3*2*1)


In  this  we  can  maintain  two  arrays  lh[]  and  rh[]

where  lh[i]= a[0] * a[1]*........*a[i-1]

and  rh[i]= a[i+1] * a[i+2]*........*a[n]  where  n  is  the  last  index  of  array

Here  is    my    code

#include<stdio.h>
int main()
{
int arr[5]={5,4,3,2,1};
int lh[5];//  will  contain  the  product  of  all  elements to  the  left
int rh[5];//  will  contain  the  product  of  all  elements to  the  right
int prod=1;
for(int k=0;k<5;k++)
{
lh[k]=prod;
prod=prod*arr[k]; }
prod=1;
for(int k=4;k>=0;k--)
{
rh[k]=prod;
prod=prod*arr[k]; }
for(int k=0;k<5;k++)
arr[k]=lh[k]*rh[k];
for(int k=0;k<5;k++)
printf("%d\t",arr[k]);
return 0;

} 

Please  tell  me  if  any  optimizations  are  required..................

Q. Given a list of integers find out the biggest interval that has all the numbers in the given list

INPUT  1,8,4,6,3,2,7,11;

Possible  candidates  will  be  1,2,3,4  and  6,7,8  as  they  are  the  continous  elements  present  in  the  input  array

But  1,2,3,4  is  having  more  length  so  it  will  be  the  answer

OUTPUT  [1,4];

METHOD  1

Sort  all  elements  and  check for  the  biggest  interval  in  the  sorted  array

1.  After  using  merge  sort  ,  

     int length=1;//  length  will  be  our  answer

     int maxYet=1;

     for(int i=1 to n)

     {

      if(a[i]==a[i-1])

      {

       maxYet++;

     }

       else

       //resetset  maxYet  and  compare

        {

          if(maxYet>length)

           length=maxYet;

      

          maxYet=1;

        } 

      

     }

Time Complexity=O(n logn)
Space Complexity=O(1)

METHOD  2

It  really  took  time  to  think  that  one   

It  involves  hash...

1.  Scan  all the  elements  and  hash  in  2  hashmaps  (visited  and  present) all  elements.

2.  int  length=1,maxYet=1;

    visited[element]=0;

   present[element]=1;
3.  For  every  element  if  not  visited   , check  if  consecutive  predecessors  are  present  in  array  and  mark  them  as  visited

4.  Similarly  do  for  consecutive  successor  elements

5. Now  higher-lower  will  be  our  length,  if  that  is  maximum  than  previous  one  then  it  is  taken  as  result.

#include<iostream>
#include<map>
#include<string>

using namespace std;
typedef map<int,int> mapping;

int main() 
{
mapping visited;
mapping present;

int length=1,res1=-1,res2=-1;
int arr[10]={1,7,4,6,3,10,2,9,13,11};

for(int k=0;k<10;k++)
{
visited[arr[k]]=0;
present[arr[k]]=1;
}


for(int k=0;k<10;k++)
{
int element=arr[k];int lower=arr[k],higher=arr[k];

if(visited[element]==0)
{
while(present[element]==1)
{
lower=element;
visited[element]=1;
element--;
}

element=arr[k]+1;
while(present[element]==1)
{
higher=element;
visited[element]=1;
element++;
}

if((higher-lower)>length)
{
res1=lower;res2=higher;length=higher-lower;
}
}
}
if(res1==-1 && res2==-1)
printf("No consecutive element");
else
printf("%d %d",res1,res2);
return 0;

}

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

-

Q. Finding integer square root of an element N (we are doing here it by 3 methods)

METHOD  1 (Naive)

It  is  naive  method  which  is  in  your  mind  in  which  we  check  every  value  from  1  to n    square  its  value  to  check  it  equal  to  N

PseudoCode

for(int i=0 to N)

{

if(i*i==N)

print  i  is  the  square  root

if(i*i>N)

print  Square  root  is  not  integer

}

Time =O(n)

METHOD  2 (Newton Raphson)

It  is  Newton - Raphson  method  as  we  can  see  that  sum  of  N  odd  terns  result  into  N^2

It  says  that  the  N consecutive  odd  elements  add  upto  give  N^2  as  its  result  as  we  can  see

1+3=4(i.e  2^2)    [2  consecutive  odd  elements  add  upto  give  4 i.e  2^2]

1+3+5+7+9+11=36(i.e  6^2)   [6  consecutive  odd  elements  add  upto  give  36 i.e  6^6]

The  programmers  having  some  knowledge  of  Mathematics  will  work  that  out  also

#include<stdio.h>

int square(int);

int square(int a)

{

int sum=0;

for(int k=0;k<a;k++)

sum+=2*k+1;

return sum;

}

int main()

{

int N;

printf("Enter  the  value  of  N");

scanf("%d",&N);

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

{

if(square(k)==N)

{printf("%d is our answer",k);return 0;}

}

printf("No integer value is found");

return 0;

}

Time=O( sqrt(N) );

METHOD  3 (Binary  Search)

It  will  be  the  most  expected  answer  as  of  having  less  complexity  than  above

  low=0; high=N;

while

{

 mid=(low+high)/2;

if(mid*mid>N)

high=mid;

if(mid*mid==N)

done;

if(mid*mid<N)

low=mid;

if(low==high)

break;

}

print  no  result

Time=O(log n)

This  can  be  extended  for  finding  square  root  in  decimals  also

See  this  http://ideone.com/ePF12g  for  the  result

Please  tell  any  queries.......

Q. Find the maximum difference between two elements i and j a[i] -a[j] where j>i

Example:

{1,23,56,24,76,89,123,32,47,94}

a[i]=123  and  a[j]=32

answer  is  123 - 32= 91

(see  -122  will  not  be  answer  here  we  dont  have  to  calculate  absolute  one... )

METHOD 1

A  completely  naive  method  in  which  for  every  element  we  calculate  difference  with  the  left  out  elements  and  maintain  the  maximum  difference.  This  method  will  not  be  expected  in  interviews .

for(i=0 to n)

{

for(j=i to n)

result=compute a[i]-a[j]

if(result>maxYet)

maxYet=result;

}

#include<stdio.h>
int main()
{
int result=0;
int arr[10]={1,23,56,24,76,89,123,32,47,94};
int minNumber=arr[9];
int maxResult=0;
for(int k=9;k>=0;k--)
{
for(int k1=9;k1>=k;k1--)
{
int diff=arr[k]-arr[k1];
if(result<diff)
result=diff;
}
}
printf("%d",result);
return 0;
}

Space  Complexity=O(1)

Time   Complexity=O(n^2)

METHOD 2

One  scan  method  for  this   is  to  scan  the  elements  from  right  only  and  calculate 

result= a[i]-min(a[i+1....n])

maximum  of  result  is  our  answer

max=0;

for(j=n  to  0)

{

result= a[j]-min(a[j  to  n])

if(max<result)

result=max;

}

#include<stdio.h>
int main()
{
int arr[10]={1,23,56,24,76,89,123,32,47,94};
int minNumber=arr[9];
int maxResult=0;
for(int k=9;k>=0;k--)
{
if(minNumber>arr[k])
minNumber=arr[k];
int result=arr[k]-minNumber;
if(result>maxResult)
maxResult=result;
}
printf("%d",maxResult);
return 0;
}

Space  Complexity=O(1)

Time  Complexity=O(n)

Q. Spiral Traversal of a nxn matrix where n is odd..

Well  this  is  a  really  good  question  for  your  coding  practice. This  is asked  in  many  interviews  to  check  the  coding  abilities  of  the  candidiates

Lets  have  a  5x5  matrix  as  an  example


0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24



for  this  answer  should  be
0 1 2 3 4 9 14 19 24 23 22 21 20 15 10 5 6 7 8 13 18 17 16 11 12

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


#include<stdio.h>

int main()
{
int n=5;
int arr[n][n];
int top=0,bottom=n,left=0,right=n;//these  are  the  boundaries  of  the  matrix  while  traversing  spirally
int currX=0,currY=0;//these  are  the  locations  which  are  being  traversed

//arr  is  having  value  0 to 48  in  row  majority  order
for(int k=0;k<n;k++)
for(int k1=0;k1<n;k1++)
arr[k][k1]=n*k+k1;

// this is for printing matrix value
/*for(int k=0;k<n;k++)
{
for(int k1=0;k1<n;k1++)
printf("%d\t",arr[k][k1]);
printf("\n");
}*/


while((currX!=n/2)&&(currY!=n/2))
{
//printf("%d %d %d %d\n",left,right,top,bottom);
while(currX<right)
{printf("%d\t",arr[currY][currX]);currX++;}right--;currX--;currY++;top++;

while(currY<bottom)
{printf("%d\t",arr[currY][currX]);currY++;}bottom--;currY--;currX--;

while(currX>=left)
{printf("%d\t",arr[currY][currX]);currX--;}left++;currX++;currY--;

while(currY>=top)
{printf("%d\t",arr[currY][currX]);currY--;}currY++;currX++;
}
printf("%d",arr[n/2][n/2]);
return 0;
}

Q. Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers (one is missing and one is repeated)

INPUT               {2,1,3,3,5}  n=5
Missing  one  is  4  and  repeating  one  is  3


It  means  that  one  number  is  missing  and  other  is  repeating  twice  and  we  have  to  find  both  of  them..

METHOD  1

It  is  the  most  obvious  way  to  do  this  which  is  to  sort  them  first  and  then  we  may  be  easily  able to  find  the  remaining  ones...

Time Complexity=O(n logn),,for   merge  sort

Space Complexity=O(n), for  stack  used  in  merge  sort 

METHOD  2

Hash  the  above  elements  and  store  count  as their  values  and  we  may  easily  get  the  answer

METHOD 3

It  is  a  little  tricky  as  it  involves  two  equations  in  this

sum(n)=n(n+1)/2,,

product  of  n=n!

now in  our  given  array  we  will  be  having  sum  as  (sum+repeated-missed)

and  similarly  we  will  have  our  product  as  (product*repeated)/missed

And  hence  we   get  our  two  equations  to  be  solved

Q. Position all elements less than 0 before elements greater than 0

INPUT                     6, -1, -2, 2, -4, 3, 5
OUTPUT                 -4, -2,-1  2 ,6 ,3 ,5

This  is  a  very  common  question  asked  in  which  can  be  of  form  arranging  all  even  numbers  before than  odd  ones  or  keeping  all  0  values  before  1 etc....  And  they  always  expect  you  to  solve  in  one  scan  and  in  place...

METHOD 1

In  this  we  take  another  array  of  same  size  and  first  push  all  the  negative  elements  and  then  in  second  scan  er  push  all  positive  elements..

Time  Complexity= O(n)

Space COmplexity=O(n)

METHOD 2

We  take  two  pointers  ptr1  and  ptr2.

ptr1  points  to  first  occurence  of  positive  elements,,

and  ptr2  searches  the  negative  number  to  the  right  of  ptr1  if  we  do  not  find  any  -ve  number  we  break...

else  we  we  swap  them  and  find  our  new  ptr1  which  is  obviously  greater  than  the  previous  value

#include<stdio.h>
void swap(int*,int,int);
void swap(int *arr,int ptr1,int ptr2)
{
int temp=arr[ptr1];
arr[ptr1]=arr[ptr2];
arr[ptr2]=temp; }

int main()
{
int bbreak=true;
int arr[7]={6, -1, -2, 2, -4, 3, 5};
int ptr1=-1,ptr2=-1;
//ptr1 maintains  the  first  +ve  element
while(1)
{
for(int k=ptr1;k<7;k++)
if(arr[k]>0)
{ptr1=k;break;}
for(int k=ptr1;k<7;k++)
{
if(arr[k]<0)
{swap(arr,ptr1,k);bbreak=false;}
}
if(bbreak==true)
break;
bbreak=true;
}
for(int k=0;k<7;k++)
printf("%d\t",arr[k]);
}

Q. Generate the next pallindrome number from a given 5 digit number

e.g
INPUT          36067

OUTUT        36163

METHOD

This  question  can  be  generalized  to  any  odd  number  digit  and  is  very  easy  and  mathematical  and  a  good  coding  question  too..

Well  I  am  not  able  to  find  any  other  method  for  this  question.

Take  the  number  in  an  array.....

int a[]=| 3 | 6 | 0 | 6 | 7 |

int  mid=a[2]=0

well  now  we  have  to  check  if  reverse  of  a[0..1]i.e  63  and  a[3...4]i.e  67,,

which  of  them  is  larger.. in  this  case  67

if  a[3...4]  is  larger,,  mid++;  And  our  example  belongs  to  this  case  so  0  becomes  1

else do  nothing...

now  just  reverse  the  a[0..1]  and  put  in  place  of  a[3...4]....  to  get  36163....

#include<stdio.h>

int main()

{

int n=36967;

int temp=n;

int mid=2;

int arr[5];

for(int k=4;k>=0;k--)

{

arr[k]=temp%10;

temp=temp/10;

}

//now compare  mid-1 and  mid+1  and  so  on......

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

{

if(arr[mid-k]>arr[mid+k])

break;

else if(arr[mid+k]>arr[mid-k])

{

if(arr[mid]!=9)

arr[mid]++;

else

{arr[mid]=0;arr[mid-1]++;}

break;

}

else

continue;

}

     //  now  reverse  1st  part  and  2nd  part

     

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

     {

      arr[mid+k]=arr[mid-k];

     }

for(int k=0;k<5;k++)

printf("%d",arr[k]);

return 0;

}

 Hope  you  understood  everything..  And  please  tell  me  if  you  find  any  test  case  not  working
Any  suggestions  are  welcomed..