CareerCup

it be 8 byte bcoz 4 bytes will be reserved base version and 4 for derived

whatever data type either it private public protected.

i think they looking virtual copy constructor 
concept how u will implement it.
this is well known problem

For this abstract class will declare a pure virtual clone method and all derived class will inherit it

class Base
{
       public:
       virtual Base* clone() = 0; //polymorphic nature
};
class Derived1 : public Base
{
       public:
      Base* clone()
     {
          return new Derived1(*this);
     }
};

class Derived2 : public Base
{
       public:
       Base* clone()
       {
             return new Derived2(*this);
       }
};

int main()
{
       Base* p = new Derived1();
       Base* q = new Derived2();

       vector<Base*> v;
       v.push_back(p);
       v.push_back(q);

//Now suppose u need to clone this vector object

       vector<Base*> vc;

       for_each(Base* x : v)
       vc.push_back(x->clone());

}

Hi Peter i updated my code ya thanks ofr pointing the bug in my code i fixed it and now i work fine it think

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;


int main()
{

  //const char* str = "################################*#";
  const char* str = "###########**#****######";

  int s = strlen(str);

  //sum used to know where the same sum last time seen at what index
  int* sum = new int[2*s+1];
  for(int i = 0; i < 2*s+1; i++)
  {
       sum[i] = INT_MIN;//mean it seen never earlier
  }

  int max = 0;
  int sMax = -1;
  int eMax = -1;

  int offset = s;
  //
  int sumUpto = 0;
  sum[offset] = -1;

  sumUpto = (str[0] == '*' ? 1 : -1);
  sum[sumUpto+offset] = 0;



  for(int i = 1; i < s; i++)
  {
      sumUpto = sumUpto + (str[i] == '*' ? 1 : -1);

      cout<<sumUpto<<" ";

      if(sum[sumUpto + offset] == INT_MIN)
      {
           sum[sumUpto+offset] = i;
      }
      else
      {
          int indexLastSeen = sum[sumUpto+offset];//the same sumUpto first time seen what index
          if((i-indexLastSeen) > max)
          {
               max = (i-indexLastSeen);
               sMax = indexLastSeen +1;
               eMax = i;
          }
      }//else
  }//forloop

  cout<<max<<"  "<<"Start Index = "<<sMax<<"  "<<"End Index = "<<eMax<<endl;

  for(int p = sMax; p <= eMax; p++)cout<<str[p];
  return 0;
}

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;


int main()
{

  const char* str = "****##**#**##";

  int s = strlen(str);

  //sum used to know where the same sum last time seen at what index
  int* sum = new int[2*s+1];
  for(int i = 0; i < 2*s+1; i++)
  {
       sum[i] = INT_MIN;//mean it seen never earlier
  }

  int max = 0;
  int sMax = -1;
  int eMax = -1;

  //
  int sumUpto = 0;
  sum[0] = -1;

  sumUpto = (str[0] == '*' ? 1 : -1);
  sum[sumUpto] = 0;

  for(int i = 1; i < s; i++)
  {
      sumUpto = sumUpto + (str[i] == '*' ? 1 : -1);

      if(sum[sumUpto] == INT_MIN)
      {
           sum[sumUpto] = i;
      }
      else
      {
          int indexLastSeen = sum[sumUpto];//the same sumUpto first time seen what index
          if((i-indexLastSeen) > max)
          {
               max = (i-indexLastSeen);
               sMax = indexLastSeen +1;
               eMax = i;
          }
      }//else
  }//forloop

  cout<<max<<"  "<<"Start Index = "<<sMax<<"  "<<"End Index = "<<eMax;
  return 0;
}

i think some more clarification need for this

    any point to any point looks impossible to cover all and reach
   
   if its a square matrix and souce is one corner and target is other diagonal corner 
   we can solve it easily....

Programme 1 No error
      Programme 2 Compile time error bocz B is inherited from A and A's constructor is private.

i think i agree your appraoch is it not good if we keep a counter at each node that how many element r in left of this and how many r on right of this ...in that case i think lookup is more faster and whole tree inorder we not need to do ......

but u see if we use a tree based solution we need extra space O(n) i think nobody will agree to provide this much space......can u think in terms of min heap max heap......

i code this problem using max heap min heap but my solution was not giving correct result.....

Can u code max heap min heap logic......i tried it but it not give me correct results....

There will be a compile time error if we inherit a class B from A and class A have constructor private....its not matter we creating an object or not...
so programme 1 give no error and programme2 give compile time error...

I think based on sum and quantity u can get mean not median.

Suppose input is 13, 18, 13, 14, 13, 16, 14, 21, 13
Then find out median sort it   13, 13, 13, 13, 14, 14, 16, 18, 21

Now if i see  13, 13, 13, 13, =< 14, >=14, 16, 18, 21 so here median is 14 bcoz here 4 elements are smaller or equal to 14 and exactly 4 element higher than this

