Construct a model of an electric circuit in java

Question

I was recently in a job interview for a position as Java Developer. I was given a task: To think about a good way to represent an electric circuit (such as the one in the figure below) in Java.

A circuit is a combination of logic gates XOR, AND, OR etc.. Each gate has two input ports and an output port. Each output is connected to an input of another gate, which goes all the way to a higher gate (as in the picture). Make the system simple, no cycles are allowed (although real life circuits can have them). I was asked to think about a good way to represent this model in Java, using the following guidelines:

1. I am given a circuit and a list of values which should be provided to its inputs.
2. I need to create a model to represent the circuit in Java, i.e., I need to define classes and an API that could be used to represent the circuit.
3. According to the input values and how the gates are connected, I need to calculate the output that the represented circuit would produce.
4. I need to think about a way to represent the board, use abstract classes or interfaces, and show understanding of the model (and if needed to use pattern design).

I chose to design the system as a tree and the interviewer told me it was a good choice. Then I build those classes:

Node

public class gate_node {
    gate_node right_c,left_c;
    Oprtator op;
    int value;
    int right_v,left_v;
    public gate_node(gate_node right,gate_node left,Oprtator op){
        this.left_c=left;
        this.right_c=right;
        this.op=op;
        right_v=left_v=0;
    }
    
}

Tree

public class tree {
    gate_node head;

    tree(gate_node head) {
        this.head = head;
    }

    void go_right() {
        head = head.right_c;
    }

    void go_left() {
        head = head.left_c;
    }

    static int arr[] = { 0, 0, 1, 0 };
    static int counter=0;

    static int compute(gate_node head) {

        if ((head.left_c == null) && (head.right_c == null))
        {
            int ret=(head.op.calc(arr[counter], arr[counter+1]));
            counter++;
            counter++;
            return ret;
        }
        return (head.op.calc(compute(head.left_c), compute(head.right_c)));

    }

    public static void main(String[] args) {
        tree t = new tree(new gate_node(null, null, new and()));
        t.head.left_c = new gate_node(null, null, new and());
        t.head.right_c = new gate_node(null, null, new or());
        System.out.println(tree.compute(t.head));
    }
}

Oprtator class:

public abstract class Oprtator {
        abstract int calc(int x, int y);
}

OR gate:

public class or extends Oprtator {
        public int calc(int x, int y){
            return (x|y);
        }
}

In the above code, I implemented the board as a tree with its a current head (which can go down to the left/right children). Every node has 2 children (also node type), 2 entries (0/1), a value and an operator (abstract class, could be extended by OR/AND..).

I used a counter and an array to insert the values to the appropriate leafs of the tree (as mentioned in the code).

It works but still I got a feeling that my interviewer wanted something more. Is my code is correct? Does anyone have a better way of represent this electrical board and how to give a good output (in terms of complexity or using better connection from one class to another, design patterns, something else?)

Erective

Well, I would have first spent some time thinking about the input representation, and how to read that representation from a file. Then there are several different ways to structure the data internally and simulate operation. – Lansquenet

(This is based on actually having done this, in FORTRAN, 38 years ago.) – Lansquenet

They may have been looking for a simulation, rather than a logic model, involving a timing model, listeners (probably), et al. – Phosphaturia

@EdStaub A timing model would need inputs that are not being supplied, the equivalent of component data sheets, not just names of logical operations. – Bournemouth

@PatriciaShanahan We're brainstorming to try to read the mind of an interviewer. For all we know, they may have been looking for him to ask about whether timing is needed, or not thought it through, or... – Phosphaturia

I've seen models where wiring is something that's explicitly modelled - that is, the wires are objects too. Gate constructors don't say what they're hooked up to; instead, wire constructors do. – Phosphaturia

@EdStaub -- IIRC, my FORTRAN system used a gate list and a wire list. Say what each gate is and separately which pin goes to which pin. – Lansquenet

My initial thoughts when reading the code are that this guy is used to programming in something other than Java. Classes should start with a capital and you should use camelCase instead of underscores. Plus you spelt operator wrong, plus static methods so not particularly OO. You see code like this all the time when someone converts from one language to another. If there was a lot of competition for the job then that could be enough to miss out. – Pliocene

Answer 1

It's not a "perfect" answer, but you can solve this using a few classes to hold the logical connection/evaluation and then recursively evaluate the circuit.

Create a base class LogicalNode and give it a list of inputs to manage. Give it a base class function to evaluate all the inputs and return an output. This gets overridden in derived classes. Each type of node (INPUT, NOT, AND, OR) gets a derived class with a special "ComputOutput" overridden version. If you compute the output at the output node, it should recurse up the tree, computing all inputs of inputs of inputs, etc., till it reaches the "INPUT" nodes, which are fixed/logical inputs to the system.

You can create new types fairly quickly (see code). Not a lot of comments here, but it should be somewhat self explanatory.

