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.