Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

1. reverse the array from 0 to n-1
2. reverse the array from n- length
3. reverse the whole array (from 0 - length)

- Mo June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For some inputs the above said logic seems not working.
For example:
a[]={7, 8, 9, 10, 1, 2, 3, 4, 5, 6};
->rotate it 3 times
->step1: 9, 8, 7, 10, 1, 2, 3, 4, 5, 6
->step2: 9, 8, 7, 6, 5, 4, 3, 2, 1, 10
->step3: 10,1, 2, 3, 4, 5, 6, 7, 8, 9 (we got this)
But we supposed to get
correct o/p should be: 4,5,6,7,8,9,10,1,2,3 right ?

pls correct me if im wrong.

- krishna.sadula June 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

a[]={7, 8, 9, 10, 1, 2, 3, 4, 5, 6};
->rotate it 3 times
->step1(reverse array): 6 5 4 3 2 1 10 9 8 7
->step2 (reverse 0-3): 4 5 6 7 3 2 1 10 9 8 7
->step3 (reverse 3 - N): 4 5 6 7 8 9 1 0 1 2 3

- DJ June 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is an extension of method 2. Instead of moving one by one, divide the array in different sets
where number of sets is equal to GCD of n and d and move the elements within sets.
If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

Here is an example for n =12 and d = 3. GCD is 3 and

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

a) Elements are first moved in first set – (See below diagram for this movement)

ArrayRotation

arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b) Then in second set.
arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c) Finally in third set.
arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

- Anonymous June 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

N = N % len
reverse (len-N, len-1), reverse(0, len-1), reverse(N,len-1)

- gsmishra2011 June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorry mistake while typing answer, answer should be [4,5,6,7,0,1,2].

- someone June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just add all elements in queue once. Second step is to do deque and queue the same element n times third step is to just de queue all elements and put them back on array

- Digitalcapser June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Cant use extra space

- someone June 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void Main(string[] args)
        {
            int[] input = { 5, 6, 7, 4, 0, 1, 2 };
            int direction = -4;

            if (direction < 0)
            {
                input = reverse(input);
            }

            for (int i = 0; i < Math.Abs(direction); i++)
            {
                rotate(input);
            }

            if (direction < 0)
            {
                reverse(input);
            }
        }

        private static int[] reverse(int[] input)
        {
            int i = -1;
            int j = input.Length;
            int tmp = 0;
            while (i++<j--)
            {
                tmp = input[i];
                input[i] = input[j];
                input[j] = tmp;
            }

            return input;
        }

        private static void rotate(int[] input)
        {
            if (input == null || input.Length == 0 || input.Length == 1)
            {
                return;
            }

            int i = input.Length - 1;
            int tmp = input[i];
            while (i > 0)
            {
                input[i] = input[i - 1];
                i--;
            }

            input[i] = tmp;
        }

- Marcello Ghali June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Javascript

rotate = function(n) {
    return this.slice(n, this.length).concat(this.slice(0, n));
}

- Sunil Hari June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main(){
int ar[1000],length,i,rightshift,temp;
cin>>length>>rightshift;
for(i=0;i<length;i++)
cin>>ar[i];
rightshift%=length;
for(i=0;i<length/2;i++){
temp=ar[i];
ar[i]=ar[(i+rightshift)%length];
ar[(i+rightshift)%length]=temp;
}
for(i=0;i<length;i++)
cout<<ar[i]<<" ";
return 0;
}

- vishgupta92 June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void rrot(int a[],int size,int n)
{
int i,j,temp;
n%=size;
for(i=0;i<n;i++)
{
temp=a[size-1];
for(j=size-1;j>0;j--)
{
a[j]=a[j-1];
}
a[j]=temp;
}
}

- keshavfarmaha249 June 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Working version of java code with time complexity as O(n) and space complexity as O(1)

class Test_ArrayRotation
{
	public static void main(String args[])
	{
		int iArray[] = new int[] { 1, 2, 3, 4, 5 };
		System.out.println("Actual Array");
		PrintArray(iArray);
		RotateArray(iArray, 3);
		System.out.println("After Rotation");
		PrintArray(iArray);
	}
	
	public static void PrintArray(int inputArray[])
	{
		for(int i=1; i<=inputArray.length; i++)
			System.out.println(i + ")" + inputArray[i-1]);
		
		System.out.println("\n");
	}