Correct me if i am wrong...

my idea for this is

we have to insert data with respect to each field

Like name id and roll

name-->id,roll
id--->name,roll
roll--->name,id

its use duplicate space  but it will fullfill this demand

//Check my code i write Combinations function two ways use anyone
//My code is tested and compiled
#include<iostream>

using namespace std;



void PrintCombinations_other(char arr[],int i, int n, char result[], int j, int r)
{
   if(r == 0)
   {
      result[j] = '\0';
      cout<<result<<endl;
      return;
   }

   if(i + r -1 >=  n)
   {
      return;
   }

   for(int x = i; x + r - 1 < n; x++)
   {
      result[j] = arr[x];
      PrintCombinations_other(arr,x+1,n,result,j+1,r-1);

      while(arr[x] == arr[x+1])x++;
   }

}

void PrintCombinations(char arr[],int i, int n, char result[], int j, int r)
{
  

   if(j == r)
   {
      result[r] = '\0';
      cout<<result<<endl;
      return;
   }

   if(i == n)
   {
      return;
   }

   //include ith char or not include it 

   result[j] = arr[i];
   PrintCombinations(arr,i+1,n,result,j+1,r);

   //handle duplicates
   while(arr[i] == arr[i+1])
   i++;

   //do not include ith char
   PrintCombinations(arr,i+1,n,result,j,r);
}

void PrintAllLenStrings(char arr[])
{

  int len = strlen(arr);

  char* result = new char[len+1];

  for(int i = len; i >= 1; --i)
  {
     PrintCombinations_other(arr,0,len,result,0,i);
  }
}

int main()
{
   char arr[] = "abcd";
   PrintAllLenStrings(arr);
   return 0;
}

//Check there exists a pair whose sum is equal to rest of elements of array
//Duplicate elements can be there

#include<iostream>

using namespace std;


void swap(int &i, int &j)
{
   int temp = i;
   i = j;
   j = temp;
}
int partition(int arr[], int low, int high)
{
  int i = low;
  int j = high;
  j--;

  int p = arr[high];

  while(i < j)
  {
      if(arr[i] <= p)
      {
         i++;
      }
      else if(arr[j] > p)
      {
         j--;
      }
      else
      {
         swap(arr[i],arr[j]);
         i++;
         j--;
      }
  }

  if(arr[i] == p)
  {
     return i;
  }
  else if(arr[i] > p)
  {
      swap(arr[i],arr[high]);
      return i;
  }
  else
  {
      swap(arr[i+1],arr[high]);
      return i+1;
  }
}

void q_sort(int arr[], int low, int high)
{
   if(low < high)
   {
       int p = partition(arr,low,high);
       q_sort(arr,low,p-1);
       q_sort(arr,p+1,high);
   }
}

//This will return true if there exists a pair whose sum is equal to
//sum of all other elements

bool isExistsPair(int arr[], int n)
{
    int sum = 0;
    
    for(int i = 0; i < n; i++)
    {
        sum+=arr[i];
    }

    if(sum%2 != 0) return false;

    q_sort(arr,0,n-1);

    int k = sum/2;
 
    int i = 0; 
    int j = n-1;

    while(i < j)
    {
        if(arr[i] + arr[j] == k)
        {
            cout<<arr[i]<<"  "<<arr[j]<<endl;
            return true;
        }
        else if(arr[i] + arr[j] < k)
        {
           i++;
        }
        else
        {
          j--;
        }
    }

    return false;
}

int main()
{
   int arr[] = {1,8,3,20,4,4,2};

   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<isExistsPair(arr,n);
   return 0;
}

Wrong solution i am sure it not give correct result
    abcebcdf
    abbcdx
    here lcs is bcd only and your solution not give 3 length

This is not recursion and my question is specific to recursion.......

HardCode plz check your code on some samples i am sure u will understand your problem what mistake u doing....this question asked to that mistake bcoz many people do it.....

abcdefba for this sample i think your code will return 4 but here only 1 len palindrome strings......check your code against some samples

if we do n&(n-1) then rightmost set bit will reset so we will use this logic to count no of 1's

 int count = 0;

while(num != 0)
{
  count++;
  num = num & (num-1);
}

return count

i think first while loop is not doing right job

it should be like

while(i < a1.len && j < a2.len)
{
     if(a1[i] < a2[j]) 
    {
       a3[k] = a1[i];
       i++;
    }
   else if(a1[i] > a2[j])
   {
       a3[k] = a2[j];
       j++;
   }
  else
  {
      a3[k] = a1[i];
      i++;
      j++;
  }
  k++;
}

#include<iostream>

using namespace std;


int Max(int i, int j)
{
   return i > j ? i : j;
}

