Example Maven Interview Questions

This is a pretty straightforward Markov chain problem. There are 4 states. The transition graph is given in Figure 1.

The problem starts at state 1. As has been explained in the lessons of this course, we use the following equation:
\begin{equation}
s_1 = \sum_{i=0}^{3}p_{1,i}s_i
\end{equation} \begin{equation}
s_2 = \sum_{i=0}^{3}p_{2,i}s_i
\end{equation} Furthermore, $s_0=0$ and $s_3=1$. Then we have
\begin{equation}
s_1 = \frac{1}{3}*0 + \frac{2}{3} * s_2
\end{equation} \begin{equation}
s_2 = \frac{1}{3}* s_1 + \frac{2}{3} * 1
\end{equation} Solving these equations gives us $s_1=4/7$ and $s_2=6/7$. So, starting with 1 dollar, player A has a 4/7 chance of winning.

Proof
If we substitute Equation 4 in Equation 3, we have

\begin{equation}
s_1 = \frac{1}{3}*0 + \frac{2}{3} * (\frac{1}{3}* s_1 + \frac{2}{3} * 1)
\end{equation} \begin{equation}
s_1 = \frac{2}{9} * s_1 + \frac{4}{9}
\end{equation}  \begin{equation}
\frac{7}{9} * s_1 =  \frac{4}{9}
\end{equation}  \begin{equation}
s_1 =  \frac{4}{9} / \frac{7}{9} = \frac{4}{7}
\end{equation}

This is called the coupon collector problem. For a fair n-sided die, the expected number of attempts needed to get all n values is \begin{equation}
n \Sigma_{k=1}^n \frac{1}{k}
\end{equation} which, for large n is approximately n log n.

The time until the first result appears is 1. After that, the random time until a second (different) result appears is geometrically distributed with parameter of success 5/6, hence with mean 6/5 (recall that the mean of a geometrically distributed random variable is the inverse of its parameter). After that, the random time until a third (different) result appears is geometrically distributed with parameter of success 4/6, hence with mean 6/4. And so on, until the random time of appearance of the last and sixth result, which is geometrically distributed with parameter of success 1/6, hence with mean 6/1. This shows that the mean total time to get all six results is \begin{equation}
6 \Sigma_{k=1}^6 \frac{1}{k} = \frac{147}{10} = 14.7
\end{equation}

For the outcome to be even is the same as the outcome not being odd. For the outcome to be odd, all three dice need to be odd, respectively:

• 1*1*1 = 1 (odd)
• 3*3*3 = 27 (odd)
• 5*5*5 = 125 (odd)

and also all combinations of the odd numbers result in odd outcomes, like:

• 1*1*3 = 3 (odd)
• 3*3*5 = 45 (odd)
• etc.

Basically, multiplying odd numbers with each other results in an odd outcome. If ANY even number comes in play, then we have "a number" multiplying "an even number", which will always result in an even number. So, "odd * even * odd" will also result in even.

So, in any other scenario than multiplying three odd numbers, the product will be even. Therefore, the probability that the product is even is, given that half of the sides of the dice are odd ({1,3,5} vs {2,4,6}) equal to \begin{equation} P(even \; product) = 1 - P(only \; odd \; product) \end{equation} \begin{equation} P(even \; product) = 1 - (\frac{1}{2})^3 = \frac{7}{8} \end{equation}

At a radius of slightly less than $\frac{r}{4}$, the duck can swim in circles, forcing the fox to run around.



Once the duck is at an angle of $\pi$ from the fox, it starts swimming towards the shore.

• The duck has to cover a distance of $\frac{3r}{4}$
• The fox has to cover a distance of $\frac{2\pi \cdot r}{2}$

Since the fox moves four times faster, the distance of the fox has to be larger than four times the distance of the duck.

As we can see, \begin{equation}\frac{3r}{4} * 4 < r* \pi \end{equation} \begin{equation} 3r  < 3.14r \end{equation} \begin{equation} 3  < 3.14 \end{equation} Therefore, the duck will survive!

Since every prisoner can end up dead or alive, there are 2^10 = 1024 possible outcomes. Since 1024 > 1000, it's actually possible to use an approach using binary strings.

• The king assigns each servant a number from 1 to 10.
• The king assigns each bottle a number from 0 to 999.

When he labels them, he writes the number on the bottle in binary with ten digits, like this:

• 0: 000000000
• 1: 000000001
• 2: 000000010
• 3: 000000011
• 4: 000000100
• ...
• 999: 1111100111.

The strategy is simple: the king assigned the prisoners a number from 1 to 10, indicating the position of the number in the binary string. If the string has a number one on the, for example, fifth and sixth position, then the prisoners with number five and six have to drink the wine. After less than four weeks, suppose only prisoners number five and six die. This means the binary representation of poisoned wine has a '1' at position five and six, and the rest are all zeros.

Convert this binary number to a decimal and that gives you the number of the poisoned wine.