## Akamai Interview Question

Java Developers**Country:**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