int MaxSumPath(int arr1[],int arr2[], int m, int n)
{
    int i = 0;
    int j = 0;

    int max_sum = 0;

    int sum1 = 0;
    int sum2 = 0;

    while(i < m && j < n)
    {
        if(arr1[i] < arr2[j])
        {
           sum1 +=arr1[i];
           i++;
        }
        else if(arr1[i] > arr2[j])
        {
           sum2 +=arr2[j];
           j++;
        }
        else
        {
           max_sum = Max(sum1,sum2) + max_sum;
           sum1 = 0;
           sum2 = 0;
           while(i < m &&  j < n && arr1[i] == arr2[j])
           {
                max_sum = max_sum + arr1[i];
                i++;
                j++;
           }
        }
    }

    while(i < m)
    {
       sum1  = sum1 + arr1[i];
       i++;
    }

    while(j < n)
    {
       sum2 = sum2 + arr2[j];
       j++;
    }

    max_sum = max_sum + Max(sum1,sum2);
    return max_sum;
}

int main()
{

   int arr1[] = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62}; 
   int arr2[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57,100};
   int sum = MaxSumPath(arr1,arr2,13,11);
   cout<<sum;
   return 0;
}

i not know what exact mean of Predecessor but i think it should be any node that come before a node in in order travesal all are Predecessor

6
      / \
    2   3

i think for 3 there are two Predecessor  2 & 3 bcoz both come before 3 in in order travesal...

plz correct me if i am wrong

#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
  int data;
  Node *left;
  Node *right;
  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {

  }
};

void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else
  {
      return;//Already present key

  }
}


void Inorder(Node *root)
{
  if(root == NULL) return;

  Inorder(root->left);
  cout<<root->data<<"  ";
  Inorder(root->right);

}

void GetPrecessorder(Node* root,int **m,int &row, int &col)
{
   if(root == NULL)
   {
       return;
   }

   GetPrecessorder(root->left,m,row,col);

   if(row == -1)
   {
      row = root->data-1;
      m[row][col] = root->data;
      col++;
   }
   else
   {
      m[row][col++] = root->data;
   }
   GetPrecessorder(root->right,m,row,col);
}
void FillMatrix(Node* root, int**m, int n)
{
   if(root == NULL) return;
   int row = -1;
   int col = 0;
   //All precessorder are stored in one row that row not have any precessorder so finally we make that as 0
   GetPrecessorder(root,m,row,col);

   for(int i = 0; i < n; i++)
   {
      int r = m[row][i] -1;
      for(int j = i-1; j >= 0; --j)
      {
          int c = m[row][j] - 1;
          m[r][c] = 1;
      }
   }

   memset(m[row],0,sizeof(int)*n);
}
int main()
{
   Node *root = NULL;

   root = new Node(4,NULL,NULL);

   Node *a = root->left = new Node(1,NULL,NULL);
   Node *b = root->right = new Node(6,NULL,NULL);
   a->left = new Node(5,NULL,NULL);

   b->left = new Node(3,NULL,NULL);
   b->right = new Node(2,NULL,NULL);

   int n = 6;

   int**m = new int*[n];

   //O(n) Time complexity to fill all matrix elements as 0
   for(int i = 0; i < n; i++)
   {
      m[i] = new int[n];
      memset(m[i],0,sizeof(int)*n);
   }

   FillMatrix(root,m,n);

   for(int i = 0; i < 6; i++)
   {
      for(int j = 0; j < 6; j++)
      {
         cout<<m[i][j]<<"  ";
      }
      cout<<endl;
   }
   return 0;
}

We can use hashmap

This is different thing....the question asked here and u rephrashing is different thing if u find a subset whose sum is just half of total sum it not necessary the avg of both side be same, if no of element in both side are same and sum also same then avg be same

//(Bar Raiser Round)
//Divide the array(+ve and -ve numbers) into two parts such that the
//average of both the parts is equal.

//[1 7 15 29 11 9] 
// Part1:- 15,9    Avg = 12
//Part2:- 1,7,11,29 Avg = 48/4=12


void DivideArray(int arr[],int i,int n,int sum,int part1[],int index1,int part2[],int index2)
{
   if(i > n)
   {
      return;
   }
   
   if(i == n)
   {
       if(index1 == 0 || index2 == 0) return;

       int s = 0;

       for(int p = 0; p < index1; p++)
       {
          s+=part1[p];
       }

       if(s/index1 == (sum -s)/(n-index1))
       {
          cout<<"\nPart1:-";
          for(int c = 0; c < index1; c++)
          {
             cout<<part1[c]<<"  ";
          }
          cout<<"\nPart2:-";
          for(int c = 0; c < index2; c++)
          {
             cout<<part2[c]<<"  ";
          }
       }
       return;
   }
   else
   {
      part1[index1] = arr[i];
      DivideArray(arr,i+1,n,sum,part1,index1+1,part2,index2);
      part2[index2] = arr[i];
      DivideArray(arr,i+1,n,sum,part1,index1,part2,index2+1);
   }
}
int main()
{

   int arr[] = {1,7,15,29,11,9};

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

   int sum = 0;

   for(int i = 0; i < n; i++)
   {
       sum +=arr[i];
   }
 
   int *part1 = new int[n];
   int *part2 = new int[n];
   DivideArray(arr,0,n,sum,part1,0,part2,0);
   return 0;
}

