abcd
BAN USER
- 26
0of 2 votes
AnswersGiven 13 cards only of one suite say spade. You have to write algorithm to arrange the cards in stack such that you put cards in sequencial order at bottom & remove top you should get cards in sequencial order.
- abcd in United States
forex:- put first top card at bottom now remove the topmost should be one of spade.
-put top two cards one by one at the bottom, now remove the topmost should be two of spade.
- similarly do three time.. four time .... and so on till king.
Jack=11, queen=12, king=13
time complexity should be nlogn
Ans should be like this:
4, 1, K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8
From this sequence put top one card at bottom & now top card should be number 1. as below
1, K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8, 4 - top one card placed at bottom
K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8, 4- top card is 1 which is removed
Now do same with two cards as below
2, 10, 6, 7, 3, 5, Q, 9, 8, 4, K, J- top two placed at bottom.
Now topmost is 2nd number so remove it
10, 6, 7, 3, 5, Q, 9, 8, 4, K, J
do same for 3, 4 ... till K
3, 5, Q, 9, 8, 4, K, J, 10, 6, 7
5, Q, 9, 8, 4, K, J, 10, 6, 7
.
.
The card we remove should be in 1 to k sequence i.e. 1,2,3,4,5,6,7,8,9,10,J,Q,K
But here we need to find how to form the sequence in NlogN i.e.
Ans should be like this:
4, 1, K, J, 2, 10, 6, 7, 3, 5, Q, 9, 8| Report Duplicate | Flag | PURGE
Microsoft Algorithm
Someone, I like your idea, better than n square so I upvoted it. However I was wondering if there are n such card which may be thousands to millions & for that case every time the reminder coming as divisor-1, which would lead to n^2 solution. So is there any way of we can take array of n number & place from 1 to n by doing some mathematical calculation which is constant time (just a thought not sure we can do this). like for first 3 numbers as below
initially idx = 0
for num =1, idx = (idx+num+1)%13 =2
for num = 2, idx = (idx+num+1)%13 = 5
for num = 3, idx = (idx+num+1)%13 = 9
after this things starting messed up. so is there way to find correct formula so that this can be done in O(N)
idx 1 2 3 4 5 6 7 8 9 10 11 12 13
pos x 1 x x 2 x x x 3 x x x x
wrong check these prime numbers with gap less than 6, 41 43 47 53 59 61 67 71
- abcd July 23, 2014