Build a circuit model in java

Question

I was recently interviewed as a Java developer. I was given the task: to think of a good way to represent an electrical circuit (for example, the one shown in the figure below) in Java.

image for illustration http://oi40.tinypic.com/nnr4wj.jpgg

The 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 the input of another shutter, which extends to a higher shutter (as in the figure). Make the system simple, no cycles are allowed (although real-life schemes may have them). I was asked to think of a good way to introduce this model in Java using the following guidelines:

• I have been given a diagram and a list of the values ​​that must be provided on its inputs.
• I need to create a model to represent the schema in Java, i.e. I need to define classes and APIs that could be used to represent a schema.
• In accordance with the input values ​​and how the gate is connected, I need to calculate the output that the presented circuit will represent.
• I need to think about a way to represent the board, use abstract classes or interfaces and show an understanding of the model (and, if necessary, use a template).

I decided to create the system like a tree, and the interviewer told me that this is a good choice. Then I create these 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; } } 

Wood

 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 the current head (which can go to left / right children). Each node has 2 children (also a node type), 2 records (0/1), a value and an operator (abstract class, can be extended by OR / AND ..).

I used a counter and an array to insert values ​​into the corresponding leaves of the tree (as indicated in the code).

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

Answer 1

This is not an “ideal” answer, but you can solve it using several classes to conduct a logical connection / evaluation, and then recursively evaluate the circuit.

Create a base class, LogicalNode, and give it a list of inputs to control. Give it a base class function to evaluate all inputs and return output. This is overridden in derived classes. Each node type (INPUT, NOT, AND, OR) receives a derived class with a special overridden version of ComputOutput. If you are calculating the output of the node output, it should recursively process the tree, calculating all the inputs of the inputs, etc., until it reaches the "INPUT" nodes, which are fixed / logical system inputs.

You can quickly create new types (see code). There are not many comments here, but this should be somewhat 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 (quickly) test it:

 static void Main(string[] args) { // The test circuit // !((A&&B) || C) // ABC 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 an exit:

 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?

Answer 2

Although I obviously cannot tell you exactly what the interviewer was looking for, if I were interviewing you, I would probably click on you to make your compute method a non-stationary member of your gate_node class. Thus, your networks do not have to be “balanced” (they can be deeper, have more input) on the one hand or the other.

In other words, looking at your computational code, I do not believe that this will 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); } 

That way, a “tree” can simply be represented by head / root gate_node (although you probably want a class, like your tree class, I could call it a “network” to avoid confusion, with static methods for building a tree, input settings, etc.), and you call the network estimate by calling head.compute() .

Of course, you still have a non-trivial problem of building a network from any external specification. I believe that another question for the interviewer could be that this aspect was not well defined in your decision. (And in my case too, sorry.)