	public static void RotateArray(int inputArray[], int iNoOfRotations)
	{
		int iIndex = 0;
		
		for(int i=0; i<inputArray.length; i++)
		{
			int iNewIndex = (iIndex + iNoOfRotations) % inputArray.length;
			int iValue = inputArray[iNewIndex];
			inputArray[iNewIndex] = inputArray[0];
			inputArray[0] = iValue;
			iIndex = iNewIndex;
		}
	}
}

Actual Array
1)1
2)2
3)3
4)4
5)5


After Rotation
1)3
2)4
3)5
4)1
5)2

- vbala1981 June 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I went down this road also and I wanted to like this solution. Unfortunately, it falls apart and gets cumbersome if array.length and rotate amount share common divisors (length = 9, rotate=3;length = 8, rotate=4; length = 8, rotate=2; ...)

I think that the triple reverse method is the way to go, provided the reverse logic is mature and runs in O(n/2) by swapping outer limits iterating in to mid.

- jyanchus June 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Cup {
public static void main(String[] args) {

int []arrayIn={0,1,3,4,5,6,7};
int []arrayOut;
int n=4;

arrayOut=new Cup().reverseNum(arrayIn,n);

for(int i=0;i<arrayOut.length;i++){
System.out.println(arrayOut[i]);
}
}

public int[]reverseNum(int []arrayIn,int n){
int len=arrayIn.length;
int []arrayOut=new int[len];

for(int i=n,j=0;i<len;i++,j++){
arrayOut[j]=arrayIn[i];
}
arrayOut[n-1]=arrayIn[n-1];

for(int i=0,j=n;i<n-1;i++,j++){
arrayOut[j]=arrayIn[i];
}
return arrayOut;
}
}

- vijay.lokhande.in June 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main(int argc, char** argv) {

int mat[7]={0,1,2,4,5,6,7};
int len=7;
int n=4;
int nindex=3;

for(int i=0;i<len;i++) cout<< mat[i]<<",";

cout << endl;
for(int i=0;i<nindex;i++)
{
mat[i]= mat[nindex+1+i]+mat[i];
mat[nindex+i+1]= mat[i]- mat[nindex+i+1];
mat[i]= mat[i]-mat[nindex+i+1];


}

for(int i=0;i<len;i++) cout<< mat[i]<<",";

return 0;
}

- Javad June 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArrayRotation
{
	public static void main(String[] args){
		
		int[] array = new int[] {1,2,3,4,5,6,7,8,9,10};
		
		System.out.println("*********************Right Rotation*********************");
		System.out.println("");
		printRightRotatedArray(array,2);
		System.out.println("*********************Left Rotation*********************");
		System.out.println("");		
		printLeftRotatedArray(array,2);
	}
	
	public static void printRightRotatedArray(int[] array, int rotation){
			int rotatedIndex = 0;
			int n = array.length;
		for(int i = 0; i < array.length; i++) {
			rotatedIndex = (i + rotation)%n;
			System.out.println(array[rotatedIndex]);
		}
	}
	public static void printLeftRotatedArray(int[] array, int rotation){
			int rotatedIndex = 0;
			int n = array.length;
		for(int i = 0; i < array.length; i++) {
			rotatedIndex = (i + (n - (rotation % n)))%n;
		/*	if(rotatedIndex >= array.length){
			
				rotatedIndex = rotatedIndex % array.length;
			} */
			System.out.println(array[rotatedIndex]);
		}
	}
}

- algeek June 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main(int argc, char **argv)
{
    std::cout << "Hello World" << std::endl;
	
	int n, a[50], rot, i;
	std::cout<< "Enter size of array \n";
	std::cin >> n;
	for (i = 0; i<n; i++)
	{
		std::cin >>a[i];
	}
	std::cout<<"Enter rotation number\n";
	std::cin>>rot;
	
	if (rot>n) return 0;
	
	if (rot == n) 
	//print org arr;
	{
		std::cout<<"\n";
		for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
	}
	for(i=0; i<(n-rot);i++)
	{
		//swap a[i] and a[i+rot]
		int temp = a[i];
		a[i]= a[i+rot];
		a[i+rot] = temp;
	}
	while(rot!=0)
	{
		//swap a[i] and a[i+rot]
		rot--;
		int temp = a[i];
		a[i]= a[n-1];
		a[n-1] = temp;
		i++;
		
	}
	//print
	std::cout<<"\n";
	for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
    return 0;
}