Output:-
Part1:-1 7 29 11
Part2:-15 9
Part1:-15 9
Part2:-1 7 29 11

//Count no of nodes between two keys in a bst
//These keys can present or not in bst
//do not include these keys even if they present there in counting

#include<iostream>
using namespace std;


struct Node
{
  int data;
  Node *left;
  Node *right;
  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {
   
  }
};

void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else
  {
      return;//Already present key
     
  }
}

//appproach here we will use is inorder
int CountNodesBetweenTwoKeys(Node* root, int key1, int key2)
{
   if(root == NULL) return 0;

   if(root->data == key1 || root->data == key2)
   return 0; //used to skip include keys node

   int n1 = 0;
   int n2 = 0;

   if(root->data > key1)//do not do this mistake if(root->left->data > key1)
   n1 = CountNodesBetweenTwoKeys(root->left,key1,key2);

   if(root->data < key2)//do not do this mistake if(root->right->data < key2)
   n2 = CountNodesBetweenTwoKeys(root->right,key1,key2);

   return n1+n2 + 1;//do not forget to add 1 that is used as counter
}


int main()
{
  
   
   Node *root2 = NULL;
   Insert(&root2,40);
   Insert(&root2,20);
   Insert(&root2,60);
   Insert(&root2,10);
   Insert(&root2,30);
   Insert(&root2,50);
   Insert(&root2,70);
   Insert(&root2,5);
   Insert(&root2,15);
   Insert(&root2,25);
   Insert(&root2,35);
   Insert(&root2,45);
   Insert(&root2,55);
   Insert(&root2,65);
   Insert(&root2,75);
   Insert(&root2,4);
   Insert(&root2,6);
   Insert(&root2,14);
   Insert(&root2,16);
   Insert(&root2,24);
   

   cout<<CountNodesBetweenTwoKeys(root2,3,75);
   return 0;
}

@Satish Will u try a test case on your code.....
i not know java so i cannot check

int M[5][9] = {
{0,1,1,0,1,0,1,0,0},
{1,1,0,0,1,1,1,0,0},
{0,1,1,1,1,0,0,0,0},
{1,1,0,0,0,0,0,0,0},
{0,1,1,1,0,0,0,0,0}
};

No of black shapes here is 1

1 used as black shape i mean x and 0 used for white shape

//Given n*m fields of O's and X's, where O=white, X=black, for example
//
//OOOXOOO
//OOXXOXO
//OXOOOXO

//Return the number of black shapes. A black shape consists of one or
// more adjacent X's (diagonals not included).
// In the example, the answer is 3.


using namespace std;


void explore(int arr[][7],int i,int j,int m,int n)
{
    if(i < 0 || i > m-1)
    {
       return;
    }
    if(j < 0 || j > n-1)
    {
      return;
    }

    if(arr[i][j] == 0 || arr[i][j] == -1)
    {
       return;
    }

    arr[i][j] = -1;

   //Open below to include diagonal also
   /* 
   explore(arr,i-1,j-1,m,n);
   explore(arr,i+1,j+1,m,n);
   explore(arr,i-1,j+1,m,n);
   explore(arr,i+1,j-1,m,n);
   */

   explore(arr,i,j-1,m,n);
   explore(arr,i,j+1,m,n);
   explore(arr,i-1,j,m,n);
   explore(arr,i+1,j,m,n);
}

int countbBlackShapes(int arr[3][7],int m,int n)
{
   int count = 0;

   for(int i = 0; i < m; i++)
   {
      for(int j = 0; j < n; j++)
      {
         if(arr[i][j] == 1)
         {
            explore(arr,i,j,m,n);
            count++;
         }
      }
   }

    //To recovedr the data again place -1 as 1
    for(int p = 0; p < m; p++)
    {
      for(int q = 0; q < n; q++)
      {
          if(arr[p][q] == -1)
            arr[p][q] = 1;
      }
   }

   return count;
}

int main()
{
   //OOOXOOO
   //OOXXOX
   //OXOOOXO

   //X =1
   //O =0

    int M[3][7]= {
        {0,0,0,1,0,0,0},
        {0,0,1,1,0,1,0},
        {0,1,0,0,0,1,0}
    };
    cout<<"Number of Black Shapes="<<countbBlackShapes(M,3,7);
}

this is my initial appraoch i will improve it for time complexity...

i have some doubts abt this problem

if u want that there should exists a path from

Node A to Node B i say its color a
Node B to Node C i say its color b
Node C to Node A i say its color c

if (a == red || b ==red || c ==red) then (A,B,C) is triplet...

if u look a closed walk of size 3 then i think its cannot be tree....trees not have closed path......

i think it can be a graph....

if i take it as graph

