Google Interview Question
Software EngineersTeam: Google Docs
Country: United States
Interview Type: In-Person
Let us assume:
N -> total cards
1-n -> numbering
k -> cards face up
N-k -> face down.
We need to find out probability of sum(k) divisible by 7.
Here we have no information about the sum(k), it can be anything. Let us take an example suppose we were asked to find out what will be the probability of sum(k) divisible by 2, the answer would be straight forward it is 1/2. On similar lines the answer here is 1/7.
Probability = (sum(k)/7)/sumk)
code?
import java.util.HashMap;
import java.util.Map;
public class ProbabiltyTest {
private static Map<Integer, Map<Long, Long>> dp = new HashMap<>();
public static void main(String[] args) {
long count = countOfSumMod7(0, 0, 50);
System.out.println("probabilty = " + (count / Math.pow(2, 50)));
}
public static long countOfSumMod7(int i, long sum, int n) {
Map<Long, Long> dpMap = dp.get(i);
if (dpMap != null) {
Long s = dpMap.get(sum);
if (s != null)
return s;
}
if (i >= n) {
if (sum % 7 == 0 && sum > 0)
return 1;
return 0;
}
long s = countOfSumMod7(i + 1, sum + i + 1, n) + countOfSumMod7(i + 1, sum, n);
if (dpMap == null) {
dpMap = new HashMap<>();
dp.put(i, dpMap);
}
dpMap.put(sum, s);
return s;
}
}
lets say we dont count the value of (ace king queen jack lets treat them as 0)and only treat numbers as numbers. So we have 4x10-1. that is 4x55. 220.
total sum of cards is max 220 when all are face up.
If we remove two cards, maximum 2x10, then its 200. number of numbers divisible by 7, 200/7 = 28 . so probability 28/200
Similarly if we remove cards with no value, its 31/220.
Average of these ((28/200)+(31/220))/2
Final result ((28/200)+(31/220))/2 * (probability of face up 0.5).
If we count the A K Q J as 14,13,12,11 then 200 more wil increase in the count. So total max is 420-(2x2s) , Min is 400.
((416/7)/416 +(400/7)/400)/2 * (0.5)
There's not enough information in the question to answer. How are the cards numbered? 1-50? 1-10? Do they contain picture cards? Are we talking about the chance that the number that land face up is divisible by seven, or the total value of the cards displayed? If 28 cards land face up, does it matter what the total value is? They're two very different questions to answer.
I'm not counting the only the cards that have a value multiple of 7.
Since there is clearly not enough information in the problem (it never says what type of cards they are, neither what numbers are present on their faces), I assumed the problem required to count the number of cards face-up, and that's what my solution is doing.
Of course my interpretation could be wrong.
@skumaringuva (for some reason the Reply button doesn't work...)
No, the "sums" are not equally distributed from 0 to 220 since the probability of having very low or very high numbers is extremely low.
Is like for instance when you roll 2 dices with 6 faces: the probability of having 12 is 1/36, while the probability of having 7 is 1/6, because 7 can be obtained in 6 different ways (1+6, 2+5, ...), while 12 only with 6+6.
The problem is very similar to the coin change problem.
Here the cards numbered from 1 through 10 are coins [1..10]
To find 7 multiples from 0, 14, 21, through 7+7+7.. (length of coins, in this case 7*10), will give rise to the following problem:
Find the # ways in which change can be made where the sum is in [0,7, 14.. 70] from coins numbered 1 through 10.
Add the # ways for each sum and divide by 10! (total # permutations)
double faceUpCards(int n, int k) {
for (int i = 0; i < 7; i++) {
dp[0][i] = 0.;
}
for (int i = 1; i <= k; i++) {
prob[i % 7] += 1. / (double)k;
}
dp[0][0] = 1.;
for ( int i = 1; i <= n; i++ ) {
for (int j = 0; j < 7; i++) {
int prevInd = j == 0? 0: 7 - j;
dp[i][j] += dp[i - 1][prevInd] * prob[j];
}
}
return dp[n][0];
}
PLEASE NOTE:
- Simone May 29, 2016>>>>
I wrote the following answer when the question was different since the guy who created this post
has recently edited the question.
In the original question, there was no information on the type of cards present in the deck, and it was very unclear whether the candidate was supposed to add the value of each card facing up or to count the total number of cards facing up.
Since the problem was very unclear, in this solution I'm counting the probability of the total number of cards with the face up is a multiple of 7.
Since now the poster has changed the question, the assumptions made for this answer are no longer valid. I'm still leaving this answer because it's correct if you want to count the number of cards with the face up.
>>>>
Assuming the probability of face-up is p=0.5.
Let āNā be the total number of cards, in this case 50.
I will use the "^" as the power operator, not as the bitwise XOR.
The fact that the cards are thrown at the same time is not relevant, this problem is like flipping a coin 50 times and counting how many times a certain side was up.
The probability of having K cards face-up is the probability of having the first K cards face-up (p^K) and the remaining N-K cards face down ((1-p)^(N-K) = p^(N-K) becase p=0.5) times the number of unique permutations (N! / (K! * (N-K)!)).
Another way to think of all the possible unique permutations is the following. Imagine you have 50 coins and you want to find the number of subsets having 7 coins (without ordering): the way to compute that number is by using the binomial coefficient (wikipedia / Binomial_coefficient), which is exactly N! / (K! * (N-K)!), or, with 50 and 7 ==> 50! / (7! * 43!) = 99884400.
Now we just need to sum the probability of every different K which is a multiple of 7, that is 0, 7, 14, 21, 28, 35, 42, 49.
P = (1 + 99884400 + 937845656300 + 67327446062800 + 88749815264600 + 2250829575120 + 536878650 + 50) / 2^50
= 159266573321921 / 2^50
= 0.141457