## Akamai Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 7 vote

reverse(arr,1,k);
reverse(arr,k+1,n);
reverse(arr,1,n);

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

but will it be a linear complexity??

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

Yes it is linear O(N) .

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

Rotation is equivalent to multiple reversals inplace.

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

I don't think its that straightforward. Consider

``````[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Rotate right by 3
[80, 90, 100, 10, 20, 30, 40, 50, 60, 70]``````

10 goes to 40's place, but 40 does not go to 10's place. That means it is a chain of replacements. You could say reverse_40_first, then reverse_10. Replacements should be done recursively then.

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

I think what you did is rotate right...it should go the other direction.
[40, 50, 60, 70, 80, 90, 100, 10, 20, 30]

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

There was a google interview question recently about std::rotate which is also applicable.

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

If you are allowed to encapsulate this array, then you don't need to rotate. Just remember k and then every get/set operation for an index i goes to a mapping logic to map to the real index. Caller thinks that the array has been rotated.
array[convert(i)] will return an element from the rotated array.

``````private int convert(int i)
{
int x = i - rotatedBy;
x = x % a.length;
if (x < 0)
x = x + a.length;
return x;
}``````

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

O(n) solution:
ideone.com/KeAcS

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

Swap the first k elements with the last k elements. Then swap the first k elements with elements in range A[n - 2k]...A[n - 1 - k]. Etc.

Consider this example with an array of 10 elements, and k = 2.

[0 1 2 3 4 5 6 7 8 9]
[8 9 2 3 4 5 6 7 0 1]
[6 7 2 3 4 5 8 9 0 1]
[4 5 2 3 6 7 8 9 0 1]
[2 3 4 5 6 7 8 9 0 1]

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

What if your array size is odd? Say [0 1 2 3 4 5 6 7 8]
[0 1 2 3 4 5 6 7 8]
[7 8 2 3 4 5 6 0 1]
[5 6 2 3 4 7 8 0 1]
[3 4 2 5 6 7 8 0 1]
then?

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

``````for  i=k->n-1  n+=k
for j=0->k-1
swap(i,j)``````

O(((n-k)*k)/k) ~O(n)

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

``````import java.util.Arrays;
import java.util.List;

public class Test
{
public static void main(String[] args)
{
List<Integer> arrayList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
int k = 12;
System.out.println("Original list: " + arrayList);
arrayList = rotateLeft(arrayList, k);
System.out.println("Result: " +arrayList);
}

static void swap(final List<Integer> arrayList, final int a, final int b)
{
System.out.println("Swap: list(" + a + ") and list(" + b + ")");
arrayList.set(a, arrayList.get(a) ^ arrayList.get(b));
arrayList.set(b, arrayList.get(a) ^ arrayList.get(b));
arrayList.set(a, arrayList.get(a) ^ arrayList.get(b));
System.out.println("New list: " + arrayList + '\n');
}

static List<Integer> rotateLeft(final List<Integer> arrayList, final int k)
{
final int actualShifts = k % arrayList.size(); // reduce unnecessary swapping

System.out.println("Actual shifts: " + actualShifts);

for (int i = 1; i <= actualShifts; i++)
{
// for optimization alternative
//int tmp = arrayList.get(iter);
for (int iter = 0; iter < (arrayList.size() - 1); iter++)
{

swap(arrayList, iter, iter + 1);

/* alternate copying strategy for optimization
arrayList.set(iter,arrayList.get(iter+1));

*/
}

/* possible optimization
arrayList.set(iter,tmp);
*/
}

return arrayList;
}
}

Output:
Original list: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Actual shifts: 3
Swap: list(0) and list(1)
New list: [2, 1, 3, 4, 5, 6, 7, 8, 9]

Swap: list(1) and list(2)
New list: [2, 3, 1, 4, 5, 6, 7, 8, 9]

Swap: list(2) and list(3)
New list: [2, 3, 4, 1, 5, 6, 7, 8, 9]

Swap: list(3) and list(4)
New list: [2, 3, 4, 5, 1, 6, 7, 8, 9]

Swap: list(4) and list(5)
New list: [2, 3, 4, 5, 6, 1, 7, 8, 9]

Swap: list(5) and list(6)
New list: [2, 3, 4, 5, 6, 7, 1, 8, 9]

Swap: list(6) and list(7)
New list: [2, 3, 4, 5, 6, 7, 8, 1, 9]

Swap: list(7) and list(8)
New list: [2, 3, 4, 5, 6, 7, 8, 9, 1]

Swap: list(0) and list(1)
New list: [3, 2, 4, 5, 6, 7, 8, 9, 1]

Swap: list(1) and list(2)
New list: [3, 4, 2, 5, 6, 7, 8, 9, 1]

Swap: list(2) and list(3)
New list: [3, 4, 5, 2, 6, 7, 8, 9, 1]

Swap: list(3) and list(4)
New list: [3, 4, 5, 6, 2, 7, 8, 9, 1]

Swap: list(4) and list(5)
New list: [3, 4, 5, 6, 7, 2, 8, 9, 1]

Swap: list(5) and list(6)
New list: [3, 4, 5, 6, 7, 8, 2, 9, 1]

Swap: list(6) and list(7)
New list: [3, 4, 5, 6, 7, 8, 9, 2, 1]

Swap: list(7) and list(8)
New list: [3, 4, 5, 6, 7, 8, 9, 1, 2]

Swap: list(0) and list(1)
New list: [4, 3, 5, 6, 7, 8, 9, 1, 2]

Swap: list(1) and list(2)
New list: [4, 5, 3, 6, 7, 8, 9, 1, 2]

Swap: list(2) and list(3)
New list: [4, 5, 6, 3, 7, 8, 9, 1, 2]

Swap: list(3) and list(4)
New list: [4, 5, 6, 7, 3, 8, 9, 1, 2]

Swap: list(4) and list(5)
New list: [4, 5, 6, 7, 8, 3, 9, 1, 2]

Swap: list(5) and list(6)
New list: [4, 5, 6, 7, 8, 9, 3, 1, 2]

Swap: list(6) and list(7)
New list: [4, 5, 6, 7, 8, 9, 1, 3, 2]

Swap: list(7) and list(8)
New list: [4, 5, 6, 7, 8, 9, 1, 2, 3]

Result: [4, 5, 6, 7, 8, 9, 1, 2, 3]``````

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

``````/*initially call with:
k = # by which to be left rotated
len = length of array
i = initial index of array to be rotated. 0 here.
*/
void Rotate(int *arr, int k, int len, int i)
{
if(!arr || (k >= len) || (k < 0))
return;
if(k == 0)
{
for(int j = 0; i < len; j++, i++)
arr[j] = arr[i];
return;
}

int tmp = arr[k-1];

Rotate(arr, --k, len, ++i);
arr[len - i] = tmp;
return;
}``````

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

I am using a temporary variable for shifting. hope that is allowed

``````package practicepackage;

public class RotateArrayLeft {

public static void main(String[] args) {

int[] numbers={1,2,3,4,5,10,20,30};
int k=4;                   		// assuming array is shifted by 4 values to the left
for(int i=0;i<k;i++)
{
int temp= numbers[0];
int j=0;
for(j=1;j<=numbers.length-1;j++)
numbers[j-1]=numbers[j];
numbers[j-1]=temp;
}
for(int l=0;l<numbers.length;l++)
System.out.print(numbers[l]+" ");
}
}``````

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

``````package data.strucure;

import java.util.Scanner;

public class ArrayRotation {

public static void main(String[] args) {
int []arr={5,2,4,9,6,3};
Scanner in=new Scanner(System.in);
int k=in.nextInt();
if(k>arr.length)
k=k%arr.length;
int temp=0;
int newIndex=0;
for(int index=0;index<arr.length-k;index++){
temp=arr[index];
if(index-k<0)
newIndex=index-k+arr.length;
else
newIndex=index-k;

arr[index]=arr[newIndex];
arr[newIndex]=temp;
}
int y=0;
while(y<arr.length)
System.out.print(arr[y++]);
in.close();
}

}``````

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.