Question: Given a list of 24 words, how many different BINGO cards can you create. What if there are more words? What if there are duplicates?
Answer: The first part is a straight forward permutation question.
Number of different cards = 24! = 620 448 401 733 239 439 360 000 (pretty large number)
What if there are more than 24 words (n words). First we will have choose 24 words out of the n options, then do permutation on the selected 24 items. Read more about choosing here
Number of different cards = 24!*nC24 = 24! * n!/(24!(n-24)!) = n!/(n-24)! (simple as that)
What if there are duplicates? (Now it gets a little tricky). Assumption: 24 words. If there are two words which are the same, they can be used interchangeably. In this case, we will need to divide the possible cards by 2 to account for this. What if there are three words which are the same? Going back to the permutation equation (n!), we will have 3! way of arranging the same words. We will need to divide this from the number of total possible cards.
Assume number of duplicates = k
Number of different cards (with duplicates) = 24!/k!
What if there are two different set of duplicates? We will need to divide both set of duplicate possibilities from the number of total possible cards.
Assume number of duplicates = k, j, m
Number of different cards (with multiple duplicates) = 24!/(k!*j!*m*)
Note, thinking back to the first equation, if there are no duplicates, it is as good as having 1 of each word = 24!/(1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!)
What happens if there are more than 24 words and there are duplicates? Take a shot at it in the comments section. I will post the answer shortly.
Meanwhile, enjoy the fun game of BINGO by creating customizable BINGO cards at www.custombingocards.net.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
You have not taken into account symmetry. If the usual rules of bingo apply (a series of hits in a line) then there will be both rotationally symmetrical and reflectively symmetrical cards that will give identical results. If the cards are square then there will be four rotational variants and four reflected rotational variants, so the total number needs to be divided by 8.