面试过几个公司的人都会有笔试经验，不少人有这样的错觉：觉得笔试题挺简单，也做出来了，为啥没有通知面试？其实作为应聘者，一个重要的点需要踩对： 笔试题究竟要考察的是什么点？针对这要考察的点再来审视自己的笔试情况，就知道差距在哪里了。
我们来看一道阿里的题，这题算是结合Leecode的综合运用
题目描述
/**
非常诚挚邀请您参加蚂蚁金服代码评测，请在本地用自己熟悉的语言实现题目，然后在1小时之内回复邮件，内附源码。
请勿上网直接搜答案，因为信任，所以简单~
如有疑问，请及时联系。
实现如下的IP地址黑白名单过滤功能。
*/
public interface IpList {
/**
* 判断指定的ipv4地址是否在当前名单中
* @param ip
* 指定的ip地址值(v4)
* @return true: 在名单中， false: 不在名单中
*/
boolean isInList(String ip);
}
/**
要求
1.'isInList'操作为常数级时间复杂度
2.'isInList'内部操作完全基于内存，不得有网络或文件读取; 对象初始化部分如构造函数则不受此限制(如初始化时可从文件中load ip名单列表)
3.让此工具所能支持的ip列表数量尽可能大(甚至能否覆盖整个ipv4地址空间?), 内存占用尽可能小
4.此工具可能在多线程环境被使用
*/如何审题
从上述题目你看出了什么？我认为你首先应该注意到： 对外只要一个方法， isInList，入参是个String ip ,从这点来说，面试官给你的发挥空间是很大的。为什么这么说？你想 他只约束你 这一个方法，这个方法依赖什么存储，依赖什么内存管理，依赖什么样的IP处理，都是你去决定的，给这种题，我认为公司还是挺尊重候选人的，能让候选人依据自己的特长去选择实现的方法。其次你应该关注什么？肯定是要求啊，4点要求你是怎么理解的？我们一一对标下：
1.'isInList'操作为常数级时间复杂度：
这个要求在做IP白名单匹配的时候时间复杂度不能太高啊，常数级是什么意思？就是说不管你的名单数量有多大，你给我常数级别查找，如果是顺序匹配时间复杂度是 n，肯定是不满足要求的。常数级的时间复杂度，你想到了什么？ Hash 表？ 还有什么结构呢？。。。。。。。
2.'isInList'内部操作完全基于内存，不得有网络或文件读取; 对象初始化部分如构造函数则不受此限制(如初始化时可从文件中load ip名单列表)
这点的要求，你得在初始化时候就把IP名单全部内存化，说明IP的白名单表你可以当做一开始就确定的，重点不会变化来处理，后续的所有操作就用内存进行。其实这点要求是为 第3点要求做准备的，因为要全部内存化，所以你的名单需要占用最少的内存！
3.让此工具所能支持的ip列表数量尽可能大(甚至能否覆盖整个ipv4地址空间?), 内存占用尽可能小
第三点，面试官想考核你有多少众方式来表征ipv4的地址。然后这些方式里面占用内存最少的是那种方式。如果把这点理解透彻了，那么这道题你就基本心中不虚了。那么ip到底该怎么存储？ 直接用string 存储 “127.0.0.1” ？未免太简单了吧。IP地址是多少位？每个段是8位，4个段是32 位。。。32位对应啥类型，好像有点套路了。
4.此工具可能在多线程环境被使用
支持多线程是最基本的要求，其实多线程支持有很多种方式： 比如加锁，但是这个就影响性能了。如果不加锁那么你能保证所有对共享内存的都只要读操作，所有新生成的内存对象不会把内存地址给传递到其他线程，那么也是线程安全的。本题你就可以通过不加锁来实现线程安全，但是你要保证共享内存的初始化是能多线程安全的。
如果这套题你能把这些潜在点的要求全部摸清楚，那么我认为审题是OK的。这个过程大概需要15分钟左右（总体时间要求是1个小时），所以需要快速去决定。
没有按要求做出来，笔试还能救场吗
如果你不是简历太牛逼（有些人因为有特殊的项目经验，是由笔试优待的，但是大多数人是没这个待遇的），笔试就不要在搞不出来的时候交白卷。但是你又没按要去想到解法，这时候你该怎么搞？
1. 首先一点，别直接就说你做不出放弃。这个从态度上就说明你是个轻易放弃的人，大多数公司是喜欢有韧劲的人，能坚持搞定事情的人。你可以跟面试官探讨。有些面试官是愿意给一些暗示性的提醒。但是如果给一些提示性的暗示你还是无解怎么办？
2. 不排除有些情况就是不能按要求想到解法。我建议你按你会的方式去实现，不管是否符合技术要求，你要做到符合公司的文化要求，用人单位是喜欢有毅力坚持忍耐的人，他们希望找到这样的人：不管在什么情况下，都会想着找到问题的解法，做问题的解决者。
总之一点：让别人相信你有搞定事情的毅力以及态度，态度决定一切。
笔试之后还该准备什么
为啥单独把笔试之后这个环节又提出来。是因为有些人在明明笔试之后，后面的面试环节 面试官反过来又跟他讨论笔试内容，结果由于对笔试解法没做进一步的思考导致了面试过程不理想。
比如蚂蚁这道面试题，最理想的内存存储方式是 BitSet ，但是你没想到，你用的是 HashMap<Integer,Boolean> 这样的方式去实现。面试官让你笔试过了，因为他觉得你对内存的使用是有一定的基础的（毕竟大多数人的常规套路就是用HashMap），还是有改进空间的。他肯定会在面试环节跟你再讨论下这个问题。而这个时候你还是坚持你的HashMap 存储，这个时候面试官就会觉得你对代码的追求完美度不够。就会打犹豫了，这个时候有另外的候选人，那么你就是被pass掉的那个。
所以我们在完成笔试题之后，一定要精益求精，去从两个维度思考改进空间：
1） 空间能再优化吗？
2） 时间能再优化吗？
如果对空间没要求，对时间要求更高，能用空间换时间吗（比如可以增加内存让查找效率更高）？
代码
import java.util.BitSet;
public class IpListImpl implements IpList {
private static volatile BitSet lowBS = new BitSet(Integer.MAX_VALUE);
private static volatile BitSet highBS = new BitSet(Integer.MAX_VALUE);
/** 构造器
* @param Ip
*/
public IpListImpl(String Ip) {
int ipInt = changeIpStrToInt(Ip);
if (ipInt < 0) {
highBS.set(ipInt + Integer.MAX_VALUE + 1);
} else {
lowBS.set(ipInt);
}
}
/**换成8位字符串
* @param num
* @return
*/
private static String getByteStr(int num) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 8; i++) {
if ((num & 1) == 1) {
sb.append(1);
} else {
sb.append(0);
}
num = num >> 1;
}
return sb.reverse().toString();
}
/**
* 去除字符串 '.' 然后转成int
*
* @param ip
* @return
*/
private static int changeIpStrToInt(String ipStr) {
if (ipStr == null || ipStr.isEmpty()) {
throw new IllegalArgumentException("illegal string!");
}
//先转成数组
String[] ipArr = ipStr.split("\\.");
//必须数组长度是4
if (ipArr == null || ipArr.length != 4) {
throw new IllegalArgumentException("Invalid ip");
}
if ("128.0.0.0".equals(ipStr)) {
return Integer.MIN_VALUE;
}
StringBuilder sb = new StringBuilder();
sb.append(getByteStr(new Integer(ipArr[0])));
sb.append(getByteStr(new Integer(ipArr[1])));
sb.append(getByteStr(new Integer(ipArr[2])));
sb.append(getByteStr(new Integer(ipArr[3])));
String intStr = sb.toString();
if (intStr.charAt(0) == '1') {
char[] arr = intStr.toCharArray();
arr[0] = '0';
intStr = new String(arr);
return 0 - Integer.valueOf(intStr, 2).intValue();
}
return Integer.valueOf(intStr, 2).intValue();
}
@Override
public boolean isInList(String ip) {
int ipInt = changeIpStrToInt(ip);
if (ipInt < 0) {
return highBS.get(ipInt + Integer.MAX_VALUE + 1);
} else {
return lowBS.get(ipInt);
}
}
public static void main(String[] args) {
String ip1= "0.0.0.0";
System.out.println(new IpListImpl(ip1).isInList(ip1));
String ip2= "127.0.0.1";
System.out.println(new IpListImpl(ip2).isInList(ip2));
String ip3= "255.255.255.255";
System.out.println(new IpListImpl(ip3).isInList(ip3));
String ip4= "128.0.0.0";
System.out.println(new IpListImpl(ip4).isInList(ip4));
}
}
