Help!!!! Interview Question

Hi all :
This is an interview question that i was asked to solve. I actually had a block and I couldn't answer it and I left it blank. But ever since I wanted to answer it , but I couldn't ...any help would be appreciated:


Engineer Programming Challenge Problem:

Given a simple virtual machine that has:

1. A program memory where the machine language bytes are stored (a pointer to this buffer will be passed in to your RunProgram function). The interpreter should run the program starting with the instruction at offset 0.
2. A register file of 10 DWORD registers which all start out with a value of 0.
3. A memory of 1024 bytes in size, with all bytes starting out with a value of 0.
4. And the following instruction set:

MOV R#, value Moves the immediate value into the specified register
Encoding: 0x00, byte destregnum, dword value (little-endian form)

LOAD R#, R# Loads the little-endian DWORD from memory at the location specified by the value of the second register and places the value into the first register.
Encoding: 0x01, byte destreg, byte memindexreg

STORE R#, R# Stores the DWORD value in the second register into the memory at the location specified by the value in the first register.
Encoding: 0x02, byte memindexreg, byte srcreg

ADD R#, R# Adds the value in the second register to the value in the first register and stores the result in the first register.
Encoding: 0x03, byte destregnum, byte srcregnum

JE R#, R#,dwOff Compares the value in the first specified register to the value in the second specified register. If the first value is equal to the second value

then jump to the specified absolute offset and continue executing instructions. Otherwise
continue with the next instruction. The offset is absolute from the top of the program.
Encoding: 0x04, byte regnum, byte regnum, dword offset value in little-endian form

JMP dwOff Jump to the specified absolute offset and continue executing instructions. The offset is absolute from the top of the program.
Encoding: 0x05, dword offset value in little-endian form

IN R# Input a decimal # from the user and store into the specified register
Encoding: 0x06, byte regnum

OUT R# Prints out the value of the specified register in decimal form
Encoding: 0x07, byte regnum

HLT Terminates the current program.
Encoding: 0x08 (no other parameters)

Challenge part 1: In one hour, write a well-structured C++ class to interpret this machine language and run well-formed machine-language programs passed in to your class.

Challenge part 2: If you have time left over, write a function in this machine language to compute a factorial (if you really want to impress us, make your function

recursive). Show a declaration like the one below (“unsigned char abyProgram[] = …”) with your solution.

For example, the following program would write out the numbers between 0 and 9:

#include <stdio.h>

main()
{
unsigned char abyProgram[] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // MOV R0, 0 (at offset 0)
0x00, 0x01, 0x01, 0x00, 0x00, 0x00, // MOV R1, 1 (at offset 6)
0x00, 0x02, 0x0a, 0x00, 0x00, 0x00, // MOV R2, 0xA (at offset 12)
0x07, 0x00, // OUT R0 (at offset 18)
0x03, 0x00, 0x01, // ADD R0, R1 (at offset 20)
0x04, 0x00, 0x02, 0x23, 0x00, 0x00, 0x00, // JE R0, R2, 35 (at offset 23)
0x05, 0x12, 0x00, 0x00, 0x00, // JMP 18 (at offset 30)
0x08 // HLT (at offset 35)
};

YourInterpreterClass var;

var.RunProgram(abyProgram);
}

Wow, a real world question in an interview! :rolleyes:

Sounds more like a test question to me. If I were asked this in an interview, I'd have gotten up, and thanked the interviewer for wasting my time. I passed 12 years of school, and 4 years of undergrad work already.

If this were a real world problem, the question should be, "Give me a timeline, with milestones, on when you can implement this."

Just my $0.02...

Viggy

Quote:

---

Originally Posted by MrViggy

Sounds more like a test question to me. If I were asked this in an interview, I'd have gotten up, and thanked the interviewer for wasting my time. I passed 12 years of school, and 4 years of undergrad work already.

If this were a real world problem, the question should be, "Give me a timeline, with milestones, on when you can implement this."

Just my $0.02...

Viggy

---

Exactly my point. Didn't catch the sarcasm?
:p

Looks like they want a guy with experience.
:ehh:They just arent saying that.

You could solve this with a dispatch table.

struct dtbl {
char cmd[8];
int (*fnptr) (unsigned char * data, double dparam);
} MYDISPATCH_TABLE;

QUASI CODE:
0 WHILE COMMANDS LEFT
1 PARSE OUT CURRENT COMMAND
2 LOOP ONCE THRU CMDS TIL COMMAND MATCHES REQ ONE.
3 EXECUTE FUNCTION IN FUNCTION POINTER
4 GO TO STEP 0

ahoodin

Quote:

