I wound up in the same situation in an interview in 2000. They asked me to do Towers of Hanoi nonrecursively. I think I refused. Didn't get the gig. Things worked out anyways (ironically, I wound up at a spinoff of UMich, working for a professor and his postdoc).

If you don't have a degree and you go interview at (what turns out to have been) a Stanford spinoff, brush up on your useless CS 101, is I guess my life lesson there.