Tech Interview: Aftertaste

Interviews take a lot of energy. In general but this one in particular. And getting through it also deserves a little celebration. Whatever the reason, it is sort of a ritual to go to a nearby food place after. Raw protein wrapped in carbs, if it can be helped.

The place is quiet, well past the rush of a lunch time, well before the noise of an evening. Getting ready your linear utensils and squishing totally reasonable blobs of green stuff onto your units of sustenance, a thought keeps coming back to you:

You pull out a writing device of your choice and a generic white-label wire-bound notebook. You open the notebook on a fresh page and stare at the empty lines for a bit.

There was a class where someone derived a formula for the Fibonacci numbers. Or someone mentioned it. And it was exciting. What was it all about? Something around representing sequences of numbers as polynomials. Was it called generating functions?

Starting simple is usually a good idea. Maybe encoding a list of all ones? In polynomials, the various powers of the variable naturally separate their coefficients. So a sequence $1, 1, 1, 1, 1, 1, \cdots$ could be represented as a polynomial on $x$ with

$$f(x) = 1 + x + x^2 + x^3 + x^4 + \cdots$$

That does not look very useful, but you won’t let that discourage you. This will need some poking around. A fun thing that can be done with polynomials is to multiply it by the variable, so you try that.

$$x \cdot f(x) = (0 +\!)\ x + x^2 + x^3 + x^4 + \cdots$$

Fascinating: This way we shifted the sequence and prepended 0! This now represents $0, 1, 1, 1, 1, 1, \cdots$. Things are emerging from murky depths of memory. Let’s subtract those…

$$f(x) - x \cdot f(x) = 1$$

Now this looks very promising. Suddenly the whole expression becomes very finite. No need to dance around the infinity with ellipsis… Just few small steps later we get

$$f(x) = \frac{1}{1-x}$$

Somehow, this fraction captures the infinite list of ones. While possibly not very useful on its own, this feels like an important piece of a puzzle.

And the whole process reminded you of writing the infinite list of Fibonacci numbers in Haskell.

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

And so you try representing the sequence:

$$\begin{align} \overline{\mathrm{fib}}(x) =& 0 + 1x + 1x^2 + 2x^3 + 3x^4 + 5x^5 + \cdots \\ x \cdot \overline{\mathrm{fib}}(x) =& 0 + 0x + 1x^2 + 1x^3 + 2x^4 + 3x^5 + \cdots \\ \overline{\mathrm{fib}}(x) - x \cdot \overline{\mathrm{fib}}(x) =& 0 + 1x + 0x^2 + 1x^3 + 1x^4 + 2x^5 + \cdots \\ \end{align}$$

It takes a bit of squinting to realize that the right side is a Fibonacci sequence shifted by 2 positions with extra x (elements of which you can kinda see in the Haskell implementation!):

You got almost to the end of that sentence before you realized, all at once, that the interviewer from earlier:

• is sitting right next to you;
• must have been peeking over your shoulder;
• is looking at you with mild interest;
• has mouth freshly stuffed with what looks suspiciously similar to your own food.

Trying to not get too distracted by what just happened you repeat the steps, but with extra $\alpha{}$.

$$\dfrac{1}{1-\alpha{}x} = 1 + \alpha{}x + \alpha^2x^2 + \alpha{}^3x^3 \cdots$$

That is actually very useful! If we find an appropriately shaped expression, this formula allows us to find n-th element in the sequence on its own! And polynomials are easy to sum as we saw earlier. That is handy. So is the pattern for adding two fractions. Now if only we could express this generating function as a sum of appropriate forms…

$$\frac{A}{1-\alpha{}x} + \frac{B}{1-\beta{}x}$$

Next goal is to find $A$ and $B$ such that

$$\frac{A}{x+\frac{1+\sqrt{5}}{2}} - \frac{B}{x+\frac{1-\sqrt{5}}{2}} = \overline{\mathrm{fib}}(x)$$

(arbitrarily putting minus on the side of $B$). It takes a bit of a paper real-estate, but eventually you get to

$$A,B = -\frac{1\pm{}\sqrt{5}}{2\sqrt{5}}$$

Even more paper is burned on re-shaping the denominator to the desired form of $1 - \alpha{}x$.

$$\frac{-\frac{1}{\sqrt{5}}}{1 -(\frac{-2}{1+\sqrt{5}})x} + \frac{\frac{1}{\sqrt{5}}}{1 -(\frac{-2}{1-\sqrt{5}})x}$$

And from there n-th element (coefficient for $x^n$) is:

$$-\frac{1}{\sqrt{5}}(\frac{-2}{1+\sqrt{5}})^n + \frac{1}{\sqrt{5}}(\frac{-2}{1-\sqrt{5}})^n = \frac{(\frac{-2}{1-\sqrt{5}})^n-(\frac{-2}{1+\sqrt{5}})^n}{\sqrt{5}}$$

That sounds reasonable.

The trick is that we don’t need exact value of $\sqrt{5}$. We can treat it as a special symbol for which $\sqrt{5} \cdot \sqrt{5} = 5$. Similar-ish to introducing $i$ for $i \cdot i = -1$.

Or we can see it as polynomials factored with $x^2 = 5$.

import Data.Ratio

data S5 a = S !a !a deriving Show

s5 :: Num a => S5 a
s5 = S 0 1

instance Num a => Num (S5 a) where
    S a b + S c d = S (a+c) (b+d)
    S a b - S c d = S (a-c) (b-d)
    S a b * S c d = S (a*c+5*b*d) (a*d+b*c)
    fromInteger a = S (fromInteger a) 0
    negate (S a b) = S (negate a) (negate b)
    abs _ = error "leave me alone"
    signum _ = error "meh"

instance (Eq a, Fractional a) => Fractional (S5 a) where
    fromRational a = S (fromRational a) 0
    S a b / S c 0 = S (a/c) (b/c) -- This is okay as we only divide by 2 anyway

type T = S5 Rational

fac :: Integer -> Integer
fac n = numerator x
  where
    -- okay, also by s5 but we know it will be like this
    -- and even the last minus does technically not need
    -- to do the rational part.
    S 0 x = ((1 + s5)/2)^n - ((1 - s5)/2)^n

You feel a congratulatory tap on your back. Well deserved. You feel satisfied. But tired too. Actually really tired. You blink, look up at the food-place employee giving you the “we are about to close look”. There is nobody else in here, you are the last customer.

Confused, you stand up, stuff all your stuff into the backpack, say quick thank you and bye and disappear into the night.