---

Originally Posted by ahoodin

Looks like they want a guy with experience.
:ehh:They just arent saying that.

ahoodin

---

Yes, but the problem is un-realistic. Has your boss come up to you with a problem along the lines of writing a machine language interpretter, and gave you only 1 hour to solve the whole thing? If so, then I'd suggest looking for a new job.

You can find out a lot more about a person when they are relaxed, not when they are rushing to solve a problem.

Viggy

Quote:

---

Originally Posted by ahoodin

struct dtbl {
char cmd[8];
int (*fnptr) (unsigned char * data, double dparam);
} MYDISPATCH_TABLE;

QUASI CODE:
0 WHILE COMMANDS LEFT
1 PARSE OUT CURRENT COMMAND
2 LOOP ONCE THRU CMDS TIL COMMAND MATCHES REQ ONE.
3 EXECUTE FUNCTION IN FUNCTION POINTER
4 GO TO STEP 0

ahoodin

---

But, the original problem said:

Quote:

---

In one hour, write a well-structured C++ class to interpret this machine language and run well-formed machine-language programs passed in to your class.

---

Isn't a dispatch table more C then C++ like? I'm guessing that the interviewer wants to talk about polymorphism, but doesn't know how to ask an interview-ee the right questions.

Viggy

Thanks guys, but that was a real interview question , i just left it blank , and I said that, i would solve it in my spare time, but really .....i am really getting frustrated becasue I can't solve it....

If those are all the instructions supported I suppose I could write it in less than an hour... :D But I wouldn't probably make the best design and most likely it won't work from the first shot... ;)

PS: take it as a joke...

Quote:

---

Originally Posted by MrViggy

But, the original problem said:

Isn't a dispatch table more C then C++ like? I'm guessing that the interviewer wants to talk about polymorphism, but doesn't know how to ask an interview-ee the right questions.

Viggy

---

Class, struct, very close. Just create an array of objects then.

Some people have said a class and a struct are the same thing.

I have provided a quick solution outline to a complex problem.

Throwing in inheritance would probably complicate matters to making the problem an all year affair. I dont see where the question specifically asks about inheritance. That is circumstantial gusswork. Don't read too much in.

ahoodin

Thanks alhoodin and everyone for your helpand input...I really appreciate it

Quote:

---

Originally Posted by ahoodin

Class, struct, very close. Just create an array of objects then.

Some people have said a class and a struct are the same thing.

I have provided a quick solution outline to a complex problem.

Throwing in inheritance would probably complicate matters to making the problem an all year affair. I dont see where the question specifically asks about inheritance. That is circumstantial gusswork. Don't read too much in.

ahoodin

---

Which helps to prove my point. This is a bad interview question, and not a real world problem at all. The "proper" solution depends on what the interpretation of "well-structured C++ class to interpret this machine language" is. In the real world, there would be a discussion on what is meant by well structured C++.

And then meetings would ensue about who/how/when to implement such class(es); deadlines would be placed on the project; etc., etc.

Man, I gotta get out of the office!

;)

Viggy

Quote:

---

Originally Posted by ahoodin

That is circumstantial gusswork. Don't read too much in.

ahoodin

---

Just too add, what I think is right, what you think is right, and what the interviewer thinks is right are three different things. And, depending on the interviewer, if you and he/she do not share the same thoughts about how to solve a problem, you are automatically not fit for the position.

As I said, this is a bad interview question.

Viggy

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

Quote:

---

Originally Posted by MrViggy

As I said, this is a bad interview question.

---

I admire the practicallity of an employer who wants the best. The question is forward thinking...but actually incomplete. Additionally it is to comprehensive to be answered eloquently in a short period of time.
Many times in business that is the way it is.

The question is bad, reality is bad. The employer attempts to be progressive but probably unfair in the case of an entry level position.
The level of tenacity and technical aptitude demonstrated on this interview will most likely amount to frantic panic on an entry level applicant.

;)

ahoodin

PS If my posts helped, please dont forget to rate. Click the scale and then click on the approve radio button.

Quote:

---

Originally Posted by melzein

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! :lol: :rolleyes: :sick: :eek:

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.

Quote:

---

Originally Posted by gstercken

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

Quote:

---

Originally Posted by gstercken

[*]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 :rolleyes: ). Took me 20 minutes though...

Code:

---

; 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)
...

Quote:

---

Originally Posted by melzein

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

Quote:

---

Originally Posted by cilu

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.

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.

Quote:

---

Originally Posted by RoboTact

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 :rolleyes: ). Took me 20 minutes though...

---

Great! :thumb: 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... ;)

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.

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.