Steve Yegge's five essential phone-screen questions | Hacker News Reader

Steve Yegge's five essential phone-screen questions

steve.yegge.googlepages.com

48 pointsvinutheraj28 comments

An old favorite ...

http://news.ycombinator.com/item?id=94990

http://news.ycombinator.com/item?id=941925

My wife just watched me do this search and trawl through the results, and then she asked me why. Why spend all that time cross-referencing something when the search terms are so vague you need to go through pages to find the duplicates?

The answer is that sometimes I find other items of interest. I don't read HN fanatically, and sometimes items come and go without my seeing them. Occasionally, more than occasionally, one turns up in a search like this, so it's worth doing for the side effect.

it's always difficult to comment on these kinds of posts because, obviously, they're pretty general, and the person doing the interview would need to use their own discretion, etc.

but having said that, one of the example questions seemed a bit odd to me. the idea was to find out whether a candidate knows how to use grep or similar. and the first case is fair enough - phone numbers with a given pattern. but a later example was reformatting code so that parentheses had spaces around them.

now anyone that tries reformatting code with a regular expression deserves everything they get. almost no programming languages have regular grammars, and even if they do, they are probably fiendishly complex (think of comments and strings). to make things worse, if you get something wrong you end up running the risks of introducing some kind of obscure bug in your code...

as i said, maybe i am being too picky. but that was the one example that jumped out as a red flag for the author's experience (which is odd, as i recognise the name, even though i don't really follow personalities on the web much).

edit: thinking some more, maybe i am being too picky. just last night i used sed to change some import statements in python code. but messing around with parens sounds like playing with fire to me. i vaguely remember, years ago, trying to enforce encoding standards with a regexp based rewriter for some obscure language that had no easily available parser. the memory is a blur, except for the pain...

