今天遇到一公司的超难的java面试题，面挂了，求帮忙！

1. 已知一个单链表上有一个节点为数字N，如何快速定位到这个节点并在它的前面插入另一个节点。不能使用遍历，面试官说遍历太慢了，，，
2. 已知有程序操作如下一张表，程序会不定时的去刷新这个表某几行的time为系统当前时间（当然这个表的行数不是固定的，也可能程序去增加或删除）。现在要求写另一个程序，这个程序只能5分钟扫描这张表，如果发现某一行的time已经超过5分钟没有去刷新了，就将state置为“已超时”。如何不用每次都遍历整张表且快速的完成这件事？
id time state
1 9:36
2 8:20 已超时
3 9:32
3. 多个线程去访问某个单例bean，如何设计这个bean，使得多个线程从这个bean中能得到属性日期date，保证不同的线程访问bean得到不同的date，同一个线程访问这个bean又能得到相同的date？
4. 已知一个SQL去查询一张表发现速度好慢，在不改动SQL的条件下如何去分析这个问题（其中索引也建的没有问题）？
5. 我本地想访问第三方的类对象的方法，我手头上没有第三方类的对象，只有接口，如何能实现访问？我说采用类似于jdk里面带的动态代理，貌似对了但是整个思路我还是不懂。
6. 采用负载均衡集群的方式部署了多个tomcat，如何管理session和缓存使得session中的数据和缓存中数据能实时更新？其中缓存我说采用分布式并利用通知的方式，感觉面试官表情好像不对，，，
7. 现在只有4个服务器，每个服务器并发量各40万，突然瞬间会达到1个亿的访问量，该怎么应对或者提前如何部署？
8. Struts2是多例的，比起Struts1和servlet单例的，每次请求都要创建和用户状态有关的对象，Struts2的优势在哪里？
9. 和银行交互时要么调用接口或者发送报文，要用到签名，签名的算法是公开的么？为什么？

有点啰嗦，跪求各路大神解答！对于那种面试现场先给个问题求最佳解决方案，要么是要快要么是访问量要大，看什么样的书或者博客可以快速恶补？求知道！财富金币不是问题！