## Microsoft Interview Question

Software Engineer / Developersit can not end up like : E-D-C-A-B no matter how many procedure were repeated

Because procedure does not change the order of those 5 boxes, it just like move the header pointer in the looped link list

wrong answer ...

following formula gives the index of first element after n rotations,

total = total number of elements in array

n = number of rotations

(total - ((n % total) - 1))

for this problem, there are 3 iterations and each iteration rotates the array by 3, so

(5 - (((3 * 3) % 5) - 1)) = 2, the top element is 'B'

so, the middle element is 'D'.

so by your method after 2 rounds top element should be B

because as per your formula:(5-(((2*2)%5)-1)) =2 thus the top element is B but its actually E so better check it

but for each iteration there will be 3 rotations

so, it will be (5-(((3*2)%5-1)) = 5,so top element will be E after 2 rounds

so i think Big N's formula is right

Iteration 1: ABCDE becomes CDEAB

Iteration 2: CDEAB becomes EABCD

Iteration 3: EABCD becomes BCDEA

D is in the middle

Initially ABCDE

Next CDEAB Next EABCD Next BCDEA...

Hence order is E then third element from E going upwards i.e. B

then third element from B i.e. D

then third element from D i.e. A

then third element from A i.e. C

then third element from C i.e. E (all these counting based on original order)

and can be generalized so on.

The simplified solution is to do circular right shit 3 times multipled by number of iterations

>>>2*3 and extract the middle element.

Programmatically you would need extra Stack and a Queue

Algorithm would be like the following

S2.push(S1.pop());

S2.push(S1.pop());

Q2.Enqueue(S1.pop());

Q2.Enqueue(S1.pop());

Q2.Enqueue(S1.pop());

S1.Push(S2.pop());

S1.Push(S2.pop());

S2.push(Q2.dequeue());

S2.push(Q2.dequeue());

S2.push(Q2.dequeue());

S1.Push(S2.pop());

S1.push(S2.pop());

S1.push(S2.pop());

Repeat the above procedure n times for n iterations. Implement the stack with an array has backing store and get the middle element.

ok here is the series I found.

- Aditya March 23, 2012it is only possible when n is odd her in your case it is 5.

(n+1)/2 , n, (n-1)/2, n-1, (n-3)/2, n-2, .............and goes on like this

so 0th iteration C

so 1th iteration E

so 2th iteration B

so 3th iteration D

so 4th iteration A

and repeats the same .......

FYI: stack revert backs to original after n iterations.