Miracle Interview

Stevey's Drunken Blog Rants™

This is my feedback on a candidate I just finished interviewing. It was an interview neither me nor the candidate is likely to forget any time soon. Background: M.S. computer science with ~2 years of experience, interviewing for SDE-2. Vote: Inclined to hire


I'm inclined... barely. It was one of the weirdest interviews I've ever had. He failed my first three or four questions miserably, so I stopped the interview, told him he was failing badly, explained HOW he'd failed badly, and said he'd better start shaping up in a real hurry. I was nearly ready to stomp out and call the recruiter, asking how we'd brought this guy in.

Oddly enough, he shaped up in a real hurry, and was able to answer a bunch of other hard questions perfectly, modulo a bit of new-found nervousness. It was as if by upping the stakes, I threw him into high gear. Pretty remarkable transformation, all in all.

The stuff he failed:

1) I asked him what languages he knows, and he said C/C++/Java. He doesn't know any others: no JavaScript, no Perl, no nothing. I find this a bit irksome for a professional engineer.

He had some experience with Basic, Pascal and Cobol from school, but his programming languages course from 2 years ago didn't cover anything useful (e.g. Perl/Python/Ruby/JavaScript) or educational (e.g. Lisp/Scheme/Ocaml/SML/Haskell). So his degree was basically a Java certification program.

2) I gave him the "find the phone numbers in 50,000 html files" question, and he decided to write a huge program with an ad-hoc state machine. When I asked how long it would take to write the program, he said he'd have to hit N files, with M lines per file, so... I interrupted him: no, WRITE. How long to WRITE the program? Oh. He estimated it at 5 days of work. At this point I was 50% ready to throw him out.

I told him my team had done this problem last year, and he brightened up and said: "Really? Did you use find and grep and regular expressions and stuff?" Woah. How do you respond to that? So I asked him why the heck he hadn't done that in the first place. He said he'd just sort of assumed it was a C-programming question. He said that with regular expressions in Java, it'd be much shorter, and even shorter using unix utilities. Argh.

3) I asked him to do string permutations, making him scramble the letters of "cat" by hand before beginning with the problem. He wanted to use 2 nested loops. When I asked about 4-letter words, he said he wanted to use 3 nested loops. This made me think of a few 4-letter words myself, right there on the spot.

But I kept them to myself, and instead asked him if he could generalize it. He said, (and I quote): "It may be possible to do it with a recursive solution. But I don't know how to do that right now." And he really didn't want to do it. So I made him. And he fumbled with it, and was being a total loser in the process. He wrote a pseudo-algorithm on the board, then asked me if it was right. C'mon, man. I asked him to hand-simulate it, and he didn't want to. When I insisted, he saw his algorithm wasn't going to work. He just wasn't getting anywhere with the problem, and clearly wanted to throw in the towel because it was recursive. F-word.

3) Maybe worst of all, thus far he was only using the rightmost 1/4 of the board. He began squeezing his text into smaller and smaller spaces in the far right 2 inches of the board. There was this vast expanse of virgin whiteboard to his left, but he started scrunching himself down into the corner so he could reach those last few millimeters of space on the right. I hate it when people do that. Shows a complete lack of attention, a lack of common sense.

