Samsung Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
Step 1:
Find the number of times array was rotated.
Step 2:
Split the array into two parts
step 3: apply binary search on same.
ex: original array
1,2,3,4,5,6,7,8,9
rotated array:
6,7,8,9,1,2,3,4,5,
the number to find 7:
Answer:
Step 1: array was rotated by 4 times.
step 2:
part 1 array: 6,7,8,9
part 2 array: 1,2,3,4,5
step 3:
Do a binary search in part 1
#include<bits/stdc++.h>
using namespace std;
int findPivotIndex(int * arr,int n){
int start=0,end=n-1;
int answer=0;
while(start<end){
int mid=(start+end+1)/2;
if(arr[mid]>arr[0]){
start=mid+1;
}
else if(arr[mid]<arr[0]){
answer=mid;
end=mid-1;
}
}
return answer;
}
int findElement(int * arr,int start,int end,int ele){
int index=-1;
while(start<end){
int mid=(start+end)/2;
if(ele>arr[mid]){
start=mid+1;
}
else if(ele<arr[mid]){
end=mid-1;
}else if(ele==arr[mid]){
return mid;
}
}
return index;
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int element;//element to be searched
cin>>element;
int pivot=findPivotIndex(arr,n),index=-1;
if(pivot>0 && element<=arr[pivot-1] && element>=arr[0]){
index=findElement(arr,0,pivot-1,element);
}else if(element>=arr[pivot] && element<=arr[n-1]){
index=findElement(arr,pivot,n-1,element);
}else{
index=-1;
}
cout<<"Index of element is "<<index<<endl;
return 0;
}
If the array is regular array without any special property then it does not add any value for multiple times rotation. A regular linear search will be the answer.
- Mohsin May 16, 2018If the array is sorted and rotated an unknown number of times and find an integer, still binary search algorithm with minor change will solve this problem.