then Make all cominations of tree element out of N elements

for each combination check there exists a closed path from a to b , b to c , c to a

if closed paths exists && 1 red edge also then print that combination

plz check is it a tree or graph...i post solution once its confirmed

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<stack>
using namespace std;


struct Node
{
  int data;
  Node *left;
  Node *right;

  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {

  }
};

void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else//To allow duplicate keys do not return from here
  {
    //return;//Already present key
     //Insert(&(temp->right),d);
  }
}

void BoundryTravesalUsingOneLoop(Node *root,bool pureLeft,bool pureRight)
{

    bool isPrinted = false;
  
    if(root == NULL)
    return;

    if(root->left == NULL && root->right == NULL)
    {
        if(isPrinted == false)
        {
           cout<<root->data<<"  ";
           isPrinted = true;
        }
        return;
    }
    
    if(pureLeft && (!pureRight) && isPrinted == false)
    {
        cout<<root->data<<"  ";
        isPrinted  = true;
    }
     
     BoundryTravesalUsingOneLoop(root->left,pureLeft,false);
     BoundryTravesalUsingOneLoop(root->right,false,pureRight);

     if(pureRight && (!pureLeft) && isPrinted == false)
     {
         cout<<root->data<<"  ";
         isPrinted  = true;
     }
        

}
int main()
{
  

   Node *root2 = NULL;
   Insert(&root2,40);
   Insert(&root2,20);
   Insert(&root2,60);
   Insert(&root2,10);
   Insert(&root2,30);
   Insert(&root2,50);
   Insert(&root2,70);
   Insert(&root2,5);
   Insert(&root2,15);
   Insert(&root2,25);
   Insert(&root2,45);
   Insert(&root2,55);
   Insert(&root2,65);
   Insert(&root2,75);
   Insert(&root2,4);
   Insert(&root2,6);
   Insert(&root2,14);
   Insert(&root2,16);
   Insert(&root2,24);
   // Call function with both flags as true
   // if u put left falg as false left view will not get printed
   //if u put right flag as false right view will not get printed
   BoundryTravesalUsingOneLoop(root2,true,true);

   return 0;
}

@Srinivas

As per question the tree is completely binary tree so its right

if the tree is not completely binary tree then code will fail but its written as per problem statement

//print boundary travesal for a BT
//Boundry travesal = left view + leaf view + right view 
//NoteL- Do not include root two time and left view should be moving from
//root to leaf and right view should be moving from leaf to root

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<stack>
using namespace std;


struct Node
{
  int data;
  Node *left;
  Node *right;

  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {

  }
};

int Max(int i, int j)
{
   return i > j ? i : j;
}
void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else//To allow duplicate keys do not return from here
  {
    //return;//Already present key
     //Insert(&(temp->right),d);
  }
}


int Height(Node* root)
{
   if(root == NULL)
   {
     return 0;
   }

   return 1 +Max(Height(root->left),Height(root->right));
}

void PrintLeftView(Node* root,int *p, int level)
{
   if(root == NULL) return;

   if(p[level] == INT_MAX &&(root->left != NULL || root->right != NULL))
   {
       p[level] = root->data;
   }

   PrintLeftView(root->left,p,level+1);
   PrintLeftView(root->right,p,level+1);
   
}


void PrintLeafsLeftToRight(Node* root)
{
   if(root == NULL) return;

   PrintLeafsLeftToRight(root->left);

   if(root->left == NULL && root->right == NULL)
   cout<<root->data<<" ";

   PrintLeafsLeftToRight(root->right);
}

void PrintRightView(Node* root,int* p, int level)
{
   if(root == NULL) return;
   
   if(p[level] == INT_MAX &&(root->left != NULL || root->right != NULL))
   {
       p[level] = root->data;
   }

   PrintRightView(root->right,p,level+1);
   PrintRightView(root->left,p,level+1);
  
}


void BoundryViewUtil(Node* root)
{
   int h = Height(root);

   int* p = new int[h-1];
   
   //Do not use memset here i done this mistake
 
   for(int i = 0; i < h-1;i++)
   p[i] = INT_MAX;

   PrintLeftView(root,p,0);
   for(int i = 0; i < h-1; i++)
   {
       cout<<p[i]<<"  ";
   }

   
   PrintLeafsLeftToRight(root);
   

   for(int i = 0; i < h-1;i++)
   p[i] = INT_MAX;

   PrintRightView(root,p,0);
   for(int i = h-2; i > 0; i--)//root already included with left so i > 0
   {
       cout<<p[i]<<"  ";
   }
   
   delete []p;//clean memory 
}
int main()
{
   Node *root1 = NULL;
   Insert(&root1,12);
   Insert(&root1,18);
   Insert(&root1,7);
   Insert(&root1,9);
   Insert(&root1,11);
   Insert(&root1,13);
   Insert(&root1,17);
   Insert(&root1,19);
   Insert(&root1,21);
   Insert(&root1,23);

   BoundryViewUtil(root1);

   return 0;
}

