Akamai Interview Question 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);

- atul gupta on August 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but will it be a linear complexity??

- Anonymous on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes it is linear O(N) .

- addy on November 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Rotation is equivalent to multiple reversals inplace.

- marti on August 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- dc360 on August 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Malluce on August 10, 2012 | Flag
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.

- Anonymous on August 10, 2012 | Flag Reply
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;
	}

- dc360 on August 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution:
ideone.com/KeAcS

- cobra on August 10, 2012 | Flag Reply
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]

- pws on August 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Malluce on August 10, 2012 | Flag
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)

- Mike on August 11, 2012 | Flag Reply
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]

- Jack on August 12, 2012 | Flag Reply
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;
}

- r.s on August 29, 2012 | Flag Reply
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]+" ");
	}
}

- codingAddicted on August 31, 2012 | Flag Reply


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More