Interviews with Fibonacci | Hacker News Reader

Interviews with Fibonacci

davedash.com

18 pointscoderdude19 comments

The last time I was looking for a job, the subject of Fibonacci as a "Fizzbuzz" or coding screen came up in discussions with colleagues. On a whim, I decided to write the most unlikely implementation possible and blog about it so that when someone asked about Fibonacci in an interview, I could say "Oh yes, I blogged my answer to your question in advance."

https://github.com/raganwald/homoiconic/blob/master/2008-12-...

As it happens, I have never been asked to code Fibonacci. But if I ever am asked... I'll be ready!

This is more of a meta question/comment, but so far in my entire professional programming career (10+ years), I've never been interviewed in a way that required any programming tests or proof of ability. Instead I've always been hired by reputation or referrals and thus skipped past such things. Is that common or unusual?

Most of the interviews I've been to involved coding. The only one that didn't was my first - but they required a code submission.

My reputation/referrals have allowed me to skip parts of the process but never the whole thing (I've skipped phone screenings, for example). I haven't been in the industry as long as you (~6 years) which might have something to do it. Also, you may be well known whereas I am not.

I would consider it someone unusual, and a red flag for your employers. In my experience the better the company is, the more likely it is to require people they are interviewing for a programming job to demonstrate some proficiency for programming.

As an extreme example, you aren't going to get a job at Google without spending several hours coding at the whiteboard.

Why is this? Well first of all, most candidates can't actually program. Asking them to weeds out a lot of the chaff. Of course there are people who obviously won't have trouble with the simple questions. But if, on general knowledge and someone's say-so, it is obvious that they meet your bar, then the odds are good that they are better than what your company expects. If you're happy to always be better than those around you, this is fine. But if you want to land in a more demanding environment, it won't be obvious to anyone, including you, that you meet the standard. And so they will need you to demonstrate somehow that you do.

If they don't, that is a red flag. It either means that they are not selective enough to guarantee decent co-workers, or you're so clearly above the bar that you're not going to have co-workers in your league.

I don't care too much about efficiency.

As a corollary to this, I often ask this same question as my opening question when interviewing candidates, and I find that asking what the big-O runtime of their proposed solution is is also a good indicator of talent/knowledge.

For example, if they answer with a recursive solution (return fib(n-1) + fib(n-2)) but are unable to figure out why it's performance will be worst than linear, then this is a red-flag on the topic of being able to analyze and compare different algorithms. If they answer with recursive and say "oh yeah the performance of this stinks but the code is elegant, I can re-write this to be linear" then it's a good sign.

I recently wrote an interpreter in C for a made up language. As a test of its performance, I coded up a powmod function, powmod(a, e, n) = a^e mod n (where ^ is power not xor). The program contained the lines:

   if (n % 2 == 0) return (powmod(a, n/2, p) * powmod(a, n/2, p)) % p;
   else return (powmod(a, n/2, p) * powmod(a, (n+1)/2, p)) % p;

The embarrassing thing is that even after having spent years writing mathematical code, it took me ages before I figured out it was not my interpreter, but this algorithm that was so ridiculously slow. Fortunately the interpreter is now really fast!

"I don't ask this problem, because I'm dying to know the 12th digit of the fibonacci sequence. I already know that's 144."

That was certainly news to me. Who would have thought that the 12th _digit_ of the Fibonacci sequence is 144.

Interesting problem: for what base (if any) is this actually true. Now there's an actual interview question!

Your problem is either ill-specified or trivial. The trivial answer is any base greater than 144, allowing all numbers up to that point to be one-digit each. Since to have a 144 "digit" we must already be in base > 144, as chosen by what appears to be your problem, there's no other possible solution. (I'm assuming integral bases to keep things well-enough contained for a simple HN post here.)

