Return back an integer array of length 2 ^ n recursively and return a new array without changing the original

Question

In an interview, I met the following question.

End this function to return the return array without changing the signature of the function or the original array. Note that static data types should not be used here at all.

Suppose the length of the array is 2. ie 2 ^ n. → I think this is a trick.

int* reverse(int *array, int arrayLength){

}

Please, help. Please note that I really could not come up with a solution to the problem. The interviewer hinted at using 2 ^ n for puspose, but I couldn't really think of a solution.

Answer 1

How about this:

int* reverse(int *array, int arrayLength){
  if (arrayLength==1) {
    int* out=(int*)malloc(sizeof(int));
    out[0] = array[0];
    return out;
  }
  int* left = reverse(array+arrayLength/2, arrayLength-arrayLength/2);
  int* right = reverse(array,arrayLength/2);
  int* out = (int*)realloc(left, sizeof(int)*arrayLength);
  memcpy(out+arrayLength/2, right, sizeof(int)*(arrayLength/2));
  free(right);
  return out;
}

Answer 2

OP, "2 ^ n". : .

. . , . , , .

#include <string.h>
#include <stdlib.h>


int* reverse(int *array, int arrayLength) {
  // Check parameters
  if (array == NULL || arrayLength < 0) {
    ; // TBD HandleBadParameters();
  }

  // Allocate space for result, not much to do if length <= 1
  int *y = malloc(arrayLength * sizeof *y);
  if (y == NULL) {
    ; // TBD HandleOOM();
  }
  if (arrayLength <= 1) {
    memcpy(y, array, arrayLength * sizeof *y);
    return y;
  }

  // Find reverse of the two halves
  int halflength = arrayLength / 2;
  int *left = reverse(array, halflength);
  int *right = reverse(&array[halflength], halflength);

  // Append them to the result - in reverse order
  memcpy(y, right, halflength * sizeof *y);
  memcpy(&y[halflength], left, halflength * sizeof *y);

  // Clean-up and return
  free(right);
  free(left);
  return y;
}

Answer 3

int* reverse(int *array, int arrayLength){
    if(arrayLength == 0) return array;
    int* ret = (int*)malloc(arrayLength*sizeof(int));
    for(int i=0;i<arrayLength;i++) ret[i] = array[arrayLength-1-i];
    return reverse(ret, 0); // technically recursive
}

Answer 4

( ):

int *reverse(int *array, int arrayLength)
{
    if (arrayLength > 1) {
        int i, n = arrayLength >> 1;
        int *m = calloc(n, sizeof(int));

        memcpy(m, array, n*sizeof(int));
        memcpy(array, array + n, n*sizeof(int));
        memcpy(array + n, m, n*sizeof(int));
        free(m);
        reverse(array, n); 
        reverse(array+n, n); 
    } /* for */
    return array;
} /* reverse */

, .

int *reverse(int *a, int al) 
{
    if (al > 1) {
        int i, a1 = al >> 1;

        for (i = 0; i < a1; i++) {
            int temp = a[i];
            a[i] = a[i + a1];
            a[i + a1] = temp;
        } /* for */
        reverse(a, a1);
        reverse(a+a1, a1);
    } /* for */
    return a;
} /* reverse */

.

int *reverse(int *array, int arrayLength)
{
    int a, b;
    for (a = 0, b = arrayLength-1; a < b; a++, b--) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    } /* for */
    return array;
} /* reverse */

, , :

int *reverse(int *array, int arrayLength)
{
    int *a1, *a2;
    int *res;

    if (arrayLength > 1) {
        int l = arrayLength >> 1;
        a1 = reverse(array, l);
        a2 = reverse(array + l, l);
        res = calloc(arrayLength, sizeof(int));
        memcpy(res, a2, l*sizeof(int));
        memcpy(res+l, a1, l*sizeof(int));
        free(a1);
        free(a2);
    } else {
        /* we return always memory alloc'd with malloc() so we have to do this. */
        res = malloc(sizeof(int));
        *res = array[0];
    } /* if */

    return res;

} /* reverse */

Answer 5

, , , . . , ,

postive, , , , , , , , ,

int* reverse(int *array, int arrayLength){
        int* result;
        if(arrayLength > 0)
        {
            result =(int*) malloc((sizeof(int)*arrayLength));
            memcpy(result, array, sizeof(int)*arrayLength);
            reverse(result, -arrayLength);
            return result;
        }
        else if(arrayLength < -1)
        {
            int end = (-arrayLength)-1;
            int temp = array[end];
            array[end] = array[0];
            array[0] = temp;
            return reverse(array+1, arrayLength+2);
        }   
        return array;
    }

Answer 6

, arrayLength 2. , . , , .

int* reverse(int *array, int arrayLength){
    int * newArray = NULL;
    if(arrayLength == 1){
        newArray = (int *)malloc(sizeof(int));
        *newArray = array[0];
    } else if(arrayLength == 2){
        newArray = (int *)malloc(2 * sizeof(int));
        newArray[0] = array[1];
        newArray[1] = array[0];
    } else {
        // apply to first half
        int * first = reverse(array, arrayLength / 2);
        // apply to second half
        int * second = reverse(array + arrayLength / 2, arrayLength / 2);
        // allocate space
        newArray = (int *) malloc(arrayLength * sizeof(int));
        // copy parts in reverse way
        memcpy(newArray, second, arrayLength / 2 * sizeof(int));
        memcpy(newArray + arrayLength / 2, first, arrayLength / 2 * sizeof(int));
        // free allocated space for parts
        free(first);
        free(second);
    }
    return newArray;
}

Answer 7

.

, 2 ^ n, , . , 2. . { 2,1,4,3,6,5,8,7 }. , , ({ 4,3,2,1,8,7,6,5}). .

#include <stdio.h>
#include <stdlib.h>

int * reverse( int* arr, int length )
{

  if ( length == 1 )
  {
    int *result = malloc( sizeof( arr[0] ) );
    result[0] = arr[0];
    return result;
  }

  int * result = 0;

  if ( length == 2 )
  {
    result = malloc( sizeof( arr[0] ) * 2 );
    result[0] = arr[1];
    result[1] = arr[0];
  }
  else
  {
    int half_length = length / 2;

    // named correctly
    int * right = reverse( arr, half_length );
    int * left  = reverse( arr + half_length, half_length );

    result = malloc( sizeof( arr[0] ) * length );

    for ( int i = 0; i < half_length; ++i )
    {
      result[i] = left[i];
      result[ i + half_length ] = right[i];
    }

    free( right );
    free( left );
  }

  return result;

}

int main( void )
{
  int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  int length = 8;

  int *reversed = reverse( arr, length );

  for ( int i = 0; i < length; ++i )
  {
    printf( "%d %d\n", arr[i], reversed[i] );
  }

  free( reversed );
  return 0;
}

Answer 8

for all integer arrays with more than two elements. The basic idea is to swap elements at both ends, while the number of remaining elements is 1.

int * reverse_array (int * array, int arrayLength) {

if(arrayLength <2)
{
    return NULL;
}
else
{
     int *array1 = NULL;
     int *array2 = NULL;
     array1 = malloc(arrayLength*sizeof(int));
     memcpy(array1,array,arrayLength*sizeof(int));

     /*swap the start and end*/
     swap(array1,(array1+arrayLength-1));

      /* swap the next pair */
     array2 = reverse_array(array1+1,arrayLength-2);
     memcpy(array1+1,array2,(arrayLength-2)*sizeof(int));

     if(array2!= NULL)
     {
        free(array2);
     }
     return array1;
}

}