In Section 2.2 (Stick breaking problem, page 70) I believe the references to equations 14 and 15 in the diagram should be swapped. See image:

First, thanks for creating this doc! I'm in the process of preparing for interviews currently and it's been extremely useful.

I wanted to suggest an alternative solution to problem 16 that I find a bit more intuitive than the one provided. It's effectively the same, but I think it follows a smoother train of thought since it beings with the reflex that many people have of immediately taking ln() when they see an expression with an exponential. I've pasted the LaTeX for the solution below.

Begin by considering,
%
\begin{align*}
    f(x) = ln(x^{x}) = xln(x).
\end{align*}
%
Then we have,
%
\begin{align*}
    f'(x) = ln(x) + 1.
\end{align*}
%
For any function, $g$, we have by the chain rule,
%
\begin{align*}
    \frac{d}{dx}g(x^{x}) = g'(x^{x})\frac{d}{dx}x^{x}.
\end{align*}
%
If we let $g = f$, and rearrange the above we get,
%
\begin{align*}
   \frac{d}{dx}x^{x} &= \frac{\frac{d}{dx}f(x^{x})}{f'(x^{x})} \\ 
   &= \frac{ln(x)+1}{\frac{1}{x^{x}}} \\
   &= x^{x}(ln(x)+1).
\end{align*}

Similar to generating functions, another useful trick for calculating moments of various distributions is to use Feynman's integral trick (differentiating under the integral sign). The main idea is to introduce a fictitious parameter and rewrite the integrand as some derivative with respect to this parameter. (Note that this trick can also be used when evaluating expectation values for discrete distributions). Let me illustrate this for moments of the Gaussian distribution, which appear in the primer. Consider the integral

In order to evaluate the above expression, we introduce a parameter in the probability density function

Notice that this integral can be rewritten as

This is just a Gaussian integral, and so we find

Finally, we recover the desired result by setting the parameter to 1,

Thanks a lot for the primer! When reading question 23, I thought the "recursion" part was meant on the binomial function itself instead of the factorial, so I came up with:

def n_given_k(n, k):
    if (k == 0) or (k == n):
        return 1
    return n_given_k(n - 1, k - 1) + n_given_k(n - 1, k)

For reference: https://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_formula

It answers the question, although it is of course very inefficient. A better recursive formula is given in http://penguin.ewu.edu/~trolfe/BinomialCoeff/ .

For any values of k or n greater than 2 the fastest algorithm is probably to simply use a hash-table which would be amortized O(n). But the answer given suggests doing a O(n^k) grid search which (in my opinion) isn't a good idea.

Another "pure" mathematical approach would be to let the non-missing values be p_1,...,p_{n-k} which are the roots of the polynomial f(x)=(x-p_1)...(x-p_{n-k})=x^{n-k}+s_1x^{n-k-1}+...+s_{n-k-1}x+s_{n-k} and calculate the symmetric homogeneous polynomials s_1,...,s_{n-k} via Newton's identities. Then we plug 1,2,...n into the polynomial f and the missing values are the non-roots. Depending on the value of k this could be faster than the grid search (but still a lot slower than the hash table).

Hi,

Just want to thank you for creating this doc, certainly helped for my interviews! Thought I should give back by suggesting a slightly easier solution for the airplane question (I think yours has a bit too much going on).

Define p_n = probability of last person in their seat if there are n people. Either the first person goes to their seat (with prob 1/n) and everything's fine, or the first person goes to any seat other than the last, in which case we return to the same problem with n-1 people.

So p_n = 1/n + (n-2)/n p_(n-1). Since p_2 = 1/2 it is simple to use induction to prove p_n = 1/2.