Symantec Interview Question
Quality Assurance EngineersTeam: DLP
Country: United States
Interview Type: In-Person
Pick a random card. Give to first player.
From remaining cards, pick a random card, give to next player.
Continue till you run out of cards.
In order to make each 'pick random card from remaining' an O(1) time operation, we maintain an array of cards, and once we have picked a card, we swap that with the last card, and decrement the length of the array.
PseudoCode
Deal (Card [] cards) {
int curLen = cards.Length;
for(i = 0; i < cards.Length; i++) {
int j = random(curLen); // Get random number in 0,1,2,..., curLen-1.
Deal(cards[j]); // Deal it to the next player.
swap(cards, j, curLen); // Essentially remove card[j] from the
curLen--; // deck.
}
}
import java.util.ArrayList;
import java.util.Random;
public class SuffleCards {
public static int k ;
public static StringBuffer ashish = new StringBuffer();
public static StringBuffer ankur = new StringBuffer();
public static StringBuffer bhatia = new StringBuffer();
public static StringBuffer rajesh = new StringBuffer();
public static int chance =1;
public static void main(String[] args) {
Random rndm = new Random();
ArrayList<Integer> arylst = new ArrayList<Integer>();
for (int i = 1; i <= 52; i++) {
arylst.add(i);
}
while (arylst.size() != 0) {
k = rndm.nextInt(arylst.size());
int l = arylst.get(k);
if ((chance-1) %4 == 0) {
ashish.append(l);
ashish.append(" ");
}
if ((chance-2) %4 == 0) {
ankur.append(l);
ankur.append(" ");
}
if ((chance-3) %4 == 0) {
bhatia.append(l);
bhatia.append(" ");
}
if ((chance-4) %4 == 0) {
rajesh.append(l);
rajesh.append(" ");
}
++chance;
arylst.remove(k);
}
System.out.println("Ashish Have: "+ashish.toString());
System.out.println("Mayank Have: "+bhatia.toString());
System.out.println("rajesh Have: "+rajesh.toString());
System.out.println("Ankur Have: "+ankur.toString());
}
}
Wikipedia entry on Fisher-Yates shuffle:
"For example, the built-in pseudorandom number generator provided by many programming languages and/or libraries may often have only 32 bits of internal state, which means it can only produce 232 different sequences of numbers. If such a generator is used to shuffle a deck of 52 playing cards, it can only ever produce a very small fraction of the 52! ≈ 2225.6 possible permutations. It's impossible for a generator with less than 226 bits of internal state to produce all the possible permutations of a 52-card deck. It has been suggested[citation needed] that confidence that the shuffle is unbiased can only be attained with a generator with more than about 250 bits of state."
Solution using Enum and Random Number :
package com.learning.puzzle;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
/*
* Write a programme to shuffle a deck of 52 cards,
* and shuffle them equallay to 4 players
*/
class Card {
public enum Rank {
DEUCE, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE
}
public enum Suit {
CLUBS, DIAMONDS, HEARTS, SPADES
}
private final Rank rank;
private final Suit suit;
private Card(Rank rank, Suit suit) {
this.rank = rank;
this.suit = suit;
}
public Rank rank() {
return rank;
}
public Suit suit() {
return suit;
}
public String toString() {
return rank + " of " + suit;
}
private static final List<Card> protoDeck = new ArrayList<Card>();
// Initialize prototype deck
static {
for (Suit suit : Suit.values())
for (Rank rank : Rank.values())
protoDeck.add(new Card(rank, suit));
}
public static ArrayList<Card> newDeck() {
return new ArrayList<Card>(protoDeck); // Return copy of prototype deck
}
}
public class RandomCards {
private Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
public RandomCards() {
}
public static void main(String[] args) {
ArrayList<Card> player1 = new ArrayList<Card>();
ArrayList<Card> player2 = new ArrayList<Card>();
ArrayList<Card> player3 = new ArrayList<Card>();
ArrayList<Card> player4 = new ArrayList<Card>();
ArrayList<Card> deck = Card.newDeck();
Random random = new Random();
int j = 1;
for (int i = 0; i < 52; i++) {
int temp = random.nextInt(52);
if (j == 1) {
player1.add(deck.get(i));
j++;
continue;
} else if (j == 2) {
player2.add(deck.get(i));
j++;
continue;
} else if (j == 3) {
player3.add(deck.get(i));
j++;
continue;
} else if (j == 4) {
player4.add(deck.get(i));
j = 1;
continue;
}
}
System.out.println(" Player 1 " + player1);
System.out.println(" Player 2 " + player2);
System.out.println(" Player 3 " + player3);
System.out.println(" Player 4 " + player4);
}
}
output
Player 1 [DEUCE of CLUBS, SIX of CLUBS, TEN of CLUBS, ACE of CLUBS, FIVE of DIAMONDS, NINE of DIAMONDS, KING of DIAMONDS, FOUR of HEARTS, EIGHT of HEARTS, QUEEN of HEARTS, THREE of SPADES, SEVEN of SPADES, JACK of SPADES]
Player 2 [THREE of CLUBS, SEVEN of CLUBS, JACK of CLUBS, DEUCE of DIAMONDS, SIX of DIAMONDS, TEN of DIAMONDS, ACE of DIAMONDS, FIVE of HEARTS, NINE of HEARTS, KING of HEARTS, FOUR of SPADES, EIGHT of SPADES, QUEEN of SPADES]
Player 3 [FOUR of CLUBS, EIGHT of CLUBS, QUEEN of CLUBS, THREE of DIAMONDS, SEVEN of DIAMONDS, JACK of DIAMONDS, DEUCE of HEARTS, SIX of HEARTS, TEN of HEARTS, ACE of HEARTS, FIVE of SPADES, NINE of SPADES, KING of SPADES]
Player 4 [FIVE of CLUBS, NINE of CLUBS, KING of CLUBS, FOUR of DIAMONDS, EIGHT of DIAMONDS, QUEEN of DIAMONDS, THREE of HEARTS, SEVEN of HEARTS, JACK of HEARTS, DEUCE of SPADES, SIX of SPADES, TEN of SPADES, ACE of SPADES]
void shuffle(int cards[], int p1[], int p2[], int p3[], int p4[])
{
int p=0;
int q=0;
int r=0;
int s=0;
int turn=0;
for(int i=0;i<52;++i)
{
int randomIdx = rand()%(52-i);
if (turn%4==0)
{
p1[p++] = cards[randomIdx];
}
else if (turn%4 == 1)
{
p2[q++] = cards[randomIdx];
}
else if (turn%4 == 2)
{
p3[r++] = cards[randomIdx];
}
else if (turn%4 == 3)
{
p4[s++] = cards[randomIdx];
}
++turn;
cards[randomIdx] = cards[52-i-1];
}
}
private static void shuffle(int[] cards) {
int totalCards = cards.length;
for(int i = 0 ; i < totalCards; ++i) {
int randomIndex = (int)(Math.random() * totalCards);
int temp = cards[randomIndex];
cards[randomIndex] = deck[i];
cards[i] = temp;
}
}
private static int[][] deal(final int[] card, int nPlayers){
int noOfPlayers = nPlayers;
int totalCards = card.length;
int cardPerPlayer = totalCards/noOfPlayers;
int[][] players = new int[noOfPlayers][cardPerPlayer];
int i =0; int j =0; int k = 0;
while(i < totalCards) {
j = j % noOfPlayers; // four players accessed in a cyclic order
players[j][k] = card[i];
++j;++i;
if(j == noOfPlayers) ++k; // increment k only after all 4 players have recieved one card each
}
return players;
}
In this approach, first the cards are shuffled, and then the deal() is called. So we are iterating twice over the same array.
import random
def define_cards():
rank_string = ("ace","two","three","four","five","six","seven","eight","nine","ten","jack","queen","king")
suit_string = ("clubs","diamonds","hearts","spades")
cards = []
for suit in range(4):
for rank in range(13):
card_string = rank_string[rank] + " of " + suit_string[suit]
cards.append(card_string)
return cards
def create_deck(deck):
for i in range(52):
deck.append(i)
return
def shuffle_deck(deck):
random.shuffle(deck)
return
def deal_card(deck):
return deck.pop(0)
deck=[]
create_deck(deck)
shuffle_deck(deck)
print "The first 10 cards are:"
for i in range(10):
deal_card(card)
print define_cards()
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
/*
* Write a programme to shuffle a deck of 52 cards,
* and shuffle them equallay to 4 players
*/
public class RandomCards
{
private List<Integer> allCards=new ArrayList<Integer>();
private Map<Integer,ArrayList<Integer>> map=new HashMap<Integer,ArrayList<Integer>>();
private Random random=new Random();
private ArrayList<Integer> player1=new ArrayList<Integer>();
private ArrayList<Integer> player2=new ArrayList<Integer>();
private ArrayList<Integer> player3=new ArrayList<Integer>();
private ArrayList<Integer> player4=new ArrayList<Integer>();
public RandomCards()
{
for(int i=0;i<52;i++)
{
allCards.add(i);
}
map.put(0,player1);
map.put(1,player2);
map.put(2,player3);
map.put(3,player4);
}
public void shuffleCardsToPlayers()
{
int temp=0;
int count=52;
Set<Integer> set=map.keySet();
for(int i=0;i<13;i++)
{
for(Integer j:set)
{
temp=random.nextInt(count);
Integer result=allCards.get(temp);
map.get(j).add(result);
allCards.remove(temp);
count--;
}
}
}
public void showResults()
{
if(allCards.isEmpty())
{
System.out.println("派已发完");
for(Integer j:map.keySet())
{
System.out.println("=====第"+j+"位牌手的牌");
ArrayList<Integer> list=map.get(j);
for(int i=0;i<list.size();i++)
{
System.out.println(list.get(i));
}
}
}
else
System.out.println("出错了");
}
public static void main(String[] args)
{
RandomCards rc=new RandomCards();
rc.shuffleCardsToPlayers();
rc.showResults();
}
}
Shuffle the cards in an array[0..51] and then assign each 13 chunks of the randomly shuffled cards to each player
- niki March 06, 2013