## Facebook Interview Question

Software Engineers**Country:**United States

**Interview Type:**Phone Interview

I assume, the question is to sort the entire array by using ONLY the given reverse method

Input: arr = [2,3,1,5,4]

Output arr = [1,2,3,4,5]

Available method = void reverse(int[] arr, int k)

Restrictions:

1. not allowed to modify the reverse method

Possible solution:

1. Since the method can only reverse elements, one possible solution is to sort the array like a bubble sort O(N^2) by reversing the out of order elements

For example:

Input: [2,3,1,5,4]

Step1: Check index 0 and 1. They are in increasing order, so no reverse call required

Step2: Check index 1 and 2. They are out of order, so call reverse method and pass only 2 elements from the array with k = 2

and so on

Input: [2,3,1,5,4]

Step1: Check 2 and 3. They are in order so change required ==> [2,3,1,5,4]

Step2: Check 3 and 1. They need to be sorted. Call reverse ([3,1], 2) ==> [2,1,3,5,4]

Step3: Check 2 and 1. They need to be sorted. Call reverse ([2,1], 2) ==> [1,2,3,5,4]

Step4: check 1 and 2. They are in order so change required ==> [1,2,3,5,4]

Step5: check 2 and 3. They are in order so change required ==> [1,2,3,5,4]

Step5: check 3 and 5. They are in order so change required ==> [1,2,3,5,4]

Step6: check 5 and 4. They need to be sorted. Call reverse ([5,4], 2) ==> [1,2,3,4,5]

Entire array is sorted.

```
<?php function reverse($arr, $k){
$midvalue = floor($k/2);
for($i = 0; $i <= $midvalue; $i++){
$lasindex = $k - $i -1;
if($arr[$i] < $arr[$lasindex]){
continue;
}
$temp = $arr[$i];
$arr[$i] = $arr[$lasindex];
$arr[$lasindex] = $temp;
}
return $arr;
}
$arr = [2,3,1,5,4];
$res = reverse($arr, 3);
print "[". implode(",",$res) ."]";?>
```

```
function reverse($arr, $k){
$midvalue = floor($k/2);
for($i = 0; $i <= $midvalue; $i++){
$lasindex = $k - $i -1;
if($arr[$i] < $arr[$lasindex]){
continue;
}
$temp = $arr[$i];
$arr[$i] = $arr[$lasindex];
$arr[$lasindex] = $temp;
}
return $arr;
}
$arr = [2,3,1,5,4];
$res = reverse($arr, 3);
print "[". implode(",",$res) ."]";
```

- Chaitanya Srikakolapu November 18, 2019