National Instruments Interview Question
Software Engineer / Developersa linked list containing all cards in order.
1. split the list
2. insert elements from list B into list B alternately
The problem now breaks down into: whats the best way to split a list, and how do we insert alternately.
This will ne O(n), but the shuffling would be pretty guessable.
We can also use a treap. Pick a card (for loop), assign a priority to it, maintain heap property on the random priorities.
This would be nlog n to create the treap, and log n to de-heap each element and place them back in the pack.
For pseudo-random priorities the shuffling would be less predictable than the linked list.
Actually the easiest would be a 52 slot hash table with random numbers as card indices.
Use array and then following algorithm
Let X1, X2…. XN (In this case N=52) be the set of N numbers to be shuffled.
1 Set j to N
2 Generate a random number R. (uniformly distributed between 0 and 1)
3 Set k to (jR+1). k is now a random integer, between 1 and j.
4 Exchange Xk and Xj
5 Decrease j by 1.
6 If j > 1, return to step 2.
we can use array[52] of objcets for storing the cards. Where object will be of type card having various poperties like (color, type <heart, diamond, ....>) ......
Now for shuffuling we need to use trick :
First genarate any random number using rand() function. This will ensure that number will not same at each time.
The use shift/rotate operation on our cards array like rotate(array, rand())
This rotate function will just rotate each element from array to the right or left (your choice) to the random number genarated.
Use and array to store the cards. I'm assuming you deck of cards will not grow so you don't need a linked list and if it did grow you could still allocate a larger array and copy the values there however this would take more work than a linked list.
int cards[NUM_CARDS];
fill cards array with cards
Anyway shuffle()
for (i = 0; i < NUM_CARDS; i++)
int newLoc = rand() % NUM_CARDS;
temp = cards[i];
cards[i] = cards[newLoc];
cards[newLoc] = temp;
You are going to shuffle without any space increase and only n time. Some cards may stay in the same place because you may have swapped them back and forth. I assumed this was alright. Every card will be touched.
I think there are different ways to shuffle cards, to make sure every card is shuffled, we can go through the array, and replace array[i] with array[i+1 mode n], and change the shuffle flag to True. Or we can use Knuth's shuffle algorithm to generate a random number proportional to the size of the remained unshuffled array.
This is an interesting one. A simple array can solve this problem. Loop 52 times (for all the card nos.) and swap each card (arr[i] with any random number i.e. arr[random] where you have chosen a random number from (i,51). This will give you a perfectly shuffled deck and that too in O(n) time:)
For shuffling ,better we can use hash array,do hashing with some mathematical operation,
- midhun sukumaran February 07, 2013like (card_value+7)%10 ,then the all cards will be shuffled.