屌丝又“扬言”要找工作了，所以要赶紧准备一下面试。实际上，按照我之前“找工作”的惯例，面试官都很注重项目经验，而对于算法、设计之类的问题，由于我遇到的这些面试官水平堪忧所以基本都难不倒我。不过，还是要准备一下，说不定下次面试的时候挂掉了呢？
下面我就选一些很简单的面试题，看看乃会不会在这些简单的问题上挂掉。
问题 1：写一个单例模式的 getInstance 方法。
问题分析：幼儿园级别的弱智问题，应该随手写出来。
回答 1-1：由于是单例模式，所以不论怎样都应该只有一个实例。万一两个线程同时访问这个方法咋办？那么当然就要加锁控制啦，用 Java 的话直接给方法加上 synchronized 好了，意思差不多的。So easy！
private static DownloadService mInstance;
public static synchronized DownloadService getInstance() {
if (mInstance == null)
mInstance = new DownloadService();
return mInstance;
}
分析 1-1：由于只有创建时才有竞争条件，因此每次访问这个方法都加锁是没必要的，这样写显然会被挂掉。
回答 1-2：对于已经有实例的情况下，直接返回就好了，没必要加锁；如果需要创建，则就需要加锁了。
private static volatile DownloadService mInstance;
public static DownloadService getInstance() {
if (mInstance != null)
return mInstance;
synchronized (DownloadService.class) {
if (mInstance == null)
mInstance = new DownloadService();
return mInstance;
}
}
分析 1-2：OK，可以做下一题了。
备注：根据 KC 提醒，mInstance 需要加上 volatile 修饰，以应对 Memory Barrier。
问题 2：有一个单链表，给你头结点以及一个指定结点的指针，要求删除这个结点。
问题分析：没技术含量的脑残问题，要求急速回答。
回答 2-1：先找到这个结点的前一个结点，然后把前一个结点的指针指向需要删除结点的下一个结点就好啦！
分析 2-1：由于是单链表，要找到前一个结点只能通过头结点，因此时间复杂度是 O(n)，显然掉到陷阱里去了！
回答 2-2：哦，既然不能遍历找到前一结点，那么就采用“狸猫换太子”的方法好了。将要删除结点的数据置为下一结点的数据，并修改当前结点的指针指向再下一个结点，最后删除下一个结点。Done！
分析 2-2：聪明！不过肯定还要考虑一下特殊情况，否则给乃头结点的指针干啥？
回答 2-3：如果是尾结点，则不能狸猫换太子。这种情况只能用头结点找出前一个结点了，不过大部分情况仍然是 O(1)。
分析 2-3：下一题。
问题 3：乃有一个系统里面有 1000 亿条用户名，现在要求找出某个用户，如何设计这个系统。
问题分析：特么这也叫做面试题？哪有这么多用户？全球的人每个人注册 10 个账号都没这么多！目测只有算上外星人才够。真特么脑残的题！
回答 3：这么多记录全部存在内存里面是不行的，因此只能放在外部存储设备上。实际上能问这样的问题的面试官，也主要是想考察一下乃分析问题的能力，谁也不可能在短时间内给出一个合理的方案。
这么一大堆记录如果存储在硬盘上，如果是 SSD 硬盘的话倒还不错。但目前 SSD 硬盘相当昂贵，买这么大一块要花不少钱，如果乃像领导申请这么多预算目测会被喷死，因此放在机械硬盘上是一个经济上可行的方式。机械硬盘的随机访问显然相当耗时，一般需要 10-100 毫秒，如果采用二分法，1000 亿条记录大约需要 37 次硬盘访问，即使一些记录命中缓存，那么平均每条记录需要 0.2 – 2 秒的访问时间，这显然是不行的。
回忆一下以前学的 B+ 树，正好就是为这种硬盘访问所“量身定制”的。硬盘的读取方式是按块读取，这就意味着读取 1 字节和 512 字节没有啥区别，而 B+ 树的每个结点都有 N 个孩子结点。采用这种方式，我们的硬盘访问次数能够压缩在 8 次左右，勉强能够满足需求。
至于 Trie 树，在这种情况下不如 B+ 树好，因为有这么多记录那意味着名字都很长，访问次数会明显高于 B+ 树。
然而实际上这么多记录只用一台机器处理通常是不可取的，最好是采用分布式的解决方案。例如乃可以采用分布式的哈希表，或者使用 MapReduce 之类的来解决这个问题。这个老夫今后再总结一下。