Reverse an integer array of length 2^n recursively and return a new array without modifying the original

Question

I encountered the following question in an interview.

Complete this function to return a reversed array without modifying the function signature or the original array. Note that static data types should not be used here at all.

Assume the arrayLength is a power of 2. i.e 2^n. -> I think this is the trick here.

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

}

Please help. Note that I could not really think of a solution to the problem. The interviewer hinted at using 2^n for the puspose, but i could not really think of the 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

Agree with OP the the hint is "2^n". As with many recursive functions: divide and conquer.

This routine first deals with errant paramters and the simple lengths. Next, divide the length in half and reverse each half. Form the result by concatenating the reversed left and right sub-arrays. First, right, then left.

Usual clean-up follows

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