Twitter Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
#include<iostream>
using namespace std;
void BinSear( int * , int , int , int );
void Rotate( int *A , int size , int r , int k )
{
int mid = r;
if( A[mid] == k )
cout << "Found";
BinSear( A , 0 , mid-1 , k );
BinSear( A , mid+1 , size-1 , k );
}
void BinSear( int *A , int l , int h , int key)
{
int mid = (l+h)/2;
if( l<=h )
{
if( A[mid] == key )
cout << "Found";
if( key < A[mid] )
{
BinSear( A,l ,mid-1,key);
}
else
BinSear( A , mid+1 , h , key );
}
}
Binary Search. Time complexity: O(logN)
---
#include <iostream>
#include <vector>
using namespace std;
class RotateFinder
{
public:
int leftValue,rightValue;
int find(vector<int> &array, int num)
{
if(array.size()==0)return -1;
leftValue=array[0];
rightValue=array[array.size()-1];
if(rightValue < num && num < leftValue) return -1;
return find(array, 0, array.size()-1, num);
}
int find(vector<int> &array, int l, int r, int num) {
if (l==r) return (array[l]==num) ? l : -1;
if (l+1==r) {
if (array[l]==num)return l;
else if (array[r]==num)return r;
return -1;
}
int mid = (l+r)/2;
if(array[mid]==num){
return find(array, l, mid, num);
}else if(array[mid] > num){
if(array[mid]>=leftValue && num >= leftValue || array[mid] <= rightValue && num <= rightValue) {
return find(array, l, mid, num);
} else {
return find(array, mid, r, num);
}
}else{
if (array[mid]<=rightValue && num >= leftValue)
return find(array, l, mid, num);
else
return find(array, mid, r, num);
}
}
};
int main(int argc, const char *argv[])
{
int a1[] = {9,12,12,12,16,16,16,21,21,28,1,3,9};
vector<int> array(a1, a1 + sizeof(a1)/sizeof(*a1));
for (int i=0;i<array.size();++i) cout<<array[i]<<" ";
cout<<endl;
for (int j = 0; j <= 29; ++j) {
int res = RotateFinder().find(array, j);
cout<<j<<"\t:\t"<<res<<endl;
}
return 0;
}
Hi, should the decision part be that complex? In my opinion,
if(arr[mid] < k), the only case k is not in the right side is that right is an increasing order, but k is bigger than arr[right]. Otherwise, we can search in the right side. The same for arr[mid]>k.
Correct me if I am wrong.
public static boolean findElemInRoatedSortedArray(int[]l, int k){
if (null == l || l.length<1)
return false;
int low = 0;
int high = l.length;
//split the array into 2 halves
int mid = low + (high-low)/2;
BinarySearch bs = new BinarySearch();
if (bs.binarySearch(l, k, 0, mid-1)){
System.out.println("Num Lookups required:" + bs.getCounter());
return true;
}
else if (bs.binarySearch(l, k, mid, high)){
System.out.println("Num Lookups required:" + bs.getCounter());
return true;
}
return false;
}
public static void main(String args[]){
int[] a = {10,11,12,7,8,9};
System.out.println("Found="+findElemInRoatedSortedArray(a, 7));
}
Can't we do it in O(logn)?? As we can see even after rotation there are only two possibilities,
1) The middle element is greater than both the end elements(array is rotated by more than half of the elements)
2) The middle element is less than both the end elements(array is rotated by less than half of the elements)
So using binary search we can find the spot where the ascending order is broken in O(logn) and then we have two sorted arrays so now we need to search the given element in both of the arrays using traditional binary search and return the logical OR of both..
public class Solution {
public int search(int[] a, int target) {
int start = 0;
int end = a.length-1;
while(start <= end){
int mid = (start + end)/2;
if(a[mid] == target){
//System.out.println(mid);
return mid;
}
else if(a[start] <= a[mid] ){
if(target < a[start] || target > a[mid]){
start = mid +1;
}
else
end = mid;
}
else if(a[start] > a[mid] ){
if(target > a[mid] && target < a[start]){
start = mid +1;
}
else
end = mid;
}
}
return -1;
}
}
Complexity - O(log N) , modified binary search
def binary_search_rotated(arr, c):
l = 0
h = len(arr) - 1
while h >= l:
m = (h + l) // 2
if arr[m] == c:
return m
if should_go_left(c, arr[m], arr[h]):
h = m - 1
else:
l = m + 1
return None
def should_go_left(target, mid, high):
if mid <= high and mid <= target <= high:
return False
elif mid >= high and (target >= mid or target <= high):
return False
return True
For finding an element in a rotated and rotated array we need to use the modified binary search which is a little bit different from the normal binary search algorithm which is discussed below:
Implementation:
bool binary-search(int arr[], int low, int high, int key){
if(high < low)
return false;
int mid = (high + low) /2;
if(arr[mid] == key)
return true;
if(arr[low] <= arr[mid]){
if(key >= arr[low] && arr[mid] >= key)
return binary-search(arr, low, mid - 1; key);
return binary-search(arr, mid + 1, high, key);
}
if(arr[mid] <= key && high >= key)
return binary-search(arr, mid + 1, high, key);
return binary-search(arr, low, mid - 1, key);
}
it can be done in done in O(lg N). sequence in sorted & rotated it strictly means that we can device string in 2 parts and both string would be in non decreasing order as in you eg: 10 12 56 is one string and other is 1 3 8 you have to find the point from where we have to break the string do binary search. find mid. lets write algo
- dabbcomputers March 06, 2012in you case 10 12 56 1 3 8 the mid point would be mid is 4th element store it in variable ie.
lastMid=4 and apply recursion on other part ie 1 to 3rd element and 5 to 6th element
now new mid is 12 ie 2nd element so 12 > 1(4th element lastMid value) which means that breaking point is in between 2nd and 4th ie 4th element now we found breaking point
break the sequence and apply binary search on both sequence to find value.