Question

今天遇到一公司的超难的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. 和银行交互时要么调用接口或者发送报文，要用到签名，签名的算法是公开的么？为什么？

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

Answer 1

交流一下，有些我也不会。^_^
1、数据没有排序的吗？排序了，可以用类似二分法搞。
3、只需用ThreadLocal包装一下这个bean的日期属性即可，简单。
5、有接口直接用spring HttpInvoke远程调用即可。
6、最简单的办法就是使用Terracotta服务器集群tomcat，ecache、quartz、session一站式解决。不那样的，缓存的话，可用memcached。tomcat中的session是复制式，直接在tomcat配置文件就可以吧。如果要实现自己手动更新感觉可以考虑用jms手动传递数据同步。
8、处理效率高了不少，并发效率好、数据更安全。
9、签名的算法是公开的，但是算法相关的密钥是私有的。

追问

第一个题目和第二个题目数据都是无序的，不能排序，面试官说排序消耗时间更久，第5题不能借助第三方的工具，要自己实现，他想听思路，，，~~o(>_<)o ~~

Answer 2

1：应该是考跳跃表，在节点之间建立告诉通道。但是感觉你题目少条件了。。。
2需要花时间想想
3.ThreadLocal每个线程的副本。
4.explain
5.jdk动态代理，如果不用接口可以考虑cglib。
6.redis去做？
7.没遇到过，不知道咋说
8.struts2没用过

Answer 3

写了二年的代码了，发现以上问题还没一个是会的

Answer 4

第一个问题应该是用二分查找法

追问

单链表是没有顺序的