CareerCup

1) Count the number of times 'a' appears in the array
2) Allocate an array of the required size / increase the size of the current array
3) Keep at write pointer at the end of the newly allocated array size , and a read pointer at the end of the original array size
4) Start reading each character and writing where the write pointer is. If you read an a write zyx instead; decrement the write point and read pointers as you write.

Sorry, I wasn't clear when writing the question. The input array is large enough to handle the extra characters, so you're suppose to modify the input array and not create a new array.

found all the occurrence of a in array.
starting from end of the array, start right shifting the each char.
number of shift= number of occurrence of a * 2. len( xyz-a))=2
while shifting if you encounter a replace it with xyz.

ruining time : 2n = O(n)

char* modifyString( char* str )
{
      int sz=0;
      int count=1;
      
      for( i=0;str[i];i++ )
       {
          sz++; 
           if( str[i]=='a' )
            count++ ;
            
            }
            
       
       p=sz-1;     
       sz = sz + (count*2) +1 ;
       q=sz-1;
       
       str=(char*)realloc( str , sz*sizeof(char) );
       if( str==NULL )
        return NULL ;
        
      
       
       while( p>=0 )
       {
            if( str[p]=='a' )
             {
                  str[q--]='z';
                  str[q--]='y';
                  str[q--]='x';
                  
                  p--;
                  continue;
                  
                  }
                  
             else 
              {
                  str[q--]=str[p];
                  p--;
                  
                  }
                  
                  
                  }
                  
                 return str;
                 
                 }

above suggested algo, i guess will go in o(n^2) in worst time..I think we can do something better to get o(n) worst time..For This we need a bit of extra memory as it was said that array is large enough to accommodate values.. So i am taking it granted..
So go like -
scan an array from left , when you encounter first a, not this index and put three blanks after the last character and start copy from next location (after first a) to last (after three inserted blanks).and for any occurrence of a put three blanks.
At last replace the blanks with xyz and shift the entire array...

The above answer is o(n) complex - why do you think that in the worst case it is going to be o(n^2).

You have to do 2 passes to get O(n)
Pass 1.
- count the number of 'a's and store it in a count variable
Pass 2.
- Loop from end to beginning of array
- Copy array[i] to array[i+2*count]
- When an a is encountered, put z at array[(i+2*count)-1], y at array[(i+2*count)-2], x at array[(i+2*count)-3] and decrement count