//Telephone Dir
//Search by telephone no
//Search by name
//A person can have more than 1 telehpne no
//But a telephone no should be assigned to 1 person

#include<iostream>
#include<map>

using namespace std;

bool isTelNoExists(multimap<string,string> &mp,int num)
{
    stringstream ss;
    ss << num;
    string str = ss.str();
   
    std::pair<multimap<string,string>::iterator,multimap<string,string>::iterator> p = mp.equal_range(str);
    multimap<string,string>::iterator it1 = p.first;
    multimap<string,string>::iterator it2 = p.second;
  
    return it1 != it2;
}

void AddContactToDir(multimap<string,string> &mp,string name,int pNo)
{
   if(isTelNoExists(mp,pNo) == true) return;

   stringstream ss;
   ss << pNo;
   string str = ss.str();
   mp.insert(std::make_pair(str,name));
   mp.insert(std::make_pair(name,str));
}

void SearchContact(multimap<string,string> &mp,string name)
{

      std::pair<multimap<string,string>::iterator,multimap<string,string>::iterator> p = mp.equal_range(name);

  
      multimap<string,string>::iterator it1 = p.first;
      multimap<string,string>::iterator it2 = p.second;
  
      cout<<"\nSearch Contact by name  "<<name<<endl;
      if(it1 == it2)
      {
         cout<<name<<"  "<<"does not exists in Dir"<<endl;
      }
      else
      {
          
          cout<<"\nContact Details  ";
          while(it1 != it2)
          {
             cout<<it1->second<<"  ";
             it1++;
          }
      }
}

void SearchContact(multimap<string,string> &mp,int num)
{
   stringstream ss;
   ss << num;
   string str = ss.str();
   
    cout<<"\nSearch Contact by Phone no  "<<endl;
    multimap<string,string>::iterator it = mp.find(str);
    if(it == mp.end())
    {
       cout<<"\nNo Person found corresponding to Tel No"<<num<<endl;
       return;
    }
    cout<<"\nContact Found  "<<it->second<<"  "<<num<<endl;  
}
int main()
{
  multimap<string,string> mp;
  AddContactToDir(mp,"Satveer",100);
  AddContactToDir(mp,"Suman",101);  
  AddContactToDir(mp,"Sunil",102);  
  AddContactToDir(mp,"Suman",103);  
  AddContactToDir(mp,"Satveer",104);  
  AddContactToDir(mp,"Sunil",105);  
  SearchContact(mp,"Suman"); 
  SearchContact(mp,104); 
  return 0;
}

//bubble sort approach

void bubble_sort(Node* head)
{
   if(head == NULL || (head)->next == NULL)
   {
       return;
   }

   int count = 0;
 
   Node* temp = head;
   while(temp != NULL)
   {
       count++;
       temp = temp->next;
   }
   

   Node *p = NULL;
   Node *q = NULL;
   bool flag = false;

   for(int i = count-1; i > 0; --i)
   {
       p = head;
       q = head->next;
       flag = false;

       for(int j = 0; j < i; j++)
       {
          if(p->data > q->data)
          {
             flag = true;
             swap(p->data,q->data);
          }
          p = p->next;
          q = q->next;
       }

       if(flag == false) break;
       
   }
}

//Sort a linklist using merge sort
//We will change nodes pointer to make it sorted
//Rewrite merge function such a way that we not need to use merge_util
// as helper

struct Node
{
  int data;
  Node *next;
  Node(int d, Node* temp) : data(d),next(temp)
  {

  }
};

void Insert(Node** head,int data)
{
   if(*head == NULL)
   {
       *head = new Node(data,NULL);
   }
   else
   {
      Insert(&((*head)->next),data);
   }
}

void print(Node *head)
{
   while(head != NULL)
   {
      cout<<head->data<<"  ";
      head = head->next;
   }
}

//Other version of middle we should not use which return
//n/2+1 th node as middle
//Subproblem1=>[head,mid]
//Subproblem2=>[mid+1,end)
//else there will be a infinite loop when item are 2
Node* middle(Node *head)// mid = n/2 th node
{
   if(head == NULL || head->next == NULL)
   {
       return head;
   }

   Node* slow = head;
   Node* fast = head;

   while(fast && fast->next)
   {
       fast = fast->next->next;
       if(fast == NULL) break;
       slow = slow->next;
   }
   return slow;
}

Node* merge(Node* head1, Node* head2)
{
    if(head1 == NULL) return head2;
   
    if(head2 == NULL) return head1;

    Node *result = NULL;
   
    if(head1->data <= head2->data)
    {
        result = head1;
        result->next = merge(head1->next,head2);
    }
    else
    {
       result = head2;
       result->next = merge(head1,head2->next);
    }
    return result;
}

