Microsoft Interview Question Software Engineer / Developers
Store a card number from by 1 to 52 in an array.
Run a loop and generate a random number in range of 1 to 52. Swap loopCounter and random Number. In this way you can do swapping in just one iteration..........
#include<iostream>
using namespace std;
int getrand(int lim) //One flavour of random number generator
{
static long a = 1; //seed
a = (a*32719 + 3)%32749;
return (a%lim + 1);
}
int main()
{
int cards[52],rand;
for(int i=0;i<52;i++) //assign initial position
{
cards[i] = i+1;
}
for(int i=0;i<52;i++) //swap indexes with counters and random numbers
{
int temp = 0;
rand = getrand(51);
cout <<rand <<"\t";
temp = cards[rand];
cards[rand] = cards[i];
cards[i] = temp;
}
cout <<endl <<endl;
for(int i=0;i<52;i++)
cout <<cards[i] <<"\t";
return 0;
}
It is not efficient at all!
It requires 52 times and each time only exchanges two cards. It is very likely, some cards are still in original positions.
Here is some ideas(acting like a dealer)
Assuming you have Spade A-10-K, following by Heart, Diamond and Club.
1. Divided the cards by 2 groups, Cards 0 to 25(Spade, Heart) and 26 to 51(Diamond, Club). Exchange the old number cards of two groups. In this exchange, Spade cards mix with Diamond cards, Heart cards mix with Club cards.
2. Divided the new deck by 3 groups. Cards 0 to 16, 17 to 33, 33 to 50 with last card left. Exchange cards in first group and the third group and then move second group to the top. Put last card radomly between card No.11 to No. 43.
3. Repeat step 2 and 3 two more times.
4. You can write a program and compare the two methods.
some changes in gajanan code , would make it right
int main()
{
int cards[52],rand, subset[52];
for(int i=0;i<52;i++) //assign initial position
{
cards[i] = i+1;
}
for(int i=0;i<52;i++) //swap indexes with counters and random numbers
{
int temp = 0;
rand = getrand(51);
cout <<rand <<"\t";
temp = cards[rand];
cards[rand] = cards[i];
cards[i] = temp;
subset[i]=temp;
}
cout <<endl <<endl;
for(int i=0;i<52;i++)
cout <<subset[i] <<"\t";
return 0;
}
Check CMH to understand how to permute an array randomly. All the above mentioned ideas are very naive. They don't suffice for a precise answer.
Suppose you want to randomize an array of 52 values, from 0 to 51 with no repeats, such as you might want for a deck of cards. First fill the array with the values in order, then go thru the array and exchange each element with a randomly chosen element in the range from itself to the end. It's possible that an element will be exchanged with itself, but there is no problem with that.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// File : misc/random/deal.cpp - Randomly shuffle deck of cards.
// Illustrates : Shuffle algorithm, srand, rand.
// Improvements: Use classes for Card and Deck.
// Author : Fred Swartz 2003-08-24, shuffle correction 2007-01-18
// Placed in the public domain.
#include <iostream>
#include <cstdlib> // for srand and rand
#include <ctime> // for time
using namespace std;
int main() {
int card[52]; // array of cards;
int n; // number of cards to deal
srand(time(0)); // initialize seed "randomly"
for (int i=0; i<52; i++) {
card[i] = i; // fill the array in order
}
while (cin >> n) {
//--- Shuffle elements by randomly exchanging each with one other.
for (int i=0; i<(52-1); i++) {
int r = i + (rand() % (52-i)); // Random remaining position.
int temp = card[i]; card[i] = card[r]; card[r] = temp;
}
//--- Print first n cards as ints.
for (int c=0; c<n; c++) {
cout << card[c] << " "; // Just print number
}
cout << endl;
}
return 0;
}
private static int getRandomNo(int range){
Random rand = new Random();
return rand.nextInt(range);
}
public static void cardSuffle(){
int[] a = new int[52];
for(int i = a.length -1 ; i >0 ; i--){
a[i] = i;
}
for(int i = a.length -1 ; i >0 ; i--){
int n = getRandomNo(i + 1);
int temp = a[i];
a[i] = a [n];
a[n] = temp;
}
for(int i = 0 ; i < a.length-1 ; i++){
System.out.print(" " + a[i] + " ");
}
System.out.println("");
}
We can use Drustenfeld's Algorithm -- Time - O(n) and Space - O(1)
- DigitalFire March 27, 2013#include<iostream> #include<stdlib.h> #include<math.h> #include<time.h> using namespace std; class Deck { public: int array[52]; Deck() { for(int i=0;i<52;i++) array[i] = i+1; } void shuffle(); void swp(int * begin, int * ebd); void print(); }; void Deck::shuffle() { srand(time(NULL)); for(int i = 51;i>=0;i--) { int r = rand() % (i+1); swp((int *)(array+i),(int *) (array+r)); } } void Deck::swp(int * num1,int * num2) { int temp = *num1; *num1 = *num2; *num2 = temp; return; } void Deck::print(){ for(int i=0;i<52;i++){ cout<<array[i]<<" "; } cout<<endl; } int main() { Deck obj; obj.shuffle(); obj.print(); return 0; }