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) ."]";
#include<iostream>
#include<vector>
using namespace std;
void bubbleSort(vector<int> &arr,int k)
{
for (int i=arr.size();i>0;i--){
for (int j=arr.size()-1;j>(arr.size()-i);j--){
cout<<" j :"<<j<<endl;
if(arr[j-1]> arr[j])
{
int temp=arr[j];
//cout<<"Before temp :"<<temp<<" a[j] :"<<arr[j]<<" a[j+1] :"<<arr[j+1]<<endl;
arr[j]=arr[j-1];
arr[j-1]=temp;
//cout<<"After temp :"<<temp<<" a[j] :"<<arr[j]<<" a[j+1] :"<<arr[j+1]<<endl;
}
}
cout<<"i :"<<i-1<<" i-k :"<<arr.size()-k<<endl;
if(i-1==arr.size()-k)
break;
}
}
int main()
{
vector<int> arr ={643,76,75,45,44,34,12};
bubbleSort(arr,2);
for (int i=0;i<arr.size();i++)
cout<<arr[i]<<",";
cout<<endl;
}
Python 3+ solution:
def reverse(arr, k):
sub_array = arr[:k]
sub_array.reverse()
remaining = arr[k:]
return sub_array + remaining
def sort(arr):
for i in range(len(arr)-1):
for j in range(len(arr)-1):
if arr[j] > arr[j+1]:
aux = reverse(arr[j:j+2], 2)
arr = arr[:j] + aux + arr[j+2:]
return arr
function reverse(dataList, k) {
if (k === 0 ) {
return dataList;
}
let resultArray = [];
let currentProcessedDataList = [];
for (var i=0; i<dataList.length; i++) {
if (currentProcessedDataList.length < k) {
currentProcessedDataList.push(dataList[i]);
} else {
for (var j=currentProcessedDataList.length-1; j>=0; j--) {
resultArray.push(currentProcessedDataList[j]);
}
currentProcessedDataList = [dataList[i]];
}
}
if (currentProcessedDataList.length) {
for (var j=currentProcessedDataList.length-1; j>=0; j--) {
resultArray.push(currentProcessedDataList[j]);
}
}
return resultArray;
}
function findMaxValue(data) {
let max = data[0];
let maxIdx = 0;
for (let i=0; i<data.length; i++) {
if (data[i] > max) {
max = data[i];
maxIdx = i;
}
}
return {max, maxIdx};
}
function sort(dataList, asc) {
let resultArray = dataList, reversedArrPart = [], leftArrPart = [];
for (let i=0; i<resultArray.length; i++) {
reversedArrPart = i=== 0 ? [] : resultArray.slice(0, i);
leftArrPart = resultArray.slice(i);
let maxValue = findMaxValue(leftArrPart, i);
let maxReverseArr = reverse(leftArrPart, maxValue.maxIdx + 1);
resultArray = reversedArrPart.concat(maxReverseArr);
}
if (asc) {
resultArray = reverse(resultArray, resultArray.length);
}
return resultArray;
}
def reverse(arr, k):
mid = int(k/2)
for i in range(mid):
new_index = (k-1) - i
# swap i and new_index
temp = arr[new_index]
arr[new_index] = arr[i]
arr[i] = temp
return arr
print(reverse([2,3,1,5,4] ,4))
def sortUsingReverse(arr):
# keep the unsorted count and let's call it current size
cur_size = len(arr)
# find the index of max elemnt in array
while(cur_size > 1):
max_index = 0
for i in range(1,cur_size):
if arr[i] > arr[max_index]:
max_index = i
# flip the arr from 0--> max index
reverse(arr,max_index+1)
# flip the array from 0--> cursize-1
reverse(arr,cur_size)
cur_size -= 1
- Chaitanya Srikakolapu November 18, 2019public void sort(int[] arr){ int startIndex = 0; int distance = 1; int[] newArr; for(int i=0;i<arr.length;i++){ if(i+1 != arr.length && arr[i] >arr[i+1]){ distance++; }else{ if(distance>1){ newArr = new int[distance]; for(int j=0;j<distance;j++){ newArr[j] = arr[startIndex+j]; } int[] revArr = revArr(newArr, distance); for(int j=0;j<distance;j++){ arr[j+startIndex] = revArr[j]; } i=-1; startIndex=0; distance=1; }else{ startIndex++; } } } }