void merge_util(Node** head1,Node **head2)
{
   *head1 = merge(*head1,*head2);
   *head2 = NULL;
}
void merge_sort(Node** head)
{
   // min size of subproblem is 2 size so if 2 or more element then call it
   if((*head)->next != NULL)
   {
       Node *mid = middle(*head);

       Node *second = mid->next;
       mid->next = NULL;

       merge_sort(head);
       merge_sort(&second);
       merge_util(head,&second);
   }
}

int main()
{

   Node* head = NULL;

   Insert(&head,5);
   Insert(&head,4);
   Insert(&head,3);
   Insert(&head,2);
   Insert(&head,-1);
   Insert(&head,-2);
   Insert(&head,-3);
   Insert(&head,-4);
   merge_sort(&head);
   print(head);
   return 0;
}

We can use merge sort here if we want do using link modify, if the problem is we can modify data itself then this question is easy and we can use bubble sort of selection sort...i will post solution soon both ways......

Wrong result....

As per my knowledge pipe implemented as file inodes so the information they can hold is limited bcoz all the info stay in structures, while using pipe for communication when u read it, data automatically removed from pipe and u not need to take care of it.

Its while(*p != '\0')

Yes while( *p != '\0') it should be i write ! mistakely

now i modify fun

const char * fun()
{
return "This is test string";
}

is there any issue ....

there is no issue string literals go in data section so without pointing to a variable we can directly return them....

Hey, do u know what is constant...what u thinking is totally wrong....

const char* p = "Test"; here data is const not the pointer so *p = 'A' //error
p++; // no issue

char const *p = "Test"; //this and above are same thing const u putting after * or before * makes sensde

char const * p is same as const char *p

the logic was here string literals stored in RO data section so this will available even after stack become empty so this programme prints "This is test string";

char arr[] = "This is test string"; if i do like this then its char *const arr= "This is test string";

in this case if i try ptr++ it fail

so we do like

int i = 0;

while(*(arr+i) != '\0')
{
cout<<*(arr+i);
i++;
}

but u can change data here not the pointer.....

char* const fun()
{
char arr[] = "This is test string";
return arr;
}

this is wrong thing once stack empty data lost and if u try access it u get seg fault...

//How many occurrences of a given search word can you find in a two-dimensional
// array of characters given that the word can go up, down, left, right, 
//and around 90 degree bends?

//Ex:
//Count of occurrences of SNAKES
//S N B S N
//B A K E A
//B K B B K
//S E B S E

//The answer is 3. 

#include<iostream>
#include<stdlib.h>
using namespace std;

//Maximum movement allowed is equal to length of target word
int FoundWaysToMakeWord(int arr[][5],int i, int j,int m, int n,int index, int maxIndex,int curr[], int target[])
{
   if(i == -1 || i == m)  //allowed index are upto m-1
   {
        return 0;
   }
   if(j == -1 || j == n)//allowed index are upto n-1
   {
        return 0;
   }

   if(index > maxIndex)//SNAKE max index = 4 we can fill char 0 1 2 3 4 position
   {
      return 0;
   }

   curr[index] = arr[i][j];

   if(curr[index] != target[index])
   {
        return 0;//char mismatch found
   }

   if(index == maxIndex)//it mean last char also matched mean we done it 
   {
      return 1;
   }

  return (FoundWaysToMakeWord(arr,i+1,j,m,n,index+1,maxIndex,curr,target) +
  FoundWaysToMakeWord(arr,i-1,j,m,n,index+1,maxIndex,curr,target) +
  FoundWaysToMakeWord(arr,i,j+1,m,n,index+1,maxIndex,curr,target) +
  FoundWaysToMakeWord(arr,i,j-1,m,n,index+1,maxIndex,curr,target));
   
}

/*
//start point can be only (0,0),(m-1,0),(0,n-1),(m-1,n-1)
int FoundWaysToMakeWordUtil(int arr[][5],int target[], int m, int n,int length)
{ 
    int *p = new int[length];
   
    return FoundWaysToMakeWord(arr,0,0,m,n,0,length-1,p,target)+
           FoundWaysToMakeWord(arr,0,n-1,m,n,0,length-1,p,target)+
           FoundWaysToMakeWord(arr,m-1,n-1,m,n,0,length-1,p,target)+
           FoundWaysToMakeWord(arr,m-1,0,m,n,0,length-1,p,target);
}
*/

int FoundWaysToMakeWordUtil(int arr[][5],int target[], int m, int n,int length)
{ 
    int *p = new int[length];

    int count = 0;
    
    for(int i = 0; i < m;i++)
    {
       for(int j = 0; j < n; j++)
       {
           if(arr[i][j] == 'S')
           {
               count += FoundWaysToMakeWord(arr,i,j,m,n,0,length-1,p,target);
           }
       }
    }

    return count;
}


