The author is a senior vegetable chicken, recently in the process of preparing the autumn recruitment encountered a byte algorithm problem, feel very interesting, decided to write an article, and discuss with everyone.
The title
Give you a deck of cards to remove king king, a total of 52 cards, please package a getCard function, accept a count parameter, will output count cards with random content, such as getCard(4), will output [1 spades, 3 hearts, 4 diamonds, 5 clubs]. This function can be called multiple times. When called multiple times, the cards previously dealt will not be dealt again. This function is called until the value of the passed count is greater than the number of cards in the hand, directly printing the remaining cards in the hand.
Train of thought
In the beginning, I wanted to use a data structure to record the cards in my hand. The cards that were dealt were deleted directly from the data structure, so I decided to use an array, but the array splice method was a bit complicated, so I used map? Math.random() is used to generate a random index, which is a random card. At the same time, the train of thought immediately began to knock up.
// Initialize a deck of cards to remove the king
let map = new Map(a);let type = ['hearts'.'the plum blossom'.'square'.'spades'];
for (let i = 1; i <= 13; i++) {
for (let j = 0; j < type.length; j++) {
map.set((type[j] + i), true)}}function getCard(count) {
let res = [];
function help() {
// Record the cards I have left in my hand
let tmpArr = [];
for (let item of map.keys()) {
tmpArr.push(item);
}
// Generate a random card
let cardIndex = Math.floor(Math.random() * tmpArr.length);
let card = tmpArr[cardIndex];
// I'll delete it as soon as I send it
map.delete(card);
return card;
}
// If the number of cards in your hand is less than count, deal all the cards
if (map.size <= count) {
res = [...map.keys()];
map.clear();
} else {
for (let i = 0; i < count; i++) {
res.push(help())
}
}
return res;
}
console.log(getCard(48));
Spade / * * [' 2 ', 'square 10', 11 'square', 'red peach 3', 4 'square', 'spades 13', '7 of spades',' the plum blossom 6 ', '4' of spades, red peach '13', '1' of spades, 'hearts 4', '5' hearts, 'plum 4', '8' hearts, 'spades 10', 'the plum blossom 12', 'red peach 10', 'red peach 11', 'square 13', 'plum blossom 10', '3' of spades, 'plum 3', 'plum blossom 5', 'spades 5', '9 square', 'square 12', 7 'square', '1' cubes, 'spades 9', '6' of spades, 'spades 11', 'plum 2', 'square 2', '8 squares',' red peach 12 ', 'red peach 2', 'square in the 5', 6 'square', '3' cubes, 'hearts, 7', 'plum blossom 11', 6 ', 'hearts' hearts 1', 'spades 12', 'plum blossom 7', '9' hearts, '9' of clubs
console.log(getCard(8)); // [' 1', '8',' 8 of Spades ', '13 of clubs']
console.log(getCard(8)); / / []
Copy the codeFinally, I stumbled and finished writing. I felt good after I finished writing. I felt that the use cases were exported and I wondered if the interviewer could prepare the next question. The interviewer gently said, “Look at your code carefully. Do you have to reshuffle the cards every time you deal a card? See if you can optimize it.” The ones who didn’t know what the interviewer meant… I just want to say that I usually do not play cards ah, king canyon is not fragrant? Then it suddenly dawned on me that it was here…
for (let i = 0; i < count; i++) {
res.push(help()) // loop count, shuffle count
}
Copy the codeThe interviewer gave me a headshot: “Is tmpArr required in your code? Can it be optimized there?” Oh ~, I seem to be through two pulse, immediately began to change.
let map = new Map(a);let type = ['hearts'.'the plum blossom'.'square'.'spades'];
for (let i = 1; i <= 13; i++) {
for (let j = 0; j < type.length; j++) {
map.set((type[j] + i), true)}}function getCard(count) {
let res = [];
function help() {
// Changed this to generate a value based on the remaining map length and a random card type
let cardIndex = Math.floor(Math.random() * map.size);
let typeIndex = Math.floor(Math.random() * type.length);
let card = typeIndex + cardIndex;
map.delete(card);
return card;
}
if (map.size <= count) {
res = [...map.keys()];
map.clear();
} else {
for (let i = 0; i < count; i++) {
res.push(help())
}
}
return res;
}
console.log(getCard(48));
console.log(getCard(8));
console.log(getCard(8));
Copy the codeThe interviewer took one look and said, “Let’s say I’ve already given out the nine of hearts. There’s something wrong with it. “I panicked… “, thought for a while then gave up, and began the back of the problem.
thinking
When I was interviewing myself, I had a brainwave and knew how to optimize it! Every time I call getCard, when I’m dealing, I just randomly generate a position, and then on the basis of that position, I do a continuous deal, so the problem is solved!
let map = new Map(a);let type = ['hearts'.'the plum blossom'.'square'.'spades'];
// Initialize a deck of cards
for (let i = 1; i <= 13; i++) {
for (let j = 0; j < type.length; j++) {
map.set((type[j] + i), true)}}function getCard(count) {
let res = [];
function help(count) {
let tmpArr = [];
let res2 = [];
for (let item of map.keys()) {
tmpArr.push(item);
}
let position = Math.floor(Math.random() * (tmpArr.length - count));
while(count){
res2.push(tmpArr[position])
map.delete(tmpArr[position]);
position++;
count--;
}
return res2;
}
if (map.size <= count) {
res = [...map.keys()];
map.clear();
} else {
res = help(count)
}
return res;
}
console.log(getCard(23));
/ * [' square 4 ', '4' of spades, red peach '5', 'plum blossom 5, 5' square ', '5' of spades, red peach '6', 6 ', 'plum blossom' square 6 ', 6 ', 'spades' hearts, 7', 'plum blossom 7', 7 'square', '7 of spades',' 8 'hearts,' plum blossom 8 ', Spade 'square, 8', '8', '9' hearts, 'plum blossom 9', '9 square', 'spades 9', 'red peach 10] * /
console.log(getCard(24));
Red peach / * [' 2 ', 'plum 2', 'square 2', '2' of spades, red peach '3', '3 of clubs',' square 3 ', '3' of spades, red peach '4', 'plum 4', 'plum blossom 10', 'square 10', 'ten of spades, red peach' 11 ', 'plum blossom 11', 'square 11', 'spades 11', 12 ' 'hearts,' plum blossom 12 ', 'square 12', 'spades 12', 'red peach 13', 'the plum blossom, 13', 'square 13] * /
console.log(getCard(10));
//[' 1 of hearts ', '1 of clubs ',' 1 of diamonds ', '1 of spades ',' 13 of spades']
Copy the codeThis is the solution to the problem, harm, only hate at that time too hasty! Not telling the interviewer…
Can that be optimized? The answer is yes.
Another disadvantage of the above method is that we need to shuffle the cards every time we call getCard, but in fact we just need to shuffle the cards when we initialize them!
// Shuffle the card function
function shuffle(arr) {
for (let i=arr.length-1; i>=0; i--) {
let rIndex = Math.floor(Math.random()*(i+1));
// Prints the swap value
// console.log(i, rIndex);
let temp = arr[rIndex];
arr[rIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
let map = new Map(a);let allCards = [];
let type = ['hearts'.'the plum blossom'.'square'.'spades'];
// Initialize a deck of cards
for (let i = 1; i <= 13; i++) {
for (let j = 0; j < type.length; j++) {
allCards.push(type[j]+i)
}
}
allCards = shuffle(allCards)
for(let i = 0; i < allCards.length; i++){ map.set(allCards[i],true)}function getCard(count) {
let res = [];
function help(count) {
let tmpArr = [];
let res2 = [];
for (let item of map.keys()) {
tmpArr.push(item);
}
let len = tmpArr.length;
while(count){
res2.push(tmpArr[len-count])
map.delete(tmpArr[len-count]);
count--;
}
return res2;
}
if (map.size <= count) {
res = [...map.keys()];
map.clear();
} else {
res = help(count)
}
return res;
}
console.log(getCard(23));
console.log(getCard(25));
console.log(getCard(10));
Copy the codeexpand
About this shuffling algorithm, there are a lot of, such as shuffling a deck of cards randomly, can be converted to shuffling an array?
function shuffle(arr) {
for (let i=arr.length-1; i>=0; i--) {
let rIndex = Math.floor(Math.random()*(i+1));// Why is this range generated
// Prints the swap value
// console.log(i, rIndex);
let temp = arr[rIndex];
arr[rIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
shuffle([1.2.3.4.5.6]); // [1, 5, 3, 6, 4, 2]
Copy the codeSo how do we prove we’re randomly shuffled?
// Use res to store results
let res = {};
let times = 100000;
for (let i=0; i<times; i++) {
// Use [1, 2, 3] for simple tests
let key = JSON.stringify(shuffle([1.2.3]));
res[key] ? res[key]++ : res[key] = 1;
}
for (let key in res) {
res[key] = Number.parseFloat(res[key]/times *100 ).toFixed(3) + The '%';
}
// The result is true
res:
/ * [1, 2, 3] : "16.514%" [31] 1: "16.764%",1,3 [2] : "16.606%",3,1 [2] : "16.587%",1,2 [3] : "16.712%" [3, 2, 1] : "16.817%" * /
Copy the codeFix a value and shuffle it.
There are many ways to fix the value of a subscript and keep its position unchanged while the order is out of order. Here is only one of them:
function shuffle(arr, index) {
let res = [];
// Fetch a fixed value
let fix = arr.splice(index, 1) [0];
for (let i=arr.length-1; i>=0; i--) {
let rIndex = Math.floor(Math.random()*(i+1));
res.push(arr[rIndex]);
arr.splice(rIndex, 1);
}
// Put the fixed value into the specified position
res.splice(index, 0, fix);
return res;
}
// We can see that the array subscript 1 is always fixed
shuffle([1.2.3.4.5.6].1);
// [5, 2, 6, 3, 1, 4]
// [5, 2, 6, 3, 4, 1]
// [3, 2, 4, 6, 1, 5]
Copy the codeHere’s another test to see if true out-of-order is implemented:
let res = {};
let times = 100000;
for (let i=0; i<times; i++) {
// Use [1, 2, 3] for simple tests, fixing the value of array subscript 1
let key = JSON.stringify(shuffle([1.2.3].1));
res[key] ? res[key]++ : res[key] = 1;
}
for (let key in res) {
res[key] = Number.parseFloat(res[key]/times *100 ).toFixed(3) + The '%';
}
// While fixed, it is still out of order
res;
/*
[1,2,3]: "49.976%"
[3,2,1]: "50.024%"
*/
Copy the codeI wrote in a hurry in the evening, and I’m sure there are mistakes. I hope you can correct them.
Wish you all get satisfactory offer as soon as possible!!