- Sunita June 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>


/* rotate an array by x
 * eg A[] = {1 2 3 4 5 6 7 8}
 * x=5
 * o/p A[] = {6 7 8 1 2 3 4 5}
 * O(n) = n*/
int main(int argc, char **argv)
{
    std::cout << "Hello World" << std::endl;
	
	int n, a[50], rot, i;
	std::cout<< "Enter size of array \n";
	std::cin >> n;
	for (i = 0; i<n; i++)
	{
		std::cin >>a[i];
	}
	std::cout<<"Enter rotation number\n";
	std::cin>>rot;
	
	if (rot>n) return 0;
	
	if (rot == n) 
	//print org arr;
	{
		std::cout<<"\n";
		for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
	}
	for(i=0; i<(n-rot);i++)
	{
		//swap a[i] and a[i+rot]
		int temp = a[i];
		a[i]= a[i+rot];
		a[i+rot] = temp;
	}
	while(rot!=0)
	{
		//swap a[i] and a[i+rot]
		rot--;
		int temp = a[i];
		a[i]= a[n-1];
		a[n-1] = temp;
		i++;
		
	}
	//print
	std::cout<<"\n";
	for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
    return 0;
}

- Sunita June 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.lang.Math;

public class RotateArray{

    public static void main(String[] args){
	
		int[] ar = new int[]{0, 1,2,4,5,6,7};
		int rotation = 4;
		System.out.println(Arrays.toString(ar));
		rotateBy(ar, rotation);
		System.out.println("Rotate Right by " + rotation + " : " + Arrays.toString(ar));
		rotateBy(ar, -1*rotation);
		System.out.println("Rotate Left by " + rotation + " : " + Arrays.toString(ar));
    }

    public static void rotateBy(int[] array, int n){

        int numberOfRotation = n % array.length;
	if ( numberOfRotation > 0 ){
            for( int i = 0 ; i < numberOfRotation ; i++){
                rotateRightByOne(array);
            }
        } else {
	    for( int i = 0 ; i < Math.abs(numberOfRotation); i++){
		rotateLeftByOne(array);
	    }
	}
    }

    private static void rotateRightByOne(int[] array){
        int first = array[0];
        for ( int i = 0; i < (array.length - 1) ; i++){
            array[i] = array[i+1];
        }
        array[array.length - 1] = first;
    }

    private static void rotateLeftByOne(int[] array){
        int last = array[array.length - 1];
        for ( int i = array.length - 1; i > 0 ; i--){
            array[i] = array[i-1];
        }
        array[0] = last;
    }
}

- adoba June 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

###Python Code
mylist=[0,1,2,4,5,6,7]
len=len(mylist)
N=4
for i in range(len-N):  ##using len-N for reverse Rotate.Use N for Normal Rotate..
    mylist.append(" ")
    mylist[len]=mylist[0]
    del mylist[0]
print mylist

- ankitpatel2100 June 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] rotateArray(int[] arr,int n) {
        int prev;
        int next;

        for(int i = 0; i < arr.length; i++){
            if(n == arr[i]){
                n = i;
                break;
            }
        }

        for(int i = 0; i < n; i++ ){
                prev = arr[i];
                next = arr[n + 1 + i];
                arr[i] = next;
                arr[n + 1 + i] = prev;
        }

        return arr;
    }

- Denys June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby implementation. Running time: O(nk). Space overhead: O(1).

def rotate(array, n)
  return [] if array.nil?
  return array if n <= 0 || array.length==0 || n % array.length == 0
  
  store_index=array.length-1
  
  (0...n).to_a.reverse.each do |element_index|
    for iter in (element_index...store_index)
      swap(array, iter,iter+1)
    end
    
    store_index -= 1
  end
  
  array
end

def swap(array, first_index, second_index)
  array[first_index]=array[first_index]^array[second_index]
  array[second_index]=array[first_index]^array[second_index]
  array[first_index]=array[second_index]^array[first_index]
  array
end

- Yev June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C Implementation
O(n) time complexity.
Number of iterations = n -1

#include <stdio.h>

