一个面试题

Question

面试链表getsizerandom

Answer 1

List l
int i=new Random().nextInt();
String tmp="";
public int getStringFromList(int i){
    try{
   tmp=l.get(i);
     }catch(exception e){
       i--;
       getStringFromList(i);
     }
retrun i;}

Answer 2

package www;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class test {
static  int flag=0;
static int tag=0;
static List<String> l=new ArrayList<String>();
public static void main(String[] args){
int i=new Random().nextInt(20);
System.out.println(i);
flag=i;
tag=0;
l.add("1");
l.add("2");
l.add("3");
l.add("4");
l.add("5");
l.add("6");
l.add("7");
int k=getStringFromList(i);
System.out.println(k);

}
public static int getStringFromList(int i){
String tmp="";
    try{
         tmp=l.get(i);
     }catch(Exception e){//跑出异常
      tag++;
      if(i>flag){
     return i-1;
      }else{
          i--;
          return getStringFromList(i);
      }
     }     if(tag==0){
           i++;
           return getStringFromList(i);
     }
   
   return i;
    }
}

Answer 3

public int checkIndexPosition(Vector<String> strList, int index){
if(strList == null){
return 1;
}

try{
String str = strList.get(index);
}catch(Exception e1){
//index out of range
return 1;
}
try{
String str2 = strList.get(index+1);
}catch(Exception e2){
//index is last index
return 0;
}
//else index inside range
return -1;
}
public int getLength(Vector<String> strList){
if(strList == null){
return 0;
}
int startIndex = 0;
if(checkIndexPosition(strList, startIndex) == 0){
//start index is last index
return 1;
}

int endIndex = Integer.MAX_VALUE-1;
if(checkIndexPosition(strList, endIndex) == 0){
//end index is last index
return endIndex+1;
}

Random random = new Random();
int index = 0;
int range = Integer.MAX_VALUE;
while(true){
range = endIndex - startIndex;
//get index between start and end index
index = random.nextInt()%range + startIndex;
int result = checkIndexPosition(strList, index);
if(result == -1){
//random index is inside range, replace old start index
startIndex = index;
}else if(result == 0){
//index is last index
return index+1;
}else{
//random index is out of range, replace old end index
endIndex = index;
}
}
}

Answer 4

import java.util.LinkedList;
import java.util.List;/**
 * 给定一个String链表，长度未知。只能用get()方法，用random来产生i。 不能用size方法。 如何决定这个链表的长度。
 * 
 * @author user1
 * 
 */
public class FaceTest {
public static void main(String[] args) {
int max = 0;
int min = 0;
List<String> list = new LinkedList<String>();
list.add("a");
while (true) {
int i = (int) ((Math.random() * Integer.MAX_VALUE) % max);
try {
list.get(i);
min = i;
max = max + 10;
} catch (IndexOutOfBoundsException e) {
max = i;
// 两种跳出情况
// 1、最大为零还抛异常
// 2、最大抛异常和最大不抛异常相距为1，并且最大不抛异常大于零
if ((max == 0) || (max - min == 1 && min >= 0)) {
break;
}
}
}
System.out.println("the list len is  " + max);
System.out.println(list.size());
}
}楼主可以试试

Answer 5

初始max为零，对其取余为什么不抛出异常？

Answer 6

初始max为零，对其取余为什么不抛出异常？
java不会抛异常，我这里将其强转为int类型了，如果使用double或者float会得到NaN

Answer 7

初始max为零，对其取余为什么不抛出异常？
java不会抛异常，我这里将其强转为int类型了，如果使用double或者float会得到NaN
请问一下强制转换后得到的int值为多少？

Answer 8

public class TestDes {
    static Integer maxInt=null;
    static Integer minInt=0;
    public static void main(String[] args){
        //新建个列表，长度为150
        List<String> list=new ArrayList<String>();
        for(int j=0;j<150;j++){
            list.add(j+"");
        }
        //随机数
        int i=Math.abs(new Random().nextInt());
        getSize(list,i);//输出150    }
    /**不标准的二分法*/
    private static void getSize(List<String> list,int i) {
        if(maxInt!=null&&minInt==maxInt-1){
            System.out.println("size:"+maxInt);
            return;
        }
        try{
            list.get(i);
            minInt=i;
        }catch (IndexOutOfBoundsException e) {
            maxInt=i;
        }
        getSize(list, maxInt==null?i*2:(minInt+(maxInt-minInt)/2));
    }
}  

Answer 9

初始max为零，对其取余为什么不抛出异常？
java不会抛异常，我这里将其强转为int类型了，如果使用double或者float会得到NaN
请问一下强制转换后得到的int值为多少？
0