Amazon Interview Question for Software Engineer / Developers

• 3

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)

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

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.

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

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

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

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}

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)

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

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

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

Cant use extra space

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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.