Something like this (in C#):

public class LogicalNode
    {
        private List<LogicalNode> _inputs = new List<LogicalNode>();
        private String _name = "Not Set";


        public override string ToString()
        {
            return String.Format("Node {0}", _name);
        }

        public void Reset()
        {
            _inputs.Clear();
        }

        public void SetName(String name)
        {
            _name = name;
        }

        protected List<LogicalNode> GetInputs()
        {
            return _inputs;
        }

        public void AddInput(LogicalNode node)
        {
            _inputs.Add(node);
        }

        protected virtual bool ComputeOutputInternal()
        {
            return false;
        }

        public bool ComputeOutput()
        {
           // Console.WriteLine("Computing output on {0}.", _name);
            return ComputeOutputInternal();
        }
    }

    public class LogicalInput : LogicalNode
    {
        private bool _state = true;

        public void SetState(bool state)
        {
            _state = state;
        }

        public bool GetState() { return _state; }

        protected override bool ComputeOutputInternal()
        {
            return _state;
        }
    }

    public class LogicalAND : LogicalNode
    {
        protected override bool ComputeOutputInternal()
        {
            List<LogicalNode> inputs = GetInputs();
            bool result = true;
            for (Int32 idx = 0; idx < inputs.Count && result; idx++)
            {
                result = result && inputs[idx].ComputeOutput();
            }
            return result;
        }
    }

    public class LogicalOR : LogicalNode
    {
        protected override bool ComputeOutputInternal()
        {
            List<LogicalNode> inputs = GetInputs();
            bool result = false;
            for (Int32 idx = 0; idx < inputs.Count; idx++)
            {
                result = inputs[idx].ComputeOutput();
                if (result)
                    // If we get one true, that is enough.
                    break;
            }
            return result;
        }
    }

    public class LogicalNOT : LogicalNode
    {
        protected override bool ComputeOutputInternal()
        {
            List<LogicalNode> inputs = GetInputs();
            if (inputs.Count > 0)
            {   // NOTE:  This is not an optimal design for
                // handling distinct different kinds of circuits.
                //
                // It it demonstrative only!!!!
                return !inputs[0].ComputeOutput();
            }
            return false;
        }

And then to (quickly) test it:

static void Main(string[] args)
        {
            // The test circuit
            // !((A&&B) || C)
            // A    B   C   Out
            // 1    1   1   0 
            // 1    1   0   0
            // 1    0   1   0
            // 1    0   0   1
            // 0    1   1   0
            // 0    1   0   1
            // 0    0   1   0
            // 0    0   0   1
            // 
            //
            //
            /*     -------     -------
             * A - |     |     |     |
             *     | AND |-----|     |    -------
             * B - | (D) |     |     |    |     |
             *     -------     | OR  |----| NOT |----
             *                 | (E) |    | (F) |
             * C --------------|     |    |     |
             *                 -------    -------
             */

            LogicalInput A = new LogicalInput();
            LogicalInput B = new LogicalInput();
            LogicalInput C = new LogicalInput();
            LogicalAND   D = new LogicalAND();
            LogicalOR    E = new LogicalOR();
            LogicalNOT   F = new LogicalNOT();

            A.SetName("A");
            B.SetName("B");
            C.SetName("C");
            D.SetName("D");
            E.SetName("E");
            F.SetName("F");

            D.AddInput(A);
            D.AddInput(B);

            E.AddInput(D);
            E.AddInput(C);

            F.AddInput(E);

            // Truth Table
            bool[] states = new bool[]{ true, false };
            for(int idxA = 0; idxA < 2; idxA++)
            {
                for(int idxB = 0; idxB < 2; idxB++)
                {
                    for(int idxC = 0; idxC < 2; idxC++)
                    {
                        A.SetState(states[idxA]);
                        B.SetState(states[idxB]);
                        C.SetState(states[idxC]);

                        bool result = F.ComputeOutput();

                        Console.WriteLine("A = {0}, B = {1}, C = {2}, Output = {3}",
                            A.GetState(), B.GetState(), C.GetState(), result.ToString());

                    }
                }
            }
        }
    }

With output:

A = True, B = True, C = True, Output = False
A = True, B = True, C = False, Output = False
A = True, B = False, C = True, Output = False
A = True, B = False, C = False, Output = True
A = False, B = True, C = True, Output = False
A = False, B = True, C = False, Output = True
A = False, B = False, C = True, Output = False
A = False, B = False, C = False, Output = True

Was this helpful?

Willena

It was thank you. I am still going through your code but it is a new way of thinking for me on this specific modeling problem so again thanks! – Erective

It was a bit of an "inspired" solution. I put it together after reading your post...I had to try it out just to make sure it made sense. It probably won't solve simulations where you need to handle numerical solutions, but for logicals, it just kind of clicked. If you ever want the full VS solution, let me know. – Willena

Answer 2

While I obviously can't say exactly what the interviewer was looking for, if I were interviewing you I would probably press you to make your compute method a non-static member of your gate_node class. This way, your networks do not have to be "balanced" (they can be deeper, have more inputs) on one side or the other.

Put another way, looking at your compute code, I do not believe it would work for general circuits.

Perhaps something like the following (in gate_node):

int compute() {
    /* The following use of a static sInputCounter assumes that the static/global 
     * input array is ordered from left to right, irrespective of "depth".  */

    final int left = (null != left_c ?  left_c.compute()  :  sInput[sInputCounter++]);
    final int right = (null != right_c ?  right_c.compute()  :  sInput[sInputCounter++]);

    return op.calc(left, right);
}

This way, the "tree" can just be represented by the head/root gate_node (although you still probably want a class like your tree class -- I might call it "network" just to avoid confusion, with static methods for constructing the tree, setting up the inputs, etc.) and you trigger the network evaluation by calling head.compute().

Of course, you are still left with the non-trivial problem of constructing a network from some external specification. I imagine that another issue for the interviewer could have been that this aspect was not well-specified in your solution. (Nor in mine here either, I'm sorry.)

Barb

Yeah, an interviewer might have recognized someone with a practical bent because they'd first worry about how to specify the input. – Lansquenet

Thank you, I think you are right.. I will change it to a none static function. From a quick look at my code - do you see any other problems? I'm asking it because I have a second interview there and I'm worried to be asked again about trying to improve this modeling problem and I want to come prepare – Erective