Technical Test for PPS applicants. (My own solution)

This is only a task from a recruitment agency.

Technical Test for PPS applicants.

The PPS processor is a simple processing engine that takes a list of numeric instructions processing them and manipulating a stack. The engine processes a list of instructions which form a PPS task. The engine will execute the program and place the results on the stack. The PPS team is very interested in performance so the PPS engine can perform multiple tasks in parallel and has some special instructions to facilitate this.

Instruction	Code	Number Arguments	Description
PUSH	1	1	Pushes the single argument onto the stack
POP	2	0	Removes the value at the top of the stack
DUP	3	0	Duplicates the value at the top of the stack
ADD	4	0	Removes the top two numbers from the stack, adds them and places the result on the stack.
SUBTRACT	5	0	Removes the top two numbers from the stack , Subtracts the top number on the stack from the second number on the stack, placing the result on the stack.
MULTIPLY	6	0	Removes the top two numbers from the stack, multiplies them and places the result on the stack.
DIVIDE	7	0	Removes the top two numbers from the stack , Divides the top number on the stack from the second number on the stack, placing the result on the stack.
ASSIGN_ID	8	0	Take the top value on the stack, removes it and assigns it as an ID to the whole routine. Once given an ID other tasks can reference the result.
PUSH_TASK	9	0	Takes the top number on the stack, removes it and uses it as an identifier to retrieve the result of the task with that identifier, waiting if necessary for the dependant task to complete if not already complete.

Examples

Code sequence	gives  the result
1 2 1 3 4	5
1 5 1 3 5	2
1 20 1 30 6	600
1 20 1 5 7	4

Instruction sequences like the above examples can be batched as parallel tasks and should execute in parallel. This is accomplished by naming tasks with a numeric identifier and referencing them from another task via this identifier. So one sequence or task can take the result of another. It should be possible for a task that uses the output from another to be submitted before its dependency such that it will have to wait until its dependant task is complete before completing.

Parallel Example 

Code sequence	gives  the result
1 100 8 1 2 1 3 4	5
1 200 8 1 4 1 5 4	9
1 100 9 1 200 4	14

Write an implementation of the PPS Engine in Java. Your solution should easy to extend as we plan to add new instructions in the future.

 

My solution

According to requirement of good OO design calls to high cohesion i had to create my own classes hierarchy to fulfil this task. It means each class should fulfil its own particular task.

Class Starter has two static methods. It means, I won't need any instances of this class. His methods make all preparations (they initialize class CommandSequenceParser and class TaskWorksList) for a main worker - class Runner. Each Runner class has his own stack. It means each thread of execution will have his own instance of stack. A private member of class Runner LinkedList<Integer> dataQueue represents a Stack with its methods pool(), peek(), offer(), addFirst().

I want to look closer at math operations ("ADD", "SUBTRACT", "MULTIPLY", "DIVIDE"). For example, those operations' code sequence looks like that: "push on top of stack" (code 1), "a first value" (a first argument - next number from a code sequence), "push on top of a stack" (code 1), "a second value" (a second argument - next number from a code sequence), "Removes the top two numbers from the stack" what means "pool from a top of a stack" "a first value" ( 1st argument), keep it somewhere, then "pool from a top of stack" "a second value" (2nd argument), keep it somewhere and accomplish a math operation with them. This is why, I created class Command which keeps a command's code and its argument. I use that class for inner representation of a single command. It keeps an intermediate value (first argument for a math operation). As a result I am able to prevent such a situation when I have a math operation command, but there are not any argument for that:
                        if (a == null) a = 0; // a is a Integer
                        if (b == null) b = 0; // b is a Integer
                        Integer c = a + b; //nothing + nothing is zerro

But the most interesting things happen with commands "ASSIGN_ID" (code 8) and "PUSH_TASK" (code 9).  They deal with concurrency of threads of execution. Each class Runner executes his own code sequence separately from other threads of execution and doesn't know about their existence. I created class Task to keep ID of a task (which can be applied for it during execution of code sequence), a reference to its own thread of execution, and a result of work of a terminated (dead) thread. Class TaskWorksList deals with all separated threads of execution (in other words, all separate and independent threads of execution deal with this single class). This is a reason why class TaskWorksList has his synchronized methods.

In order to implement "PUSH_TASK" (code 9) command the current thread of execution must find another thread with a certain ID and if that thread of execution is alive to wait when it finish its work and it will be possible to retrieve the result of its work. That it's. Work is done. Checked and built. It was a very interesting challenge for me. I want add only one thing I never be able to describe this my own solution at the job interview due to my difficulties of speaking. I am a very bad speaker at all.