Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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.
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
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}
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
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.
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
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;
}
#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;
}
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;
}
}
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;
}
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]);
}
}
}
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;
}
#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;
}
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;
}
}
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
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;
}
#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;
}
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;
}
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();
}
}
}
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();}}}
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]);
}
1. reverse the array from 0 to n-1
- Mo June 10, 20152. reverse the array from n- length
3. reverse the whole array (from 0 - length)