Can You Ace the Technical Interview?

This Week's Fiddler

Let the expected value of the desired sum of a line segmnent of length $L$ be $f(L)$, which is defined recursively as:

$$f(L)=\frac{1}{L}\int_0^L{\Big(x(L-x)+f(x)+f(L-x)\Big)\ dx} \\ f(L)=\frac{1}{L}\int_0^L{(Lx-x^2)\ dx}+\frac{1}{L}\int_0^L{\Big(f(x)+f(L-x)\Big)\ dx} \\ f(L)=\frac{1}{L}\Big[\frac{1}{2}Lx^2-\frac{1}{3}x^3\Big]_{x=0}^L+\frac{1}{L}\int_0^L{\Big(f(x)+f(L-x)\Big)\ dx} \\ f(L)=\frac{1}{L}\Big(\frac{1}{2}L^3-\frac{1}{3}L^3\Big)+\frac{1}{L}\int_0^L{\Big(f(x)+f(L-x)\Big)\ dx} \\ f(L)=\frac{1}{6}L^2+\frac{1}{L}\int_0^L{\Big(f(x)+f(L-x)\Big)\ dx}$$

Due to symmetry between $x$ and $L-x$ from $x=0$ to $x=L$, we can rewrite this as:

$$f(L)=\frac{1}{6}L^2+\int_0^L{\frac{2}{L}f(x)\ dx}$$

Expanding the recursive definition, we get:

$$f(L)=\frac{1}{6}L^2+\int_0^L{\frac{2}{L}\Big(\frac{1}{6}x^2+\frac{2}{x}\int_0^x{f(y)\ dy}\Big)\ dx} \\ f(L)=\frac{1}{6}L^2+\frac{1}{9}L^2+\int_0^L{\int_0^x{\frac{4}{Lx}f(y)\ dy}\ dx}$$

Continuing one more step:

$$f(L)=\frac{1}{6}L^2+\frac{1}{9}L^2+\int_0^L{\int_0^x{\frac{4}{Lx}\Big(\frac{1}{6}y^2+\int_0^y{\frac{2}{y}f(z)\ dz}\Big)\ dy}\ dx} \\ f(L)=\frac{1}{6}L^2+\frac{1}{9}L^2+\frac{2}{27}L^2+\int_0^L{\int_0^x{\int_0^y{\frac{8}{Lxy}f(z)\ dz}\ dy}\ dx}$$

This pattern, though I have no formal proof for it (proof by induction, perhaps?), continues as a geometric series! (Note that the terms approach 0 as we continue recursing.) The initial value is $\frac{1}{6}L^2$, and the ratio between terms is $\frac{2}{3}$, making the value of $f(L)=\frac{1}{6}L^2\cdot\frac{1}{1-\frac{2}{3}}=\frac{1}{2}L^2$.

Hence, $f(1)=\frac{1}{2}$.

Answer: 1/2

Extra Credit

There's a "triangle" of probabilities based on the values of $a$ and $b$ because $a+b\le L$. The area of this triangle is $\frac{L^2}{2}$, so our double-integral of expected value must be divided by this. Hence, our recursive definition of $G(L)$ (the expected value of our sum):

$$G(L)=\frac{2}{L^2}\int_0^L{\int_0^{L-a}{\Big(ab(L-a-b)+f(L-a)+f(L-b)+f(a+b)-f(a)-f(b)-f(L-a-b)\Big)\ db}\ da}$$

Using commutivity, we can combine the positive recursive terms into $3f(a+b)$ and combine the negative recursive terms into $3f(a)$.

The first non-recursive term is $\frac{1}{60}$.

The second non-recursive term is $\frac{3}{200}$.

Guessing that it's another geometric series, this makes one with a ratio of $\frac{9}{10}$, making the final answer $\frac{1}{60}\cdot10=\frac{1}{6}$.

Answer: 1/6