I got into an argument with someone regarding an interview question. The question is “write a function to print out the fibonacci sequence”, and then the person went on a rant about someone they interviewed who solved the problem but didn’t use recursion. His argument is that using recursion showed a bit more “programming prowess”, but the problem I see is that with a recursive solution you end up recomputing terms you have already computed (This iteration’s (n-1) is the prior iterations (n-2). In addition, with a recursive solution you have to give an upper bound to the series.
In my mind, a simpler solution would go something like this:
int main() {
unsigned int current = 0;
unsigned int previous = 1;
while(1) {
unsigned int new = current + previous;
printf("%i ", current);
previous = current;
current = new;
}
}
Voila, problem solved without inane stack growth. There are possibly other (even “better”) non-recursive solutions to this problem, but in my opinion, this would be a “good enough” answer if I was interviewing someone. Of course, I rarely am interested in making people write code on whiteboards in interviews, so I probably wouldn’t ask it in the first place, but that’s a different story. This argument reminds me of one awhile back where someone was arguing that you don’t always need to use the bounded string functions in C because sometimes you “know how much space you need”.
P.S. I do realize that without a ceiling on the calculation I will eventually roll the int over, but that’s tangential
P.P.S. Of course using new as a variable name was a bad choice (since it is also a C++ keyword), but again, that is tangential, so stop whining at me about it.
I’d actually argue that it’s better to do it iteratively than recursively, since you’d blow the stack in no time with a recursive function.
I think that the important aspects of this in an interview situation are:
1) can the person solve the problem posed to them
2) can they explain why they went with this
3) can they verbally explain alternatives that might be better or worse, and explain why they didn’t go for them
4) ????
5) PROFIT
Exactly the point I was trying to make…
I had an interview with one company that complained that I made some simple syntatic error in my whiteboard code… That shit drives me crazy…
When I am interviewing someone, I want to see their problem solving abilities, not their memorization of syntax. You know what, I’d rather have a co-worker who solved problems like a pro but had to try to compile all their code twice (once to find the syntax errors, once to create object code) than someone who has the exact syntax of C memorized but can’t program their way out of a sack. Programmers refer. It’s common for a programmer to have to RTFM, so if that’s the case, why grill them on bullshit during the interview.
When I am interviewing, I go out of my way to pseudocode any “whiteboard tests” like that so they look as dissimilar to a real language as possible. Sometimes interviewers complain about this, but whatever…
I’m with you. And when I say “i’m with you”…. ;)
seriously though, I agree. I suck with remembering exact syntax. I need reference materials and example code. Once I have that, I can do what I need to do.
I’m good with coming up with a solution, but not always knowing offhand the intricacies of how to implement it. I mean, I might know “I should use a Vector, or a Map template” to accomplish this, and it might be the correct solution, but I can’t remember how to use them without looking at either my old code or example code… and I wouldn’t expect anyone else to remember.
I know where to look for reference… which I believe is more important than memorizing those references.
def fib(n): """Print a Fibonacci series up to n.""" a, b = 0, 1 while b < n: print b, a, b = b, a+bNice. Although I really hate that comma syntax in python, I think it is very unclear.
It’s not very C-like, true, but it’s used consistently, so it doesn’t really bother me any more.
I think it’s stupid to ask someone to do something like that in an interview. “Excuse me,” I would say, “don’t you have my transcript in front of you? Can’t you see that I got an A in programming? What do you think, I sucked cock for that grade?”
About a decade ago I interviewed for a summer job at a law library and they gave me a “test.” I had to put a date stamp on five periodicals. I somehow managed to pass that Herculean feat, and was offered a job at $5.15 an hour. I ended up turning it down for a job cleaning toilets at $8 an hour. Hey, when you need to make money over the summer, I’ll get down on my knees if I have to.
:)
context
What do you think, I sucked cock for that grade? . . . Hey, when [I] need to make money over the summer, I’ll get down on my knees if I have to.
The last sentences of your two paragraphs are funny juxtaposed together. Man, I have a sick mind.
Eh, I interviewed too many ‘A’ students with Master’s Degrees in CS that couldn’t tell me the smallest thing that wasn’t on their PowerPoint slides.
We resorted to these kinds of questions in the end, and it sorted out much chaff.
It was kinda funny though… we asked people if they’ve ever used recursion. So many people had somehow written all kinds of things with AVL trees but weren’t sure they’ve ever used recursion.1 But, the next question after the “have you ever used recusion” was… “write us a function that takes a floating point number to a (positive) integer power. Only one person did it iteratively as a first attempt (countless straight-‘A’ master’s students entirely bungled both their recursive attempt and the iterative attempt that we pushed on them when it was obvious they weren’t going to make it out the other side of the recursion).
1 Yes, I know you can do this stuff iteratively. But, this is the kind of stuff you should have a really compelling reason to do non-recursively.
I’m with everyone else.. Using recursion doesn’t show programming prowess, it shows a complete lack of understanding about when recusion is appropriate to the problem at hand. Adding a function call and a stack bomb when all you need is an assignment and an addition doesn’t make a bit of sense. You use recursion when it makes the solution easier or more elegant, not because you fucking can.