int main()
{
   int p[4][5] = {
                   {'S', 'N', 'B', 'S', 'N'},
                   {'B', 'A', 'K', 'E', 'A'},
                   {'B', 'K', 'B', 'B', 'K'},
                   {'S', 'E', 'B', 'S', 'E'}
                 };
   int target[] = {'S','N','A','K','E','\0'};

   cout<<FoundWaysToMakeWordUtil(p,target,4,5,5)<<endl;
}

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<stack>
using namespace std;


struct Node
{
  int data;
  Node *left;
  Node *right;
  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {

  }
};


void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else//To allow duplicate keys do not return from here
  {
    //return;//Already present key
     Insert(&(temp->right),d);
  }
}


int Max(int i, int j)
{
     return i>j?i:j;
}
int Height(Node* root)
{
   if(root == NULL) return 0;

   return Max(Height(root->left),Height(root->right))+1;
}

Node* lcabt(Node* root, int i, int j, bool &flag1, bool &flag2)
{
    if(root == NULL)
        return NULL;

    Node *p1 = lcabt(root->left,i,j,flag1,flag2);
    Node *p2 = lcabt(root->right,i,j,flag1,flag2);

    if(p1 != NULL && p2 != NULL)
    {
       return root;
    }
    //Do not place these checkers before recursion
    if(root->data == i)
    {
      flag1 = true;
      return root;
    }

    if(root->data  == j)
    {
      flag2 = true;
      return root;
    }

    return p1==NULL ? p2 : p1;
}

int PathDistance(Node* root, int i)
{
  if(root == NULL)
    return 0;

  if(root->data == i)
    return 1;

  int x = PathDistance(root->left,i);
  int y = PathDistance(root->right,i);

  if(x > 0 || y > 0)
  {
     return (Max(x,y)+1);
  }

  return 0;
}
int Distance(Node* root, int i, int j)
{
    if(root == NULL) return 0;
    
    if(i == j) return 0;

    bool flag1 = false;
    bool flag2 = false;
    Node* p = lcabt(root,i,j,flag1, flag2);

    if(flag1 == false || flag2 == false || p == NULL)
    {
      return -1;
    }
    return (PathDistance(p,i) + PathDistance(p,j) - 2);
}

//==============================Suman Code for Testing======================
int recursiveGetDistance(Node *root, int key1, int key2)
{
	if (root == NULL)
        {
	   return 0;
        }
 
	if (root->data == key1 || root->data == key2)
	{
	   return 1;
	}
		
	int lDistance = recursiveGetDistance(root->left, key1, key2);
	int rDistance = recursiveGetDistance(root->right, key1, key2);
	if (lDistance == 0 && rDistance == 0)
	{
	    return 0;
	}
	else
	{
	    return lDistance + rDistance+1;
	}
	        
}	

int findShortestDistance(Node *root, int key1, int key2)
{
   if (root == NULL)
   {
	return 0;
   }
   int lDistance = recursiveGetDistance(root->left, key1, key2);
   int rDistance = recursiveGetDistance(root->right, key1, key2);
   if (lDistance > 0 && rDistance ==0)
   {
	return findShortestDistance(root->left, key1, key2);
   }
   else if (lDistance == 0 && rDistance > 0)
   {
        return findShortestDistance(root->right, key1, key2);
   }
   else
   {
	return rDistance+lDistance+1;
   }
}
	
//=====================================================================

int main()
{
   Node *root1 = NULL;
   Insert(&root1,12);
   Insert(&root1,18);
   Insert(&root1,7);
   Insert(&root1,9);
   Insert(&root1,11);
   Insert(&root1,13);
   Insert(&root1,17);
   Insert(&root1,19);
   Insert(&root1,21);
   Insert(&root1,23);

  
   cout<<"Suman Logic  "<<findShortestDistance(root1,23,18)<<endl;

   cout<<"My Logic"<<Distance(root1,23,18)<<endl;

   cout<<"Suman Logic  "<<findShortestDistance(root1,11,100)<<endl;

   cout<<"My Logic"<<Distance(root1,11,100)<<endl;

  return 0;

}

Output:- 

Suman Logic  1
My Logic3
Suman Logic  1
My Logic-1

Thanks buddy, you solved for top 5 but its not right solution

S1 S2 S3 S4 S5 25 24 23 22 21
S6 S7 S8 S9 S10 20 19 18 17 16
S11 S12 S13 S14 S15 15 14 13 12 11
S16 S17 S18 S19 S20 10 9 8 7 6
S21 S22 S23 S24 S25 5 4 3 2 1

if horses speed like this then if u eliminate bottom 2 from each group, u cannot find right top 5 horses, check your approach on this type data

improve your solution...i able to solve it in 9 races worst case but i looking better than this.....9 is my answer....

not necessary that eahc group top racer is among top 5...try it more...

@LoveCoding : What abt if we have space constraint then how to design

My Openion :- Implement a separate minStack that contain only min data like

i/p - 10 ->5->12->14->0->8->11
min Stack - 10->5->0
pop operation design like if is popped from Main stack then pop from minstack also else pop from main stack only