Microsoft Interview Question
Country: United States
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
@abcd I believe the worst case for the modulus would be around n/2 at which point you would need to rotate about n/2 times. But unless you can prove better than n/2 then it does end up being n^2.
I considered the approach you suggest, but it doesn't account for removing the cards does it?
@someone, true reminder is anything so difficult to prove, but definitely efficient.
For My approach I was just trying leaverage some other methods like Josephus Problem, but looks like it is not possible, so I want drop my approach.
heap data structure will be the data structure i would choose. maintain highest card on top, and each time you pop the root node, the biggest one will become to top one. NLogN to create the heap structure.
correct me if I'm wrong since the first description of the problem was not that clear. if I put the X top most cards from the button, i should pop the number of the card according of the number i just input right?
for exaple, I put the top 4 cards, and i should pop 4 of spade right? i believe that the structure already has the missing cards. am i right? If so, then the structure won't be a heap obviously, but can be done fairly easy with a balanced binary tree and output the cards after doing a search throughout it.
can't we use doubly linked list.Once i reached the last node .I'll try to see if it is the min element
and if it is .
8<->9<->7<->K<->6<->3<->4<->1
Go back to 4 and delete the element. and print it
8<->9<->7<->K<->6<->4 . now since 4 is not the min element . First Go back and now my pointer will point to 3. and Remove the element and add to the head of the list i.e
4<->8<->9<->7<->K<->6<->3
now keep repeating it for the Element which are not the min. And stop when only king remains.
But I am not sure about the time. Can somebody tell me if this approach is correct or not.if it is what will be the time complexity
thanks in advance
l = [];
for x in range(13):
i = (13-x)%(x+1);
l.insert(0,13-x);
l = l[-i:] + l[:-i];
print l
seems it just O(n)
you can compute the index of each card from card value(n in above formula). then just put the card into corresponding slot.
Take an array of 13 elements set to zero.
for each n (n < 7) skip n zeros and set the next field to n. for n > 6 skip 12-7 zeros and set the next zero element to the value.
-- After removing 6 elements there wont be more than 6 elements to move down to place the last element. (6+6+1).
I think this is the modified Josephus permutation problem with the k being not constant. If k is supposed to be constant it is linear solution problem. We need to use augmented balanced binary search tree with extra field (this field is left sub-tree size and right sub-tree size) in it to get the best next indexed empty slot in the array. This is really very interesting problem. So the complexity analysis goes like this.
First the construction of the augmented binary search tree for all 13 elements in O(nlogn). Then we iterate in loop for each element, we pick the empty slot of particular index from BST which is O(logn). So for n elements it is O(nlogn). I guess this is the solution for it.
Use List structure in java to avoid rotation
public int[] arrangeCards(int n) {
List<Integer> list = new ArrayList<Integer>();
int pos = 0;
for(int i = n ; i > 0; i--) {
list.add(pos, i);
pos -= i % (n - i + 1);
pos = (pos + (n - i + 1)) % (n - i + 1);
}
int[] array = new int[list.size()];
for(int i = 0; i < list.size(); i++) {
array[i] = list.get(pos);
pos = (pos + 1 + n) % n;
}
return array;
}
#include "stdio.h"
#include "stdlib.h"
#define NUM 13
/* GLOBAL STRUCTURE */
typedef struct Stack Stack;
struct Stack
{
int id;
Stack* next;
Stack* prev;
};
/* GLOBAL VARIABLE */
Stack* top = NULL;
Stack* bot = NULL;
/* GLOBAL FUNCTIONS */
void ArrangeCards(void)
{
int i;
Stack* temp;
for(i=NUM; i>0; i--)
{
temp = (Stack*)malloc(sizeof(Stack));
temp->id = i;
if(top == NULL)
{
temp->next = NULL;
temp->prev = NULL;
top = temp;
bot = temp;
}
else
{
int j; //Num of times bot to top
Stack* iter;
/* Place new card on Top */
temp->next = top;
temp->prev = NULL;
top->prev = temp;
top = temp;
/* Shuffle card */
j = i%(NUM - i + 1);
for(;j>0;j--)
{
//Remove from bottom put it on top
iter = bot;
bot = bot->prev;
bot->next = NULL;
iter->next = top;
iter->prev = NULL;
top->prev = iter;
top = iter;
}
}
}
}
/* MAIN FUNCTION */
int main()
{
Stack* temp;
ArrangeCards();
temp = top;
printf("Card sequence : \n");
while(temp)
{
printf(" %d ", temp->id);
temp = temp->next;
}
printf("\n");
return 0;
}
Output :
rajkamal@Rajkamal-PC:~/Documents/Junk$ ./CardSeq.o
Card sequence :
4 1 13 11 2 10 6 7 3 5 12 9 8
I used modulo to reduce numer of iterations .. but will it be O(nlogn) ??
void arrangeCard(int a[], int n) { //here n = 13
//Assuming array a[] is initialised with value zero at all index.
int index = 0;
int count, k;
for(int i = 0; i < 13; i++) {
count = i+1;
k = 0;
while( k <= count) {
if( a[i] == 0) {
k++;
}
index = (index + 1)%n; // n=13 in this case
}
a[index++] = i;
}
}
{
public class Test {
public static void main(String[] args) {
int[] arr = new int[13];
int index;
for (index = 0; index < 13; index ++) {
arr[index] = 0;
}
int card = 1;
index = 0;
while (card <= 13) {
int skip = 0;
while (skip < card) {
if (arr[index] == 0) {
skip ++;
}
index = (++index) % 13;
}
while (arr[index] != 0) index = (++index) % 13;
arr[index] = card ++;
}
for(index=0; index < 13; index++) System.out.print(arr[index] + ", ");
}
}
}
I would suggest using a circular linked list and working backwards.
So you start with a K, you would place cards from the bottom to the top (reversed from the way you will select them).
First you have K. You rotate it 13 times, but you can just rotate 13 mod 1 = 0.
Next you put Q on top. You rotate is 12 times, but you can just rotate 12 mod 2 = 0.
Next you put J on top. You rotate 11 times, but you can just rotate 11 mod 3 = 2 times.
Eventually you have the full set.
Untested sample code:
Not sure how to prove that as nlogn time, but it seems efficient.
- someone July 22, 2014