面试题，请指教

1. How to calculate the execution time of a simple instruction “a=3” without writing a program?

怎样计算一个没有写出程序的简单说明“a=3”的完成时间

 答：首先在寄存器中为a变量分配存储空间，然后为其赋值为3，
        根据CPU的频率可以计算出时钟周期，乘以2从而得到该指令的运行时间。

 

2. Show the pseudo code that deletes a node from a single link list. Keep the delete time constant O(1), not O(n). Assume the input p is pointing to the node to be deleted. Hint: just 3 steps.

给出从一个单一的连接目录中删除一个节点的伪代码。保持删除时间不变O（1），不是O（N）。

假设输入P是指被删除的节点，提示：只有3个步骤。

 

 答： q = p->next();
     p->next() = q->next();
     delete q;
个人观点：用空间换时间，把链表每个节点的指针留下作为一个数组，然后可以直接访问每个节点
插入和删除的时间复杂度就是o(1)

 

 

3. Class A generates random integers between -100 and 100 at a random frequency between 0 and 2 seconds. Class B decrements a counter when class A generated a negative integer and increments when class A generated a positive integer. Class B's counter needs to be updated in real time as class A generates numbers.

Show pseudo code when A and B are in different threads

A类产生随意的整数在-100和100之间（在0到2之间随意的一个频率）。当A类生成了一个负整数并且增加一个正数时B类减少了一个计数器。在A类产生数字的时候B类的计数器需要更新。

    当A和B在不同的线程中时给出伪类的代码

 答：
import java.util.Random;

public class CurrentThread {

    public static void main(String[] args) {

       new A();// 实例化类A

       new B();// 实例化化B

    }

 

    class A implements Runnable {// 类A

       Thread th;

 

       static int intRand;// 随机数

 

       Random r = new Random();

 

       A() {

           th = new Thread(this);

           th.start();

       }

 

       public void run() {// 实现抽象方法

           while (true) {

              intRand = 100 - r.nextInt(200);// 随机产生(-100,100)中的整数a

              try {

                  intRand = r.nextInt(2000);// 随机产生数字的周期时间（0，2）秒

                  Thread.sleep(intRand);

              } catch (InterruptedException e) {

                  System.out.println("Thread is Interrupted");

              }

           }

       }

    }

 

    class B implements Runnable {// 类B

       static int count = 0;// 静态变量

 

       public synchronized void deposit(int count) {// 加法

           count += amt;

       }

 

       public synchronized void withdraw(int count) {// 减法

           count -= amt;

       }

 

       public void run() {// 实现抽象方法

第一题貌似说的是，如何不写程序获得一条简单指令“a=3”的执行时间，但是答案我不知道，觉得这个跟具体的执行环境有关系，太复杂说不清。

第二题，p是指向要被删除结点的指针，按你的方法，删除的是p指向结点的下一个结点，所以你肯定错了。
我的步骤是：q = p->next();completelyCopy(p, q);delete q;
其中completelyCopy函数中第一个参数是指向拷贝目标结点的指针，第二个参数是指向拷贝源结点的指针，功能是将源结点完全拷贝（深拷贝）到目标结点。虽然实际上删除的是p指向结点的下一个结点，但是效果确实p指向的结点从链表中消失了（删除）。此步骤序列显然时间复杂度符合0(1)。