"Ill-specified" is if you're still playing fast-and-loose with the meaning of "digit"; I've tried to adopt the closest meaning I can come up with where 144 can be a "digit" but in conventional terms the "digit" refers not to the number, but the encoding, in which case 144 can't be a "digit". It may be the ordinal identifier of some digit, but it is not itself a digit, which by definition is a single atomic unit in your number digitization scheme. (That is, your atomic glyph may itself be encoded by multiple glyphs in another scheme, I could imagine representing base 1296 numbers (36 times 36) by definition as two base36 numbers with the obvious English encoding, but in the base1296 encoding a "digit" would be two alphanums in the English encoding. Gotta make sure to keep all the layers straight; there's the abstract number, there's the digit breakdown in a given base, and there's the serialization of those digits in some concrete format.)

The trick with such questions is finding an interpretation which is neither over nor underspecified and for which the answer is not obvious.

The question only supposes that 144 is a digit in the base.

We might also write the fibonacci sequence in whatever base is chosen, i.e. the fibonnaci sequence is no longer

1, 1, 2, 3, 5, 8, ....

but may be

31, 31, 32, 33, 39, ....

To keep the problem simple, let's suppose that our digits are represented by glyphs which just happen to be composed of ordered sequences of decimal digits and that the glyph m corresponds to a lesser digit than the glyph n only if m < n when considered as decimal numbers. Thus we could have 37 < 144 but not 144 < 37 for glyphs 37 and 144.

This already places some hard restrictions, e.g. as 144 is a digit, 1 and 4 cannot both be digits.

Now I think the problem is neither trivial, nor overspecified (though I didn't actually check the latter). I certainly agree it was underspecified.

I applied for a company where a significant portion of the first phone screen was devoted to basically making sure I knew what modulus was.

After the screen, I asked them about what percentage of applicants failed - it turned out it was something like half. Sad.

I guess the OP does not realize that a correct solution to his ill-defined "question"

> Print n digits of the Fibonacci sequence

is (in Python): print "1"*n

I find this surprising. Can you please explain?

Sure.

A digit is "a symbol (a number symbol, e.g. "3" or "7") used in numerals (combinations of symbols, e.g. "37"), to represent numbers (integers or real numbers) in positional numeral systems." (Source: Wikipedia)

For example, the number 17 consists of the digits 1 and 7.

So n digits of the Fibonacci sequence is ill-defined. Maybe a reasonable interpretation could be: n digits if you concatenate Fibonacci numbers. (At least, that was my working interpretation while reading the post until I realized that the OP had no idea what a digit is.) Since the question does not ask for the first n digits, you can choose any digit. I assume the Fibonacci sequence has n "1"s (actually I have no proof for that, but since the Fibonacci numbers are infinite it is reasonable assumption IMHO). Hence: print "1"*n

Ah. I was hoping that the behaviour of "1"*n was interesting :-)

Huh. I'm thinking I might very well not want to be hired by someone who doesn't know the difference between a digit and a number. What an odd thing...

Are you sure he doesn't know the difference? He may have banged out the post in a hurry. English may not be his first language. He may know the concepts very well but be unclear on the terms.

If I were interviewing someone and they seemed to get the terms wrong, I would simply ask them "Do you mean number instead of digit?" If they sheepishly say, "Oh yeah!" I would carry on and forget about it. No big deal.

You may have a different view, of course. But for me, getting this wrong is like getting the terms "pass by reference" and "pass reference by value" mixed up. It's worth clarifying, but hardly a sign someone is irredeemable :-)

Sure, it all depends on context. If I'm talking with someone and he's obviously knows what he's doing, then I'd certainly make allowances.

At the same time, you'd certainly hope that an interviewer had the basic English-language terms down pat for one of his standard interview questions. (Presuming he's giving interviews in English, of course!) It's not a single mistake here, it's jumbled throughout the article in a fashion that makes the simple question sound much more complicated than it is.

For what it's worth:

    my @fib := 0, 1, *+* ... *;
    my @fib-digits := @fib.map(*.comb).flat;

Okay, I guess given an adequately expressive language, the problem still isn't very interesting even if you're really asking about the digits. :)

The answer looks like he's looking for something closer to:

   >>> print [1]*5
   [1, 1, 1, 1, 1]

Reply on news.ycombinator.com