int main(int argc, char **argv) {
    int k = 0, x = 0;
    int a[] = {-5,-4,-1,0,1,2,30,43,52,68,700,800,9999};
    int N = 0, R = 57; /*R = No of rotations*/
    int temp = 0, temp2  = 0, start = 0, iter = 0;

    x = 0;
    temp2 = a[x];

    N = sizeof(a) / sizeof(a[0]);
    for ( k = 0; k < N - 1; k++) {
        x = x + R;
        while ( x >= N ) {
            x = x - N;
        }
        temp = a[x];
        a[x] = temp2;
        temp2 = temp;
        if ( x == start ) {
            start = start + 1;
            x = x + 1;
            temp2 = a[x];
        }
        iter++;
    }
    a[start] = temp2;
    for ( k=0; k<N; k++) {
        printf(" %d", a[k]);
    }
    printf("\n");
    printf("Done in %d iteration\n", iter);
    return 0;
}

- cheersalam June 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
using namespace std;
void rotate(vector<int> & V, int N) {
	int n=V.size();
	int index=0;
	int val_old=V[index];
	int val_new;
	for(int i=0;i<n;i++) {
		val_new=V[(index+N)%n];
		V[(index+N)%n]=val_old;
		val_old=val_new;
		index=(index+N)%n;
	}
}
int main() {
	vector<int> V={0,1,2,4,5,6,7};
	rotate(V,4);
	for(int x:V)
		cout<<x;
}

- montreal6 June 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time complexity, O(1) memory

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void rotate(vector<int> & V, int N) {
	int n=V.size();
	int gcd=__gcd(N,n);
	for(int i=0;i<gcd;i++) {
		int index=i;
		int val_old=V[index];
		int val_new;
		for(int j=0;j<n/gcd;j++) {
			val_new=V[(index+N)%n];
			V[(index+N)%n]=val_old;
			val_old=val_new;
			index=(index+N)%n;
		}
	}
}
int main() {
	vector<int> V={0,1,2,4,5,6,7};
	rotate(V,4);
	for(int x:V)
		cout<<x;
}

- montreal6 June 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this is right (pseudo code):

int N; //Given N value
int ip_array[]; //input array
int output_array[] = new int[ip_array.size]; // 

for(int i=0;i<ip_array.size;i++){
	output_array[(i+N)%ip_array.size] = ip_array[i];
}

- iceman0bc July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do nothing, just the way to read the elements as they are in the rotated array as newArray[i] = originalArray [(i-1+N) mod L] where L is the length of the (original) array. In case of rotating N1, N2, ..., Nk times, then aaply the same formula with N = (N1 + N2 + ... + Nk) mod L.

- Quang Le September 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

namespace consoleApp
{
class Program
{

static void Main(string[] args)
{
int[] array = new int[] {0,1,2,3,4,5,6,7,8 };
Console.WriteLine("please enter number : ");
int input = Convert.ToInt32(Console.ReadLine());
int number = 0 ;

for (int k = 0; k < input; k++ )
{
number = array[0];
for (int i = 1, j = 0; i < array.Length; i++, j++)
{

array[j] = array[i];

}
array[array.Length - 1] = number;
}
Console.WriteLine("Here is rotate : ");
for (int i = 0; i < array.Length; i++ )
{
Console.Write("{0}",array[i]);
}
Console.ReadKey();
}
}
}

- Anonymous March 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

namespace consoleApp{
class Program{
static void Main(string[] args){
int[] array = new int[] {0,1,2,3,4,5,6,7,8 };
Console.WriteLine("please enter number : ");
int input = Convert.ToInt32(Console.ReadLine());
int number = 0 ;
for (int k = 0; k < input; k++ ){
number = array[0];
for (int i = 1, j = 0; i < array.Length; i++, j++)
{ array[j] = array[i];}
array[array.Length - 1] = number; }
Console.WriteLine("Here is rotate : ");
for (int i = 0; i < array.Length; i++ )
{Console.Write("{0}",array[i]); }
Console.ReadKey();}}}

- Anonymous March 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void Rotate(int[] inp, int rotate)
    {
        if(null == inp || inp.Length == 0)
            return;
        int len = inp.Length;
        int si=0;
        int hop = rotate % len;
        int temp1 = inp[si];
        int count = 0;
        while(count < len)
        {
            si = si + hop;
            if( si >= len)
                si = si - len;
            int temp2 = inp[si];
            inp[si] = temp1;
            temp1 = temp2;
           
            count++;
        }
        for(int index = 0; index< len;index++)
            Console.WriteLine(inp[index]);
    }

- Rahul Vishnoi May 24, 2016 | Flag Reply


Add a Comment
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.

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