Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
public static void circularShift(int[] inputArray, int shiftSize) {
if (inputArray.length <= 1) {
System.out.println("Array must have more than one integer.");
} else {
System.out.println("Before shift:--");
for (int temp : inputArray) {
System.out.println(temp);
}
int i = 0;
int[] outputArray = new int[inputArray.length];
while (i < inputArray.length) {
int k = (shiftSize + i) % inputArray.length;
outputArray[k] = inputArray[i];
i++;
}
System.out.println("After shift:--");
for (int temp : outputArray) {
System.out.println(temp);
}
}
}
}
public static void circularShiftToRightInPlace(int[] inputArray, int shiftSize) {
int length = inputArray.length;
if (inputArray.length <= 1) {
System.out.println("Array must have more than one integer.");
} else {
System.out.println("Before shift:--");
for (int temp : inputArray) {
System.out.println(temp);
}
int start = 0;
int end = length - (shiftSize % length) - 1;
circularShiftToRightInPlace(inputArray, start, end);
circularShiftToRightInPlace(inputArray, end + 1, inputArray.length - 1);
circularShiftToRightInPlace(inputArray, 0, inputArray.length - 1);
System.out.println("After shift:--");
for (int temp : inputArray) {
System.out.println(temp);
}
}
}
private static void circularShiftToRightInPlace(int[] inputArray, int start, int end) {
int i = start;
int j = end;
while (i < j) {
int temp = inputArray[i];
inputArray[i] = inputArray[j];
inputArray[j] = temp;
i++;
j--;
}
}
// IN-PLACE
C++ implementation with O(n) time and O(1) space using tail recursion.
#include <iostream>
#include <iterator>
static void rotate_right(int arr[], size_t len, int n)
{
n = n % len;
if (n == 0)
return;
for (size_t i = len - n, j = 0; i < len; i++, j++) {
std::swap(arr[i], arr[j]);
}
return rotate_right(arr + n, len - n, n);
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6};
rotate_right(arr, sizeof(arr)/sizeof(arr[0]), 2);
std::copy(std::begin(arr), std::end(arr),
std::ostream_iterator<int>(std::cout, " "));
return 0;
}
Good algorithm!
But if the size of the given array is very huge, like 1000000, and under the worst situation, like this
rotate_right(arr, sizeof(arr)/sizeof(arr[0]), 1);
how to solve the stack overflow problem?
@yuxiaohui78 There's no stack overflow problem with this algorithm. The rotate_right function uses tail recursion, so this is optimized as a regular loop by the compiler, preventing the use of stack for each call. You can use an array of any size (limited by the maximum value of size_t) and it will work.
int[] reverse(int[] A, int shifts)
{
int[] temp = new int[A.length * 2];
System.arrayCopy(A, 0, temp, 0, A.length);
System.arrayCopy(A, 0, temp, A.length, A.length);
shifts = shifts % A.length;
int[] result = new int[A.length];
System.arrayCopy(temp, shifts - 1, result, 0, A.length);
}
Explanation: temp array is A + A. And temp.length = 2*A.length.
e.g. A = [4,3,2,5] then temp = [4,3,2,5,4,3,2,5].
Now select the array between (including) (shifts - 1) and including shifts - 1 + A.length - 1.
The catch is to do it in place. No use of temporary array.
void rightShift(int[] array, int n)
{
for (int shift = 0; shift < n; shift++)
{
int first = array[array.length - 1];
System.arraycopy( array, 0, array, 1, array.length - 1 );
array[0] = first;
}
}
int size = array.Length;
int i1 = 0;
int i2 = size - shift;
while (i1 < size-1)
{
swap(i1, i2, array);
i1++;
i2++;
i2 = i2 == size ? size - shift : i2;
}
public class CircularShiftArray {
public static void main(String[] args) {
int[] array = {2,5,1,8,10};
shiftArray(array,2);
}
private static void shiftArray(int[] array, int n){
int length = array.length;
int i =0,temp = array[0],temp2 =0, count = 0;
while(count!=length){
int newIndex = (i+n)%length;
temp2 = array[newIndex];
array[newIndex] = temp;
temp = temp2;
count++;i = newIndex;
}
}
}
best sol would be if a swap gets minimized and in one shot the elements gets reolcation to right position.
for example : if we have array of size 6 and 4 shifts has to be done then
a[(i+s)%n] = a[i]
a[0] =a[4]
a[4] = a[2]
a[2] =a[0]
and so on
number of actual shift s = k % n
for( i=0 ; i < n/3 ; i++)
{
temp = a[i];
for(j=1; j < 4 ; j++)
{
next = ( i + j*s)%n
//swap the contents of a[next] and temp
temp1 = a[next]
a[next] = temp
temp = temp1
}
}
O(N) time, O(N) space... determine new position in array for bucket, move into temporary array, determine for next bucket etc...
int main()
{
int arr[10] = {1,2,3,4,5,6,7,8,9,0};
int *tempArr = new int[ sizeof(arr) / sizeof(int)];
int n;
cout << "Enter the number of shifts you would like to occur: ";
cin >> n;
for( int x = 0; x< (sizeof(arr) / sizeof(int)); x++)
{
int newPosition = (n + x ) % (sizeof(arr) / sizeof(int));
tempArr[newPosition] = arr[x];
}
delete[] tempArr;
tempArr = NULL;
}
The O(N) time and O(1) space looks optimal for small tables
void shiftArraySmall(int arr[], int aSize, int n)
{
if (aSize == 0 || n == 0) return;
int lastStart = 0;
int lastIdx = 0;
int saved = arr[0];
for(int i = 0; i < aSize; ++i)
{
int nextIdx = (lastIdx + n) % aSize;
if (nextIdx == lastStart)
{
arr[nextIdx] = saved;
lastStart = lastIdx = (lastStart + 1);
saved = arr[lastStart];
}
else
{
int temp = arr[nextIdx];
arr[nextIdx] = saved;
saved = temp;
lastIdx = nextIdx;
}
}
}
but it's actually very bad for very large tables and relatively large n. Why? Because if n*sizeof(int) is larger than CPU cache this algo would generate only random memory accesses which can kill any algo. The modulo operation is expensive as well.
void shiftArrayLarge(int arr[], int aSize, int n)
{
if (aSize == 0) return;
n %= aSize; //make sure it's smaller than aSize
if (n == 0) return;
int tmpArr[n];
memcpy(&tmpArr[0], &arr[aSize - n], n * sizeof(arr[0]));
memmove(&arr[n], &arr[0], (aSize - n) * sizeof(arr[0])); //can implement better than that with reverse copy
memcpy(&arr[0], &tmpArr[0], n * sizeof(arr[0]));
}
#include <iostream>
#include <stdio.h>
#define S 5
void show(int* w, int size)
{
printf("-------------\n");
for (int e = 0; e < size; ++e)
printf("%d \n", w[e]);
}
int main()
{
int tab[S] = { 1, 2, 3, 4, 5 };
int shift = 2;
int* w = new int[shift];
for (int k = 0; k < shift; ++k)
w[k] = tab[S - k - 1];
show(w, 2);
int tmp = S - shift - 1;
int dek = S - 1;
for (int z = tmp; z >= 0; --z)
tab[dek--] = tab[z];
int k = 0;
for (int e = shift - 1; e >= 0; --e)
tab[k++] = w[e];
show(tab, 5);
system("pause");
return 0;
}
#include <iostream>
#include <stdio.h>
#define S 5
void show(int* w, int size)
{
printf("-------------\n");
for (int e = 0; e < size; ++e)
printf("%d \n", w[e]);
}
int main()
{
int tab[S] = { 1, 2, 3, 4, 5 };
int shift = 2;
int* w = new int[shift];
for (int k = 0; k < shift; ++k)
w[k] = tab[S - k - 1];
show(w, 2);
int tmp = S - shift - 1;
int dek = S - 1;
for (int z = tmp; z >= 0; --z)
tab[dek--] = tab[z];
int k = 0;
for (int e = shift - 1; e >= 0; --e)
tab[k++] = w[e];
show(tab, 5);
delete[] w;
system("pause");
return 0;
}
public static void shiftRight( int[] arr, int shift ){
if( arr == null ){
throw new IllegalArgumentException("NULL 'arr' parameter passed");
}
if( arr.length < 2 ){
return;
}
if( shift % arr.length == 0 ){
return;
}
int index = 0;
int prev = arr[0];
do{
int newIndex = (index+shift) % arr.length;
int temp = arr[newIndex];
arr[newIndex] = prev;
prev = temp;
index = newIndex;
}
while(prev != arr[index]);
}
public static void Shift(int[] array, int n)
{
if (array.Length <= 1 || n == 0)
{
return;
}
n = n % array.Length;
int i = 0;
int k;
int lastItem, temp;
lastItem = array[0];
while (true)
{
k = (i + n) % array.Length;
temp = array[k];
array[k] = lastItem;
lastItem = temp;
i = k;
if (i == 0)
{
break;
}
}
}
public static void main(String[] args) {
int[] array = {2,5,1,8,10,12,4,15};
shiftArray(array,3);
MyUtilities.PrintArray(array);
}
public static void Reverse(int[] A,int first, int last) {
while(first < last){
MyUtilities.Swap(A, first, last);
first++;last--;
}
}
private static void shiftArray(int[] array, int n){
if(n<array.length && n >0){
Reverse(array,0,array.length-1);
Reverse(array,0,n-1);
Reverse(array,n,array.length-1);
}
}
c++
#include <memory.h>
static void shiftArray(int shift, int arr[], int length )
{
int *tmp = new int[length];
memcpy(tmp, arr + (length-shift), sizeof(int)*shift);
memcpy(arr + shift, arr, sizeof(int)*(length-shift));
memcpy(arr, tmp, sizeof(int)*shift);
}
int main(int argc, char* argv[])
{
int arr[] = {1,2,3,4,5,6,7,8,9};
shiftArray(3, arr, sizeof(arr)/sizeof(*arr));
return 0;
}
private static void CircularRightShiftForArrayOfIntegers(int[] inputArray, int shift)
{
int[] outputArray = new int[inputArray.Length];
int i = 0;
while (i != inputArray.Length)
{
if (i + shift == inputArray.Length)
{
shift = -i;
}
outputArray[i + shift] = inputArray[i];
i++;
}
Console.WriteLine(string.Join(" ", outputArray));
}
How about this: jump with step n, e.g. starting from index 0, n, 2*n, .... and swap their values. Do that n times with starting points in n first elements. O(N) time, O(1) memory.
public class shiftn {
public static void shiftRight(int[] A, int shift)
{
for (int i = 0; i<shift; i++)
{
int j = i;
int temp = A[j%A.length];
while (j< A.length + i)
{
int temp2 = A[(j+shift)%A.length];
A[(j+shift)%A.length] = temp;
j = j+shift;
temp = temp2;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A = {1,2,3,4,5,6,7,8,9};
System.out.println("before");
for (int i = 0; i<A.length;i++)
{
System.out.println(A[i]);
}
shiftRight(A,3);
System.out.println("after");
for (int i = 0; i<A.length;i++)
{
System.out.println(A[i]);
}
}
}
public class CircShift {
public static void main(String[] args){
int[] array=new int[]{0,1,2,3,4} ;
int[] newarray=new int[5];
int shiftsize=2;
for(int i=0;i<array.length;i++){
newarray[(i+shiftsize)%array.length]= array[i];
}
for(int i=0;i<array.length;i++){
System.out.print(newarray[i]);
}
}
}
InPlace
void circularshift(int A[], int N, int sh)
{
sh = sh% N;
int cur = N - sh - 1; // it needs to move in N-1 th position
int dest = N - 1;
int DatatoMove = A[cur];
int count = 0;
while(count<N)
{
int temp = A[dest];
A[dest] = DatatoMove;
DatatoMove = temp;
cur = dest;
dest = (cur + sh) % N;
count++;
}
}
- Anonymous November 10, 2013