That interview question is quite interesting (it don't want to comment here on whether it's a good question for an interview - it depends on the job description). As for part 1, I believe it can be done, although one hour is pretty tough... As for part 2: That virtual machine has no support for calcuated jumps (it only has a conditional (JE) and an unconditional (JMP) instruction to absoulte addresses) - so it's not even a Turing Machine. And since it lacks a Von-Neumann architecture (the memory for the instructions is separated from that for the data), you can't even simulate it by modifying the instructions programmatically - this rules out recursion (which would require a calculated jump to a return address popped from some kind of stack). As for the factorial itself: Yes, it could be done iteratively, of course. But I would roughly estimate that the time alone to type all the instructions required to get a multiplication done only with additions, and, based on that, the factorial, would require more than an hour.

So IMO, good answers could be as follows:
  • A Q&D implementation for part 1 (or a good one, if you're really smart),
  • As for part 2a, point out that it can theoretically be solved, but you can show that it can't be done in the given timeframe due to quantitative reasons
  • and for part 2b (the recursion), explain why it can't be done even theoretically.


In addition, I'd ask the interviewer
  • What they meant by a register "file" - shouldn't that rather be a memory area?
  • Why, in their sample, they used the old <stdio.h> C header in a C++ program
  • Why their main() was not declared as int and doesn't return anything.