It's a good sign if the interviewee thinks about an RE modifying the strings in a program, though. While programmers who think RE are all-powerful are likely outnumbered by those completely ignorant of them, they're out there. It's important to know REs' limitations - sometimes you need an actual parser. (My favorite example: RFC-822-compliant e-mail address validation - http://www.ex-parrot.com/~pdw/Mail-RFC822-Address.html)

I feel good about all of these questions except the OO design one. I would rather declare types and write functions that operate on those types; granted it's the same, semantically, but if I focus on nouns personally I start coding stupid stuff.

I'm guessing that in an actual interview Yegge would be sympathetic to your point of view:

http://steve-yegge.blogspot.com/2006/03/execution-in-kingdom...

That being said, here's a question: How many people who self-identify as functional programmers could write an OO program competently? Compare and contrast to the question of how many people who self-identify as OO programmers could write a functional progam competently?

Do the paradigms themselves have anything to do with the difference? Or is this strictly an issue of bias for other reasons?

I would guess that almost all functional programmers know OO programming, but very few OO programmers know functional programming.

I think this is just because of pedagogic issues. Every introductory book/class introduces OO, but most undergraduate CS courses barely discuss functional programming (besides a semester on ML or Scheme, if you're particularly lucky).

So, the people who go out off the beaten path to learn functional programming are a self selected subset that is particularly driven, curious, etc.

That would be my conjecture about academia. In business, a certain kind of person learns the languages and paradigms that appear to be well-represented in monster.com job postings.

I do self-identify as a functional programmer, and when I have to write an OO solution to a problem, I often get it wrong. Less wrong when I'm working with a more common idiom (like a tree of widgets), more wrong when I'm striking out into the wild.

In my personal (non-work) work, I don't do objects at all. I just don't find that stateful solutions sit right with me.

I think you have to be realistic here. Sure, functional concepts are arguably more powerful than OOP concepts. But if you can't understand OOP, how are you going to work in a Java/C++ shop like Google (where presumably Steve Yegge would be giving you a phone screen).

It should be noted that Steve has said elsewhere that he can't use these questions anymore because everyone knows them. Thus, I wouldn't follow this template too closely. That said, it's a good way to get a general idea about how to ask these kinds of questions.

Those particular questions are now toast, but the essay was always about the five subjects he asks about.

That's a problem for everyone. We (like many other organizations) use third party recruiters, and the latest ad one of them has put out very clearly indicates that they've been quizzing (unsuccessful) candidates about what we asked, and are now trying to coach candidates in them. Unfortunately said recruiter is non-technical and a) the ad now makes no sense (e.g. if I ask "what is a deadlock?" it doesn't translate into "must have 5 years of experience of deadlocks") and b) some of the canned answers they've been giving to our questions are wrong, so we get a stream of candidates all parroting the same wrong thing.

It'd make me laugh if somebody's resume listed "5 years experience with C++, deadlocks, linking errors", though. :)

No joke, one dude I interviewed claimed so-many years experience of C++, it turned out he meant experience of running programs written in C++ on his PC (!)

I really am utterly mystified why people do this. It was the first skill he listed. Did he not think an interviewer might ask him about it? And even on the offchance he blagged his way through the interviews, he's not going to be able to fake it to the machine and he'll be found out on his first day. It really shakes my faith in human nature, interviewing :-(

The sample code for reversing a string in Java reminded me of why I can't bring myself to use Java-the-language anymore. Clojure FTW!

Am I the only one who thinks that his "Example 2: Write function to compute Nth fibonacci number" is a terrible resource hog?

IMHO an iterative approach would be the way to go.

So, so many people miss the point(s) here.

Firstly, in my direct, personal experience, just writing a candidate to write a program that compiles and runs gets rid of up to 90% of applicants. People here on HN are exceptional, but around 90% of recent applicants for a position I advertised couldn't write a FizzBuzz program that compiled and ran.

Secondly, these are the starting points. From here you can ask what problems the program has. Yes, it's exponential in stack and runtime. You can write an iterative version that runs in constant stack and linear time. More subtle, and more probing, is how do you write a recursive version that also runs in small stack and time.

These are the starting points, the initial cull. Don't assume they're the be all and end all.

On paper? Or with a computer and compiler/interpreter?

Writing pseudocode on paper will shift focus from correcting minor syntax errors to how well they understand concepts, which is arguably more important. It's still worth requiring them to produce at least a tiny piece of working code, though.

I helped interview someone who couldn't explain the trade-offs between a couple different designs for a simple class hierarchy, even an obviously wrong one included as a canary. Then we asked him to write one out, and, after stalling and getting several hints from us, he nervously scratched out a (naive) MySQL schema. Despite what his resume claimed, his only programming experience consisted of PHP and a fairly shallow understanding of SQL.

Some couldn't produce either.

I look for someone to sketch a correct algorithm using any notation they choose. Independently I look for someone to produce working code with an editor and compiler. The former is usually for something like linked lists or quicksort, the second for something like FizzBuzz and then recursive and iterative Fibonnaci.

Working code is essential for something, anything, at some point, although really what I want is someone who can then talk sensibly through the issues. Even so, working code for trivial problems is still only seen in about 10% of cases.

I like to ask candidates to write real code (not pseudocode) on paper, but emphasize to them that I don't really care about superficial syntax errors. Most of the point of this is not in seeing the code they produce, but in watching them think and seeing how they react to questions and suggestions.

Entirely correct. The purpose of a phone screen is to rule out the cases where a candidate will come in, be scheduled for 6-8 hours of interviews and receive a "no" from every interviewer.

Recursive Fibonacci numbers are also a good way to work Memoization into the picture.

No, the iterative approach is only marginally less terrible. If, for some strange reason, you actually need a Fibonacci function that's efficient, you have two choices, depending on the return type:

Are you returning a machine integer (long or otherwise)? Precompute them and use a freaking lookup table. The sequence grows so fast you'll never see more than maybe 60 or so terms.

Are you returning an arbitrary-size bignum? Use the closed-form solution based on powers of the golden ratio. It still runs in non-constant time (bignum math isn't free), but will run much faster than pointlessly enumerating the sequence up to that point.

Of course, I would be surprised if anyone asking about Fibonacci numbers in an interview has ever been looking for one of those answers. Usually it's a "FizzBuzz for recursion" question.

I have asked a candidate about Fibonacci numbers in interview. We discussed a number of different implementations, the possibility of memoization, the practical differences between machine integers, machine floating-point, and bignums, etc.

Incidentally, if you want arbitrary-sized bignum results as quickly as possible, you might do better with a "matrix-squaring" approach (equivalently: use the recurrences that give you F(2k) and F(2k-1) in terms of F(k) and F(k-1)) so that you stick with integer arithmetic.

If your bignum library isn't clever about multiplication, I suspect that the simple iterative solution is about as fast as anything else, but most bignum libraries have at least Karatsuba multiplication.

Well, iterative (and smart tail recursive [0]) solutions are going to be roughly O(n) for the nth Fibonacci number, assuming addition is O(1). In bignum territory, addition isn't free, but is still pretty cheap.

The closed form solution involves computing something raised to the power of n, so would be O(log n) assuming nonintegral multiplication is O(1), which is... not so much the case. Given that the (sqrt 5) factors will always be eliminated by the end you can manipulate things to work with only integers, at the expense of complicating the algorithm.

The matrix-based solution, which I had forgotten, is also of the form x^n, so is probably isomorphic to a sufficiently clever handling of Binet's formula that completely avoids the (sqrt 5) terms.

So, yes, good call, the matrix approach is better--you win this round.

[0] The naive un-memoized recursive algorithm, such as the recursive solution in the linked article, is not only not tail-recursive, but manages to have time complexity of precisely O(fib(n)). If that doesn't make you die a little inside, you're made of sterner stuff than I.

With a dumb bignum library addition will be O(d) and multiplication will be O(d^2), d being the number of digits; d increases linearly with index, so to compute the n'th Fibonacci number by naive iteration will be O(d^2), whereas doing it by repeated squaring will involve (ignoring lots of constant factors) one size-n multiply, one size-n/2 multiply, one size-n/4 multiply, etc., so also O(d^2). So, same order of magnitude, but it seems quite possible that the constant factor will be worse.

And yes, the naive recursive approach is a total disaster. Pretty code, though, and if you have language or library support for memoization you can just write the naive recursive function and demand that it be memoized.

No, they are probably not looking for that answer - but failure to accept them (with working code) would be a negative corporate indicator. An interviewer shouldn't look for answers like that because it requires some amount of fibonacci domain knowledge, which, unless the company specifically works with fibonacci (or similar math), would be a pretty odd filter criteria for programmer quality.

Huh. Not impressed. One of my guys, who went on to be one of the ZFS guys, came from 3par. And they had the 3x3 test:

Gives a shit Positive learning curve. Not an asshole.

Make your candidates pass that and you're doing fine.

Reply on news.ycombinator.com