Akamai Interview Question for Java Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 3 vote

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:

``````#include <vector>

using namespace std;

class Solution {
public:
int pos(vector<int> v) {
int len = v.size();

if(len < 2) {
return 0;
}

int s = 0, e = len-1;

while(s <= e) {
int m = s + (e-s)/2;

if(m < len && v[m] > v[m+1]) {
return m;
}
else if(v[m] > v[0]) {
s = m+1;
}
else {
e = m-1;
}
}

return 0;
}
};``````

Comment hidden because of low score. Click to expand.
0

You are right, more specific the technique is hill climbing, you can find the lowest element of such function with log(n) complexity.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

yes.. i guess it should be

``else if (v[m]>v[s])``

Comment hidden because of low score. Click to expand.
1
of 1 vote

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] << " ";
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 }``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
using namespace std;
int getIndex(int index, int rot, int size)
{
int tot = index + rot;
if(tot >= size)
else
}
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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I haven't implmented the swap function outside, did in the same function.

Comment hidden because of low score. Click to expand.
0
of 0 vote

What is being sought out here? Do you want to predict the state of the array after n rotations or do you want to search an element in the array after it has been rotated n times?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can address this problem by searching for the index of the smallest element in the array. The original array is sorted, hence n-i+1 (i is the index of the smallest element) is the number of elements that are not in their correct position. It is an O(lg n) solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

please clarify .. what is N here.. and how can you clarify the complexity is O(logn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

I didnot understood the question

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.