30 Day Risk-Free Guarantee:
100% money back if you're unsatisfied.
Book (308 Pages):
  • 150 Programming Interview Questions and Solutions
  • Five Proven Approaches to Solving Tough Algorithm Questions
  • Ten Mistakes Candidates Make -- And How to Avoid Them
  • Steps to Prepare for Behavioral and Technical Questions
  • Interview War Stories: A View from the Interviewer's Side
  • Book Preview and More Info

Video (One Hour):
  • Watch CareerCup's founder perform a totally unscripted technical interview of a candidate.
  • Overview of what interviewers look for in software engineering jobs.
  • Technical questions with white-boarding coding where the candidate does well - and struggles.
  • Interviewer reviews with what went well and poorly.
  • Video Preview and More Info

Resume Review (24 - 48hr)
  • Get your resume reviewed by a trained engineering interviewer. More Info
All Products / Services


Express Prep Package (Book)
$29.99 for e-book | $32.45 for paperback
Buy E-Book Buy on Amazon


Standard Prep Package (E-Book & Video)
Emailed Instantly | $39.99
Buy Standard

Elite Prep Package (E-Book, Video & Resume)
Emailed Instantly | $99.99
Buy Elite
 



Write a function to shuffle cards

12


Anonymous on November 12, 2009 |Edit | Edit


for(int i = 0; i< 52; i++)
{
int j = rand(i, 52);
if(i != j)
{
int temp = cards[i];
cards[i] = cards[j];
cards[j] = temp;
}
}

Anonymous on November 14, 2009 |Edit | Edit

int j = rand(i, 52);

make it

int j = rand(1, 52);

geniusxsy on November 12, 2009 |Edit | Edit

LMAO!

Non-uniform probability.

Go home and study more math

Arjun on November 13, 2009 |Edit | Edit

The solution given above is an implementation of the Knuth algorithm. Please stop acting like a jerk and do some research before posting something.

Anonymous on November 14, 2009 |Edit | Edit

Knuth shuffle starts from a[51] rather than a[0] I think.

Starting from a[0] is not uniform apparently, and it looks like geniusxsy is right.

geniusxsy on November 12, 2009 |Edit | Edit

Think about it, why it's non-uniform?
If you still don't get it, try N=3, enumerate all possibilities.

Anonymous on November 13, 2009 |Edit | Edit

Use Knuth Shuffle

http://en.wikipedia.org/wiki/Knuth_shuffle

Coder on November 13, 2009 |Edit | Edit

Use Knuth Shuffle

http://en.wikipedia.org/wiki/Knuth_shuffle

Anonymous on November 13, 2009 |Edit | Edit
Synonymous on December 23, 2009 |Edit | Edit

what nice?

Anonymous on January 06, 2010 |Edit | Edit

class Card
{
String type;
int value;
int randomVal;
boolean struck;

Card(String type,int value,int randomVal)
{
this.type = type;
this.value = value;
this.randomVal = randomVal;
struck=false;
}
}

List<Card> deck = new ArrayList<Card>();

void initializeSpade()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Spade",i,randomVal);
deck.add(card);
}
}

void initializeClub()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Club",i,randomVal);
deck.add(card);
}
}

void initializeHearts()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Hearts",i,randomVal);
deck.add(card);
}

}

void initializeDiamonds()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Diamonds",i,randomVal);
deck.add(card);
}
}

public Card[] perfectShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();
Card[] originalList = new Card[52];
for(int i=0;i<deck.size();i++)
{
originalList[i]=deck.get(i);
}
int iter=51;
while(iter>0)
{
iter--;
int randomVal = (int)((Math.random()*100)%iter);
Card temp = originalList[iter];
originalList[iter]=originalList[randomVal];
originalList[randomVal]=temp;
}
System.out.println("Number of iterations are : " + iter);
return originalList;
}

Anonymous on January 06, 2010 |Edit | Edit

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import javax.print.attribute.standard.OrientationRequested;

public class CardShuffling {

class Card
{
String type;
int value;
int randomVal;
boolean struck;

Card(String type,int value,int randomVal)
{
this.type = type;
this.value = value;
this.randomVal = randomVal;
struck=false;
}
}

List<Card> deck = new ArrayList<Card>();

void initializeSpade()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Spade",i,randomVal);
deck.add(card);
}
}

void initializeClub()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Club",i,randomVal);
deck.add(card);
}
}

void initializeHearts()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Hearts",i,randomVal);
deck.add(card);
}

}

void initializeDiamonds()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Diamonds",i,randomVal);
deck.add(card);
}
}

public Card[] quadraticShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();
int[] sortedArr = sort();

//for(int i=0;i<sortedArr.length;i++)
// System.out.println(sortedArr[i]);

Card[] card = reArrange(sortedArr);
return card;
}

public int[] sort()
{
int arr[]= new int[deck.size()];
for(int i=0;i<arr.length;i++)
{
arr[i] = deck.get(i).randomVal;
}
Arrays.sort(arr);
return arr;
}

public int binarySearch(int[] arr,int left,int right,int val)
{
int mid=(left+right)/2;
if(arr[mid]==val)
return mid;
else if(arr[mid]>val)
return (binarySearch(arr,left,mid-1,val));
else if(arr[mid]<val)
return (binarySearch(arr,mid+1,right,val));
else
return -1;
}

