Synopsys R&D Interview Question Senior Software Development Engineers
1of 1 voteProgram to rotate an array
Country: India
You still have to traverse the array 3 times! You can easily do this with one traversal.
There are NO traversals here. You just swap the elements in the array during reversal. The maximum number of swap operations are N for an array of size N and this is a linear time algorithm.
I was counting each call of std::reverse as a traversal, but after understanding what std::reverse is, I can see how it is n swaps.
However, this answer would be unacceptable in an interview because they usually prohibit using convenience functions and want to see you do the actual element swaps.
Then you can also provide the reverse routine :)
static void reverse(int *arr, int start, int end) {
if (arr == 0) return;
while (start < end) {
int tmp = arr[start];
arr[start++] = arr[end];
arr[end--] = tmp;
}
}
Look, the point here is that this is an elegant algorithm, which I've learned from Programming Pearls and I wanted to share. You can google and find even more different solutions. For instance, I can even write another C/C++ solution with memmove and memcpy to rotate any array in O(1) time with some extra storage.
Why did people vote down this solution?
It's nice and elegant :)
BTW Programming Pearls is a great book.
Rotating to the right and rotating to the left are different. However, the code is easy.
public <T> void rotateRight(T[] t, int start, int end) {
if (start < end) {
T last = t[end];
for (int i = end; i > start; i--) {
t[i] = t[i - 1];
}
t[start] = last;
}
}
public <T> void rotateLeft(T[] t, int start, int end) {
if (start < end) {
T first = t[start];
for (int i = start; i < end; i++) {
t[i] = t[i + 1];
}
t[end] = first;
}
}
No, they're exactly the same. Rotating 1 to the right is the same as rotating n-1 to the left.
@yokuyuki
>> No, they're exactly the same. Rotating 1 to the right is the same as rotating n-1 to the left.
But rotating 1 to the right is not the same as rotating 1 to the left.
public void CircularArrayRotation(int[] arr, int sublen)
{
int[] brr = new int[sublen];
int i, k=0, len = arr.Length;
//copy the part of 1st array that needs to be rotated (ideally the size of sublen from the last element of the array)
for (i = len-sublen; i < len; i++)
{
brr[k] = arr[i];
k++;
}
//Right shift the elements so that they are now stored from the last element of the array
for (i = len - sublen - 1; i >= 0; i--)
{
arr[i + sublen] = arr[i];
}
//Now start adding the new array's elements to the original array (from the 0th index onwards) to get the final output
for (i = 0; i < sublen; i++)
{
arr[i] = brr[i];
}
//print the resultant array
for (i = 0; i < len; i++)
{
Console.Write(arr[i] + ",");
}
}
Hi,
beside the edge cases, what do you think of this solution?
Regards,
Gio
package algorithm.arrayrotation;
public class ArrayRotation {
public int[] rotateLeft(int[] array, int numRotation) {
if (numRotation < 0)
return rotateRight(array, -numRotation);
if (array == null) {
return null;
}
if (array.length == 0) {
return new int[0];
}
if (array.length == 1) {
return new int[] { array[0] };
}
int[] newArray = new int[array.length];
int effectiveRotation = numRotation % array.length;
for (int i = 0; i < array.length; i++) {
newArray[i] = array[(i + effectiveRotation) % array.length];
}
return newArray;
}
public int[] rotateRight(int[] array, int numRotation) {
if (numRotation < 0)
return rotateLeft(array, -numRotation);
if (array == null) {
return null;
}
if (array.length == 0) {
return new int[0];
}
if (array.length == 1) {
return new int[] { array[0] };
}
int[] newArray = new int[array.length];
int effectiveRotation = numRotation % array.length;
for (int i = 0; i < array.length; i++) {
newArray[i] = array[(array.length - effectiveRotation + i)
% array.length];
}
return newArray;
}
}
If positive k is rotating to the right and negative k is rotating to the left, you can just adjust them all to rotate to the right by taking the modulus of k by the length of the array. Below is my Python version:
def rotate(arr, k):
k %= len(arr)
if k != 0:
current = 0
store = arr[current]
for i in range(len(arr)):
current = (current + k) % len(arr)
arr[current], store = store, arr[current]
return arr
Here's an in-place right-rotate which needs only constant space and N time.
public static void rotateRight(int [] arr, int rotateBy)
{
//If the array is <= 1, it's already 'rotated'
if(arr.length <= 1)
return;
int temp = arr[0];
//If the rotateBy is larger than array length, we need to get it into range
while(arr.length-rotateBy < 0)
rotateBy -= arr.length;
//If the rotate equals the length of array or 0, we're not actually doing any
//rotating
if(arr.length - rotateBy == 0 || rotateBy == 0)
return;
//Rotate the element at 0
arr[0] = arr[arr.length-rotateBy];
int at = rotateBy;
//While we're not back at 0, keep rotating elements
while(at != 0)
{
int newTemp = arr[at];
arr[at] = temp;
temp = newTemp;
at += rotateBy;
at %= arr.length;
}
//In the case where len % rotateBy == 0, we need to take care of
//the 'odd' cases, since those will be skipped initially
if(arr.length % rotateBy == 0 && rotateBy > 1)
{
temp = arr[1];
arr[1] = arr[arr.length-rotateBy+1];
at = rotateBy+1;
while(at != 1)
{
int newTemp = arr[at];
arr[at] = temp;
temp = newTemp;
at += rotateBy;
at %= arr.length;
}
}
}
This is a simple java function for rotating an array in clickwise by n
public static void RotateArray(int[] arr, int n)
{
int size=arr.length;
ArrayList<Integer> al=new ArrayList<Integer>(size);
for (int i=size-1; i> size-1-n; i-- )
{
al.add(arr[i]);
}
for (int j=0; j < size-n ; j++ )
{
al.add(arr[j]);
}
System.out.print("rotated array: ");
for (int k=0; k < al.size(); k++)
{
System.out.print(al.get(k));
}
}
oOZz's code is nice and elegant.
Actually it takes 3n assignments. (Swap cost 3 assignments)
I can provide an algorithm which takes about 1n assignments. (Actually, it takes n + 2 * gcd(n,k) assignments.)
And the space remains O(1).
Let me state this question in clarified version:
Input:
1. An array A of size n
2. A rotate number k. Assume k < n.
3. Direction: For simplification, assume we always rotate to left. If we need to rotate to right, just rotate to left n-k element.
Output:
Array A after circular rotate for k elements to left.
Idea:
Since I want to use only O(1) space and n assignment. So when I move element A[j] to position 0, I have to put the correct element to the hole, and so on. This procedure make a circular movement. There is an example:
let A = {0, 1, 2, 3, 4, 5, 6, 7, 8};
let k = 6;
0 1 2 3 4 5 6 7 8 0<-6<-3<-0
6 0 3 moved elements after circular movement
The above action put all element which are multiples of gcd(n,k) to correct position.
And then, I repeat the above action, but start from A[1] to A[gcd(n,k)-1]. There is an example.
0 1 2 3 4 5 6 7 8 original
6 0 3 first cicular movement
7 1 4 second cicular movement
8 2 5 third cicular movement
-----------------
6 7 8 0 1 2 3 4 5 after 3 cicular movement
Here is the code in C++
void RotateArray(int A[], unsigned n, unsigned k){
int gcd = GCD(n,k);
for (int i=0; i<gcd ; i++ ){ //circular move from 0 to gcd-1
int tmp=A[i], j, lastJ=i;
for (j=i+k; j!=i ; j=(j+k)%n){
A[lastJ] = A[j]; //1 assingment vs. Swap cost 3 assingment
lastJ = j;
}
A[lastJ] = tmp; //tmp cost another 2 assingment
}
}
package CrackingCodingInterview;
public class ArrayCircularShift {
public static void main(String[] args) {
int origArray[] = {3,2,1,4,5,6};
// right shift by k
int k = 3;
int size = origArray.length;
k = k % size;
int rightShiftedArray[] = new int[size];
//right shift
for(int i =0 ;i < size ; i++)
{
int pos = i + k;
if(pos < size)
rightShiftedArray[pos] = origArray[i];
else
rightShiftedArray[pos%size] = origArray[i];
}
System.out.println("right shifted array");
for(int ele : rightShiftedArray)
System.out.println(ele);
//left shift by k
int[] leftShiftedArray = new int[size];
for(int i=0; i < size ; i++)
{
int pos = i - k;
if(pos >= 0)
leftShiftedArray[pos] = origArray[i];
else
leftShiftedArray[pos + size] = origArray[i];
}
System.out.println("left shifted array");
for(int ele : leftShiftedArray)
System.out.println(ele);
}
}
package CrackingCodingInterview;
public class ArrayCircularShift {
public static void main(String[] args) {
int origArray[] = {3,2,1,4,5,6};
// right shift by k
int k = 3;
int size = origArray.length;
k = k % size;
int rightShiftedArray[] = new int[size];
//right shift
for(int i =0 ;i < size ; i++)
{
int pos = i + k;
if(pos < size)
rightShiftedArray[pos] = origArray[i];
else
rightShiftedArray[pos%size] = origArray[i];
}
System.out.println("right shifted array");
for(int ele : rightShiftedArray)
System.out.println(ele);
//left shift by k
int[] leftShiftedArray = new int[size];
for(int i=0; i < size ; i++)
{
int pos = i - k;
if(pos >= 0)
leftShiftedArray[pos] = origArray[i];
else
leftShiftedArray[pos + size] = origArray[i];
}
System.out.println("left shifted array");
for(int ele : leftShiftedArray)
System.out.println(ele);
}
}
Hi,
My code to rotate an array anticlockwise by 'd' times.
Divide the array into 2 parts:-
A[] = [0...d-1] and B[] = [d...n-1]
Steps:-
1. reverse array A.
2.reverse arrayB
3.Reverse the whole array AB.
Code:-
package Arrays.Rotations;
import java.util.Scanner;
public class RotateArrayAnticlockwise {
public static void main(String... a) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter the value of n");
int n = scan.nextInt();
int[] arr = new int[n];
System.out.println("Elements in an array:");
for (int i = 0; i < arr.length; i++) {
arr[i] = scan.nextInt();
}
System.out.println("Enter the value of d:");
int d = scan.nextInt();
rotateArrayAnticlockwiseByReverseMethod(arr, d, n);
scan.close();
printArray(arr);
}
private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
private static void rotateArrayAnticlockwiseByReverseMethod(int[] arr, int d, int n) {
reverse(arr, 0, d - 1);
reverse(arr, d, n - 1);
reverse(arr, 0, n - 1);
}
private static void reverse(int[] arr, int start, int end) {
int temp;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}
0. Let's say your original array is A = {1, 2, 3, 4, 5, 6, 7, 8} and you wanna rotate by k = 2
1. Reverse the whole array => A' = {8, 7, 6, 5, 4, 3, 2, 1}
2. Reverse the first k elements of A' => A' = {7, 8, 6, 5, 4, 3, 2, 1}
3. Reverse the remaining elements of A' starting from the kth element => A' = {7, 8, 1, 2, 3, 4, 5, 6}
4. return A'
The reverse operation is O(1) space, so this program is O(n) time and O(1) space
Here is the code in C++
template <typename T> void rotate_array(vector<T>& A, int k) { k %= A.size(); std::reverse(A.begin(), A.end()); std::reverse(A.begin(), A.begin() + k); std::reverse(A.begin() + k, A.end()); }This algorithm is from Programming Pearls!
- oOZz June 22, 2013