Amazon Interview Question: you have array with n element... | Glassdoor.ie

## Interview Question

Software Engineer Interview Dublin, Co. Dublin

# you have array with n elements. How would you do circular

shift of k positions? Time and space complexity?
Tags:
algorithm

2

Make a circular linklist, and move headpointer K position to do K shifts. It's O(n) time complexity. Space is contant. (circular link list).

Praveen Chettypally on 11 Jan 2011
1

Well, space isn't constant because you took an array and then copied it somehow to a linked list. Remember, you were given an array?

If I understand the question correctly, they're asking to do a circular shift of some range of values, like the first k values in an array of length n? So if you wanted to shift right,

temp = array[k]
from index=k to 1
array[index] = array[index-1]
array[0] = temp

this would be O(k)? I mean, it would take k steps, but maybe it's somehow still O(n)

sarah on 23 Jan 2011
2

oh, sorry, I misunderstood. Not k values, move everything k positions. Praveen Chettypally's answer works but the space complexity would be O(n) since there is a fully copy of the list?

The simplest would probably be to make another array and copy in, starting at the (n-k)th element, going to the end, then starting at the beginning. A second array would probably be a better option than a completely different data structure.

What if it has to be done in place? is there an O(n) solution?

sarah on 23 Jan 2011
2

alright -
http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position

shiftArray( theArray, M ):
size = len( theArray )
assert( size &gt; M )
reverseArray( theArray, 0, size - 1 )
reverseArray( theArray, 0, M - 1 )
reverseArray( theArray, M, size - 1 )

O(n) with no extra storage. Wish I could have thought of that one myself...

sarah on 23 Jan 2011
0

I beieve this does the trick too:

public static String shiftArray(char[] inputArray, int shiftLen)
{
assert(inputArray != null);
int length = inputArray.length;
assert(length &gt; shiftLen);

int moves = 0, from= 0, to = 0;
char next, last;

to = (from + shiftLen) % length;
next = inputArray[from];

while(moves &lt; inputArray.length)
{
last = inputArray[to];
inputArray[to] = next;

next = last;
from = to;
to = (from + shiftLen) % length;

moves++;
}
return String.valueOf(inputArray);
}

CortexCompiler on 6 Mar 2011
0

I tried the above function - shiftArray and the looks is not working:

shiftItemsFromList class:

class shiftItemsFromList{

public static String shiftArray(char[] inputArray, int shiftLen)
{
assert(inputArray != null);
int length = inputArray.length;

assert(length &gt; shiftLen);

int moves = 0, from= 0, to = 0;
char next, last;

to = (from + shiftLen) % length;
next = inputArray[from];

while(moves &lt; inputArray.length)
{
last = inputArray[to];
inputArray[to] = next;

next = last;
from = to;
to = (from + shiftLen) % length;

moves++;
}
return String.valueOf(inputArray);
}

}

Part of the main function:

System.out.println("Circle Shift N size array for M possitions:");

char [] array = {'a', 'b', 'c', 'd', 'e', 'f'};

shiftItemsFromList sh = new shiftItemsFromList();

String s = sh.shiftArray(array, 2);

System.out.println("Print the Circle Shift N size array: " + s);

System.out.println("DONE");

OUTPUT:

Circle Shift N size array for M possitions:
Print the Circle Shift N size array: cbadaf
DONE

ovymura on 8 Aug 2011