Help!!!! Interview Question

[KevinHall]

Challenge part 2: If you have time left over, write a function in this machine language to compute a factorial

Sweet! We get to write a function that is based on the concept of multiplication with a VM that doesn't have multiplication. Yes!!! I always wanted to write a multiply function that could only use adds and compares!

[gstercken]

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.

[SuperKoko]

• 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.

Yes, it looks like old C code.

Note that, even if it is a really bad programming method, it is legal to don't declare the return type of a function, and its implicit return type is defined to be int by the compiler. So, the prototype of main is correct.
The standard also says that it is legal to don't return any value in the main function (and compilers don't even generate a warning in that case), and the compiler is supposed to automatically return 0.

But i really disapprove this programmation style!

It is also legal to use stdio.h, even if in C++ programmers are supposed to use iostream or cstdio.h if really needed.
Note that even if cstdio.h is supposed to be used by programmers, using stdio.h is better for compatibility with old compilers (for example Borland C++ 5.0), and works with recent compilers (for now).

[RoboTact]

[*]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.[/list]

It can be done, if return addresses are indexed (all return points are known). You can use special function to return there (L_return in my implementation). Here is recursion solution (I haven't coded part 1, so it's not tested ). Took me 20 minutes though...

; R0 - stack head
; R1 - temporary
; R2 - return code for functions
; R3 = 0
; R4 = 1
; R5 = -1
; R6 - temporary
; R7 - temporary

  MOV R4,1
  MOV R5,-1

  IN R1

; CALL L_fact R1
  MOV R6, 0
  STORE R0, R6
  ADD R0, R4

  STORE R0, R1
  ADD R0, R4

  JMP L_fact
L_ret_0:
  OUT R2
  HLT

// param_-1: value1
// param_-2: value2
L_mult:
; load value1 to R6
  MOV R6,1023
  STORE R6,R0
  LOAD R6,R6

; load value2 to R7
  MOV R7,1023
  STORE R7,R0
  LOAD R7,R7
  
  MOV R2,0
L_mul_loop:
  ADD R2,R6
  ADD R7,R5
  JE R5,R3,L_mul_end_loop
  JMP L_mul_loop
L_mul_end_loop:
  ADD R0,R5
  ADD R0,R5
  JMP L_return

; param_-1: return index
L_return:
  ADD R0,R5
  LOAD R1,R0
  MOV R6,0
  JE R1,R6,L_ret_0
  MOV R6,1
  JE R1,R6,L_ret_1
  MOV R6,2
  JE R1,R6,L_ret_2
  HLT ; runtime error

; param_-1:  value to calculate factorial of
L_fact:
  MOV R6,1023
  STORE R6,R0
  LOAD R6,R6
  ADD R6,R5
  LOAD R1,R6

  JE R1,R4,L_fact_stop
  ADD R1,R5

; CALL L_fact R1
  MOV R6, 1
  STORE R0, R6
  ADD R0, R4

  STORE R0, R1
  ADD R0, R4

  JMP L_fact
L_ret_1:

  MOV R6,1023
  STORE R6,R0
  LOAD R6,R6
  ADD R6,R5
  LOAD R1,R6

; CALL L_mul R1 R2  
  MOV R6, 2
  STORE R0, R6
  ADD R0, R4

  STORE R0, R1
  ADD R0, R4

  STORE R0, R2
  ADD R0, R4

  JMP L_mul
L_ret_2:  
  JMP L_no_ret_1
L_fact_stop:
  MOV R2,1
L_no_ret_1:
  ADD R0,R5
  JMP L_return

Edit:
.. and 8 more minutes to fix some bugs

P.P.S.
It would took another 10-15 minutes to encode in in codes....
unsigned char abyProgram[] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // MOV R0, 0 (at offset 0)
...

[cilu]

Thanks u guys...for a minute I thought that I was the problem...good to know that it's not a good interview question...

I don't know if it's a bad question for an interview.. depends on what for are they hireing people... One hour seems a bit too little...

[RoboTact]

I don't know if it's a bad question for an interview.. depends on what for are they hireing people... One hour seems a bit too little...

It would be OK if they prompt you not just to solve the problem, but "solve as much as you can in one hour". But I think the whole may be done - it wouldn't be well-designed code, but it may work.

[Amn]

Shall we have an honest competition for solving the problem ? We can post our results later, and compare who has the most elegant solution and who was fastest I love competitions !

Nothing is impossible.

[gstercken]

It can be done, if return addresses are indexed (all return points are known). You can use special function to return there (L_return in my implementation). Here is recursion solution (I haven't coded part 1, so it's not tested ). Took me 20 minutes though...

Great! Yeah, the return points are known... Forgot about that. OMG, I'm getting rusty at that stuff...
When I find an hour of spare time, I'll try to implement part 1, so we can test your code...

[Ejaz]

I don't know if I'm right or not (as I don't have anything to confirm that right now), but I think that this problem is taken from the last chapters of "C++: How to program" by Deitel & Deitel.

[JernauGurgeh]

it's a trick question. when your boss (who invariably doesn't know what you are doing) asks you to do something that will take a couple of hours, you always tell them it will take you at least a week so that you can mess around the rest of the time "testing the server ping rate" with HL2 Deathmatch.