That's when I stopped the interview and said: dude, this isn't going well. You've failed every single one of my questions so far. You screwed up the regex question, opting to write a gigantic C program. And you're getting nowhere with this string-permutations problem because it's recursive. Every single candidate we hire can do recursion in their sleep. It's a requirement. You don't know any scripting languages, so you're horribly inefficient (and you demonstrated this clearly during the HTML phone-numbers question, wasting 5 days of my team's time). And what's with the whiteboard space management? Why are you only using the far right 1/4 of the board? This isn't filling me with confidence. (I was writing all these failures as bullet points on the board — I had plenty of space for it.)

I told him if he didn't start doing a LOT better, right now, then it wasn't going to work out. I told him it's perfectly OK to have a bad interview — happens to all of us. If he does well with the rest of the interviews, maybe they can convince me that this was just a fluke. But I told him he needs to be a lot quicker on his feet, and not waste any time.

He took my stern, impromptu lecture very seriously, listening intently and nodding crisply, and said he'd try to do better.

Diving Save

So I asked him the Parking Lot object-oriented design question, outlining the problem requirements and my expectations for it.

He aced it. My definition of "aced" means you get a working but inefficient answer first (meaning you haven't heard the question before), and then you're able to refine it to constant-time park() and retrieve() operations by changing your data structures and method signatures. He did exactly that; in fact he even jumped to the idea of using a hashtable for retrieving cars before I'd thrown that part of the problem at him. Smoked it.

Then I asked him a bunch of stuff about operating systems: threads, processes, synchronization, semaphores and their implementation, IPC, scheduling, interrupts, signalling. My god, he smoked it. All of it. He was in the Zone. He was slightly nervous, but was getting all the answers correct.

Then I jumped into a slightly harder question (the guy DOES have a Masters Degree in Computer Science, after all) had him explain how a compiler works. He was slightly less clueless about this than the average person, and at least knew about some of the phases. But he didn't realize the output of the parser is a tree, and has to be a tree. I wanted to work him up from first principles.

So I wrote an arithmetic expression: "2*(5+3)" and asked him how you'd evaluate it. Predictably, he didn't get any further than he had with the compiler phases, because he wasn't thinking of trees. I asked him to name ALL the data structures in java.util. He said (equally predictably): list, linked list, array list, vector, map, hash map, hashtable, queue, stack, doubly-linked list, array, ...

I started getting mad (well, stern) again, and said: DUDE! You've named off sixteen different LINEAR data structures, and a bunch of MAPPING structures. Are there any OTHER SHAPES for data structures? He thought about it and suggested "trees", and I asked: "did it ever once occur to you that the output of parsing might be a PARSE TREE?"

He thought that sounded right. I only had a minute or two — the next interviewer (Sam) had already arrived. So I switched into overdrive and started giving the candidate direct orders.

First: write that arithmetic expression as a tree. Do it now. He did it pretty quickly, and correctly. Not that it was a hard tree, but I didn't actually explain what I meant by writing it as a tree, and he deduced what I meant automatically, and did exactly the right thing.

Then I said: Write the eval() function, NOW. Assume takes a node as an argument (the root of that tree) and returns a double value.

In under a minute, he'd written more of it than most candidates get in 10 minutes — he had the recursive backbone correct, and was struggling over how to represent the operator. I stopped him and asked how he'd do it, and he said he'd been thinking of using a switch statement. This is the "correct" brute-force first answer I'm usually looking for; so far, so good.

Then I just threw the hard part of the question at him without any more explanation: can you do it with polymorphism? Bafflement. I asked if he knew what polymorphism was. Yes. He stared at the tree, and within 20 seconds had realized what I meant, talked himself into believing that he could do it, and then he described the correct polymorphic solution to me, using Plus/Minus/etc. node classes that each override the eval() operation. Bravo!

I'd call this nothing short of a miraculous diving save. He'd gone from screwing up nearly all my questions to acing nearly all of them. He started off needing a ton of help and requiring prompting for almost everything, and wound up deducing the correct meanings from vague questions with lightning speed. He'd gone from slow and fuzzy thinking to sharp, precise, correct thinking — all because I told him that if he didn't shape up fast, then no yob.

I seriously doubt most candidates would exhibit a similar turnaround in similar circumstances. Most people would probably melt down. I'm almost never a meanie in interviews, but this guy had been wasting my time and wasn't going to get an offer, so I'd had to do something drastic. And it worked!

I can't go so far as to say I'd be strongly inclined, given some of his weaknesses. But I'm definitely willing to make him an offer.

(Published March 18th, 2005)


It makes you wonder how he is going to behave on a team. Is he going to futz around and not apply himself until he is under pressure? I don't know but thats really weird.

Posted by: Eric M. at March 19, 2005 12:20 AM

Dude. Call me an elitist, but if the SDE II candidate doesn't know about trees, recursion, or compilers, that's pretty sketchy.

Did any of the folks on the loop ask him any distributed systems or database questions? Sounds like somebody who's going to leave off a WHERE clause and take down the web site.

Not inclined to hire.

Posted by: Sunny G. at March 19, 2005 10:39 PM

*sigh* ... all of this just reminds me how very very bad I am at interviews.

Posted by: Brian W at March 21, 2005 04:28 AM

Sunny, you're an elitist. :-)

The thing is, he actually did know the stuff, or at least he had understood the principles at one point in his career. His brain had just started the inexorable process of turning into mush because of his lame day-job. People who don't take explicit steps to counter this process — well... mush! mush!

Posted by: Steve Yegge at March 21, 2005 07:30 PM

I like the way that you use "find the phone numbers in 50,000 html files" to see if the candidate is familiar with UNIX-y file/text handling without explicitly saying as much.

But I think this interview is a good example of how the "Interview Game" can interfere with that tactic.

It's a truism that in order to do well on standardized tests, you have to study both the subject matter and the test. No matter how much ambiguity you can philosophically discern in a multiple-choice question, the scantron only accepts one answer. Good students learn to play along, analyzing each question in terms of "what is being tested" before settling on an answer.

The rules of the Interview Game are similar. Here the candidate failed to recognize that you were looking for his awareness of regular expressions and text utilities. He thought the underlying question was "Can you code?"

Maybe a stronger (or simply more assertive) candidate in that position would have anticipated the traps in the construction of an ad-hoc parser and raced ahead to the conclusion: "The only winning move is not to play."

This candidate almost got there: He said it would take him 5 days. Had he been given a time constraint (as in the "5 Essential Questions" version), maybe he would have been tipped off that it was not his coding chops being tested. Was he aware of that constraint?

In any case, it seems to me that the effect of the extra pressure that you applied was to encourage the candidate to abandon the Interview Game — since you made it clear that he wasn't winning — and to answer your remaining questions without trying to interpret or anticipate your expectations. This served him better.

The trouble with the Interview Game — and it's unavoidable to some extent — is that the interviewer has to play, too. Just as the interviewee has to discover what question is being asked, interviewers need to ask themselves, "What question is being answered?"

Posted by: Riley L. at March 21, 2005 08:07 PM

Yes, interviewing is definitely a game. Or a dance. For many questions, it's challenging to come up with a way to phrase it that doesn't give the answer away.

I am always particularly careful to explain, in the html-phone-numbers question, that this is not necessarily a programming question. It's just a problem I need them to solve, e.g. if they were on my team, and I don't care how they do it. It's really a "tools awareness" question just as much as it is a regexp question.

In any case, in the future, I may call time-out on the game more often, rather than just writing the candidate off early in the interview and going through the motions.

Posted by: Steve Yegge at March 21, 2005 08:34 PM

p.s. everyone else on the loop was not inclined. Miracle cancelled, I guess.

Hopefully this entry was at least *mildly* helpful though. I thought it was interesting.

Posted by: Steve Yegge at March 21, 2005 10:57 PM

Hmmmm. I know that when I haven't actively written in a language for over a month, I literally have to look up basic functions (eg perl "open" syntax.) I've actually been known to take my pocket guides to interviews, to not screw up simple stuff. But then I'm a script hack, not an OO programmer. Besides, I have a brain injury, and that means forgetful and easily confused.

Still, the guy had a Masters in CS and couldn't explain how a compiler works? I thought that part of that kind of degree was writing a compiler as an exercise.

Posted by: llaubenh at April 8, 2005 09:14 PM