I got asked to write a fibonacci function in an interview once, but they were kind enough to say "go sit at your text editor and write it and then read it to us". I was still flustered a little (since I wasn't sure whether to just talk through it or actually say "int fibs open-parent int n close-paren open-brace...") but apparently I passed the phone screen. I did remark that the naive recursive approach was a terrible algorithm, which may have helped.

Of course, I failed their day-long battery of on-site interviews later. But I did get interviewed by the entire development team, plus the CEO. That was kind of fun.