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;
}
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
// support variables
int len = nums.size(), l = 0, r = len, mid;
// finding the pivot
while (l < r) {
mid = (l + r) / 2;
// current element > first elemen: we move the window right
if (nums[mid] >= nums[0]) l = mid + 1;
// otherwise we move it left
else r = mid;
}
// checking for edge case - pivot at the end = sorted vector
if (l == len) l = 0;
// preparing for the next BS: target is between pivot and the last element
if (target >= nums[l] && target <= nums.back()) r = len;
// target is between the first element and the one before pivot
else r = l, l = 0;
// all other cases
// finding the element
while (l < r) {
mid = (l + r) / 2;
// mid matches the target element: we return it
if (nums[mid] == target) return mid;
// mid matches an element smaller than target: we move the window right
else if (nums[mid] < target) l = mid + 1;
// otherwise we move it left
else r = mid;
}
return nums[l] == target ? l : -1;
}
};
int main(){
Solution sol;
int n;
cin>>n;
vector<int> nums;
for(int i=0; i<n; i++){
int x;
cin>>x;
nums.push_back(x);
}
int tar;
cin>>tar;
cout<<sol.search(nums,tar);
}
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
// support variables
int len = nums.size(), l = 0, r = len, mid;
// finding the pivot
while (l < r) {
mid = (l + r) / 2;
// current element > first elemen: we move the window right
if (nums[mid] >= nums[0]) l = mid + 1;
// otherwise we move it left
else r = mid;
}
// checking for edge case - pivot at the end = sorted vector
if (l == len) l = 0;
// preparing for the next BS: target is between pivot and the last element
if (target >= nums[l] && target <= nums.back()) r = len;
// target is between the first element and the one before pivot
else r = l, l = 0;
// all other cases
// finding the element
while (l < r) {
mid = (l + r) / 2;
// mid matches the target element: we return it
if (nums[mid] == target) return mid;
// mid matches an element smaller than target: we move the window right
else if (nums[mid] < target) l = mid + 1;
// otherwise we move it left
else r = mid;
}
return nums[l] == target ? l : -1;
}
};
int main(){
Solution sol;
int n;
cin>>n;
vector<int> nums;
for(int i=0; i<n; i++){
int x;
cin>>x;
nums.push_back(x);
}
int tar;
cin>>tar;
cout<<sol.search(nums,tar);
}
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.