java - 在java中使用线程解决建模面试谜语

Question

我最近参加了 Java 开发人员职位的面试。我接到了一项任务:想出一种用 Java 表示电路(如下图中的电路)的好方法。

电路是逻辑门 XOR、AND、OR 等的组合。每个门都有两个输入端口和一个输出端口。每个输出都连接到另一个门的输入，一直到更高的门(如图所示)。使系统简单，不允许有循环(尽管现实生活中的电路可以有循环)。我被要求考虑使用以下准则在 Java 中表示此模型的好方法:

我得到了一个电路和一个应该提供给它的输入的值列表。 我需要创建一个模型来表示 Java 中的电路，即我需要定义可用于表示电路的类和 API。 根据输入值和门的连接方式，我需要计算所表示的电路将产生的输出。 我需要考虑一种方法来表示板，使用抽象类或接口(interface)，并展示对模型的理解(如果需要，还可以使用模式设计)。 我选择将系统设计成一棵树，面试官告诉我这是一个不错的选择。然后我构建这些类: 一个门:

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;
    }
    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 != this.left_c ?  this.left_c.compute()  :  main_class.arr[main_class.counter++]);
        final int right = (null != this.right_c ?  this.right_c.compute()  :  main_class.arr[main_class.counter++]);
        return op.calc(left, right);
    }   
}

抽象运算符

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

或门:

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

和门:

public class and extends Oprtator {
        public int calc(int x, int y){
            return (x&y);
        }
}

大门上的一棵树:

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;
    }


}

和一个主类:

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

 

    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(t.head.compute());
    }
}

在上面的代码中，我将棋盘实现为一棵树，它有一个当前头部(可以向下延伸到左/右子节点)。每个节点都有 2 个子节点(也是节点类型)、2 个条目 (0/1)、一个值和一个运算符(抽象类，可以通过 OR/AND.. 扩展)。

我使用一个计数器和一个数组将值插入树的适当叶子(如代码中所述)。

但后来我的邀请者希望我使用线程，因为将代码变成并行计算，例如每个线程将接收一个门(我必须决定)并进行独立计算，他将传递给直到.. 直到设置最终值。 我有点不知道该怎么办... 有人有什么建议吗？ 非常感谢!

Answer 1

因为我不是 Java 程序员，所以我只能给你一个大概的想法。

首先区分门和树节点。

准备:

1) 将每个门实现为一个类/对象。它必须有 2 个属性:输入 A、输入 B 和计算结果的方法；

2) 实现一棵树。每个节点都是一对(gate，next_node)。 Root 是 next_node 为 null 的节点。叶子是没有其他节点指向它的节点。

3) 使用节点的共享(线程安全)队列。它最初是空的。

4) 有一个固定数量(选择一个，不依赖于门的数量)的线程不断等待队列中的元素(除非达到结果，在这种情况下它们会退出)。

循环:

1) 每当节点上出现输入时，将该节点放入队列中(在开始时输入转到叶子)。这可以通过在门上定义 add_input 方法来简单地实现。

2) 一个线程从队列中取出一个节点:

3.1) 如果其中一个输入丢失，丢弃它(当第二个输入出现时它会再出现一次)。另一个想法是仅当两个输入都存在时才将节点放入队列。

3.2) 如果两个输入都存在，则计算结果并将其传递给 next_node 如果它不为空(并将 next_node 放入队列中)。如果 next_node 为 null，那么这就是您的结果 - 打破循环并完成。

虽然那里没有真正的循环，但我说的是“循环”。等待节点的线程就是循环。

所以基本上这个想法与你的相反。在您的想法中，您从 root 开始并递归计算输入。在我的想法中，您从叶子开始，计算值并将其推送到更高的节点。由于没有完成递归，您可以轻松地在线程之间划分作业。

我不确定这是否是您面试官想要的，但这是我能想到的唯一使用线程的解决方案。