From this question asked in an interview:
Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted hash table, what is the probability that there will be a slot with $K$ elements? $K$ could vary from $0$ to $N$.
I'm not very good in statistics, that's why I'm asking for your help. What is the probability and how to compute it?
I could think of the following. Let $a_i$ be the number of elements in slot $i$. Then $P(a_i = K) = P(a_j = K) = P_K, \forall i, j$. And the answer is given by $P^* = 1 - (1 - P_K)^M$. But how to comupte $P_K$?
PS. The only question I could answer is "what is the expected value of the number of elements in a single slot?". And the answer is $N/M$. Am I right?