java面试之常见编程题

1.编程实现：二分搜索算法

解答：

public class SearchTest {

/** 被搜索数据的大小 */

private static final int size = 5000000;

public static void main(String[] args) {

long[] data = new long[size];

// 添加测试数据

for (int k = 0; k < data.length; k++) {

data[k] = k;

}

// 要查找的数据

long target = 4970002;

binaryFindTest(data, target);

}

/**

* 二分搜索算法实现

*

* @param data

* 数据集合

* @param target

* 搜索的数据

* @return 返回找到的数据的位置，返回-1表示没有找到。

*/

public static int binaryFind(long[] data, long target) {

int start = 0;

int end = data.length – 1;

while (start

= data[middleIndex]) {

start = middleIndex + 1;

} else {

end = middleIndex – 1;

}

}

return -1;

}

/**

* 二分搜索测试

*

* @param data

* 数据集合

* @param target

* 搜索的数据

*/

public static void binaryFindTest(long[] data, long target) {

long start = System.nanoTime();

int result = binaryFind(data, target);

long end = System.nanoTime();

System.out.println(“binary search position：” + result);

System.out.println(“binary search time：” + (end – start));

}

}

2.编程实现：线程A向队列Q中不停写入数据，线程B从队列Q中不停读取数据（只要Q中有数据）。

解答：

接口中有两个一个是向队列中写push方法 一个是从队列中读。

public interface StackInterface

{

public void push(int n);

public int[] pop();

}

上边接口的实现类。

public class SafeStack implements StackInterface {

private int top = 0;

private int[] values = new int[10];

private boolean dataAvailable = false;

public void push(int n) {

synchronized (this) {

while (dataAvailable) // 1

{

try {

wait();

} catch (InterruptedException e) {

// 忽略 //2

}

}

values[top] = n;

System.out.println(“压入数字” + n + “步骤1完成”);

top++;

dataAvailable = true;

notifyAll();

System.out.println(“压入数字完成”);

}

}

public int[] pop() {

synchronized (this) {

while (!dataAvailable) // 3

{

try {

wait();

} catch (InterruptedException e) {

// 忽略 //4

}

}

System.out.print(“弹出”);

top–;

int[] test = { values[top], top };

dataAvailable = false;

// 唤醒正在等待压入数据的线程

notifyAll();

return test;

}

}

}

读线程

public class PopThread implements Runnable

{

private StackInterface s;

public PopThread(StackInterface s)

{

this.s = s;

}

public void run()

{

while(true)

{

System.out.println(“->”+ s.pop()[0] + “

3 && lines < 21) {

for (int i = lines-1; i >= 0; i–) {

for (int z = 0; z