Akamai Interview Question
Java DevelopersCountry: India
Interview Type: In-Person
You are right, more specific the technique is hill climbing, you can find the lowest element of such function with log(n) complexity.
seems to work for the given example but wouldn't you want the line to be
else if(v[m] > v[s])
, just happens to work that s would stay 0 in this example before it would matter
lets array length is L
reminder = n % L
reminder < (L-reminder) ? reminder : (L-reminder)
ex: 1 2 3 4 5 6 7 8 9
case 1: n = 13
reminder = 13%9 = 4
6 7 8 9 1 2 3 4 5 here 6 7 8 9 (4 numbers) are not in correct position
case 2: n = 23
reminder = 23%9 = 5
5 6 7 8 9 1 2 3 4 here 1 2 3 4 is not in correct position, here return reminder or (L-reminder) which ever is smaller
to print the numbers that are not in correct position
if(reminder < (L-reminder))
{
for(int i=0; i < reminder; i++)
cout << a[i] << " ";
}
else
{
for(int i=reminder; i < L; i++)
cout << a[i] << " ";
}
1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 #include<iterator>
5
6 void swap(int array[],const int& length,const int& swaps)
7 {
8 int temp_array[swaps];
9 memmove(temp_array,array+(length-swaps),sizeof(int)*swaps);
10 memmove(array+(length-swaps),array,sizeof(int)*swaps);
11 memmove(array,temp_array,sizeof(int)*swaps);
12 }
13
14 int main()
15 {
16 int array[] = { 10, 20 , 30, 40, 50 };
17 int length = 5;
18 int swaps = 2;
19 swap(array,length,swaps);
20 std::copy(array,array+length,std::ostream_iterator<int>(std::cout," "));
21 }
#include <iostream>
#include <vector>
using namespace std;
int getIndex(int index, int rot, int size)
{
int tot = index + rot;
if(tot >= size)
return tot%size;
else
return tot;
}
void swap(int* x, int *y)
{
}
void arrayRotation(vector<int> &v, int rot)
{
int lIndex = v.size() - 1;
int index = lIndex;
int tIndex = -1;
int tVar = v.at(lIndex);
do
{
tIndex = getIndex(index, rot, v.size());
//swapping the element -start
int temp = v.at(tIndex);
v.at(tIndex) = tVar;
tVar = temp;
//swapping the element - End
index = tIndex;
}while(index != lIndex);
}
int main()
{
int myints[] = {10,20,30,40, 50};
int rot =3;
std::vector<int> v(myints, myints + sizeof(myints) / sizeof(int) );
for(int i =0; i< v.size(); i++)
cout<<v.at(i)<<"\t";
cout<<endl;
arrayRotation(v,rot);
for(int i =0; i< v.size(); i++)
cout<<v.at(i)<<"\t";
cout<<endl;
return 0;
}
The rotation can be done in Linear Time, I don't think it will posiible to do less than liner because there will be a change in every element of the array.
1.first check if the array is rotated or not
2.if not rotated then count is 0
3.then check for <=n rotations
4.find its rotations times using binary search
#include<stdio.h>
int binary_search(int a[],int lb,int ub,int n,int *c)
{
int mid=lb+(((ub-lb)+1)/2);
if((mid>0)&&(a[mid]>a[mid-1])&&(mid<n)&&(a[mid]>a[mid+1]))
*c=mid;
if(!*c)
binary_search(a,lb,mid,n,c);
if(!*c)
binary_search(a,mid+1,ub,n,c);
return c;
}
int main()
{
int a[]={70,80,90,10,20,30,40,50,60};
int n=(sizeof(a)/sizeof(a[0])),c=0;
binary_search(a,0,n-1,n-1,&c);
if(a[0]<a[n-1])
{
printf("0");
return 0;
}
else if(c)
{
printf("%d",c+1);
return 0;
}
else if(a[0]>a[n-1])
{
printf("%d",n);
return 0;
}
return 0;
}
An O(logn) solution:
int find_head(int A[], int n)
{
int l, r, m;
l = 0; r = n-1;
while (l < r) {
m = (l+r)/2;
if (A[m] < A[r])
r = m;
else if (A[m] >= A[l])
l = m+1;
}
return l;
}
/**
* O(logn)
* find no of rotations - circularly sorted array, anti-clockwise, no duplicates - binary
* no of rotation = index of min element
* @param source
* @param needle
* @return
*/
private int countRotationsBinary(int[] source){
int low = 0;
int high = source.length - 1;
int length = source.length;
while( low <= high ){
if( source[low] <= source[high] ) return low; //case 1 (sorted array)
int mid = ( low + high ) / 2;
int next = (mid+1) % length;
int prev = (mid+length-1) % length;
if( source[mid] <= source[prev] && source[mid] <= source[next] ) return mid; //case 2
if( source[mid] <= source[high] ) { high = mid - 1; } //case 3 - search left
if( source[mid] >= source[low] ) { low = mid + 1; } //case 4 - search right
}
return -1;
}
the problem can be solved by using binary search in 0(logn) time. enjoy.
public class RotateArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] x = {10,20,30,40,50,60,70};
getRotateArray(x, 3);
}
public static void getRotateArray(int[]y, int rotate){
for (int j = 0; j < rotate; j++) {
for (int i = y.length-1; i > 0; i--) {
int temp =y[i];
y[i] =y[i-1];
y[i-1] =temp;
}
}
for (int i = 0; i < y.length; i++) {
System.out.println(y[i]);
}
}
}
Binary Search could be used, compare the middle element A[m] with next element A[m+1], if A[m] > A[m+1], then m is the turning point; else compare A[m] with A[0] to determine the next range, code as follow:
- Leo August 23, 2013