public Card[] reArrange(int[] arr)
{
Hashtable<Integer,List<Card>> cardKey = new Hashtable<Integer,List<Card>>();

for(int i=0;i<deck.size();i++)
{
int pos = binarySearch(arr, 0, arr.length-1, deck.get(i).randomVal);
if(cardKey.containsKey(pos))
{
List<Card> cardList = cardKey.remove(pos);
cardList.add(deck.get(i));
cardKey.put(pos,cardList);
}
else
{
List<Card> cardList = new ArrayList<Card>();
cardList.add(deck.get(i));
cardKey.put(pos,cardList);
}
}

Set set = cardKey.keySet();
Iterator it = set.iterator();

Card[] card = new Card[deck.size()];
for(int t=0;t<card.length;)
{
while (it.hasNext())
{
System.out.println();
List<Card> cardList = cardKey.get(it.next());
for(int i=0;i<cardList.size();i++)
{
card[t] = cardList.get(i);
t++;
}
}
System.out.println("Final value of t : " + t);
}
return card;
}

public Card[] linearShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();

Card[] originalList = new Card[52];
Card[] shuffledList = new Card[52];

for(int i=0;i<deck.size();i++)
{
originalList[i]=deck.get(i);
}

int count=0;
int remainCards = 52;
int iter=0;
while(count<52)
{
iter++;
int randomVal = (int)((Math.random()*100)%52);
if(originalList[randomVal].struck==false)
{
originalList[randomVal].struck=true;
shuffledList[count]=originalList[randomVal];
count++;
remainCards--;
}
}

System.out.println("Number of iterations are : " + iter);
return shuffledList;
}

public Card[] perfectShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();
Card[] originalList = new Card[52];
for(int i=0;i<deck.size();i++)
{
originalList[i]=deck.get(i);
}
int iter=51;
while(iter>0)
{
iter--;
int randomVal = (int)((Math.random()*100)%iter);
Card temp = originalList[iter];
originalList[iter]=originalList[randomVal];
originalList[randomVal]=temp;
}
System.out.println("Number of iterations are : " + iter);
return originalList;
}

public static void main(String[] args) {

CardShuffling obj = new CardShuffling();
//Card[] card = obj.quadraticShuffle();
//Card[] card = obj.linearShuffle();
Card[] card = obj.perfectShuffle();

int count=0;
for(int i=0;i<card.length;i++)
{
System.out.println();
if(card[i]!=null)
{
count++;
System.out.print(" ");
System.out.print(card[i].type);
System.out.print(" ");
System.out.print(card[i].value);
System.out.print(" ");
System.out.print(card[i].randomVal);
}
}
System.out.println();
System.out.println("count is: " + count);
}
}

Add a Text Comment | Add Runnable Code
Name:
Comment:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.








Amazon (1033)Bloomberg LP (403)Qualcomm (117)Adobe (88)Goldman Sachs (78)NetApp (49)IBM (43)Morgan Stanley (33)CapitalIQ (30)Sophos (25)Achieve Internet (23)Electronic Arts (19)Motorola (18)Research In Motion (17)Flipkart (16)
Microsoft (867)Google (141)NVIDIA (98)Yahoo (82)Epic Systems (69)Expedia (47)VMWare Inc (43)Apple (32)Cisco Systems (28)Facebook (23)Infosys (22)Agilent Technologies (19)Sage Software (17)Deshaw Inc (16)FlexTrade (15)
More Companies »
Software Engineer / Dev... (1062)Financial Software Deve... (170)Testing / Quality Assur... (56)Analyst (35)Virus Researcher (25)Field Sales (15)Developer Program Engin... (9)Front-end Software Engi... (6)MyJoB (5)area sales manager (4)Assistant (3)Cabin crew (2)Accountant (1)personnel (1)Intern (1)
Software Engineer in Te... (288)Program Manager (65)Development Support Eng... (47)INTERN(MSIDC) (28)Web Developer (18)System Administrator (10)Consultant (10)Production Engineer (5)Associate Technology L2 (5)AcquireKnowledge (4)Product Security Engine... (3)Solutions Architect (2)Gamer (1)mts (1)Fresh graduate interview (0)
More Job Titles »
Algorithm (1073)Terminology & Trivia (294)C (166)Object Oriented Design (159)Java (121)Testing (114)Arrays (101)Operating System (78)Database (70)Linked List (62)String Manipulation (56)Networking / Web / Inte... (44)Threads (36)Linux Kernel (33)PHP (22)
Coding (511)C++ (204)Behavioral (159)Data Structures (155)Experience (116)Brain Teasers (111)Computer Architecture &... (79)General Questions and C... (73)Trees and Graphs (69)Math & Computation (57)Application / UI Design (45)Ideas (38)System Design (35)Puzzles (30)Bit Manipulation (20)
More Topics »
CareerCup Official Interview Book Daily Questions Requests for Help Mock Interviews Video for Cracking the Coding Interview Job Placement Service CareerCup Blog
My Profile Edit Profile & Email Settings Sign Out