简答题：什么情况下会引起内存泄漏，有什么方法规避和检查内存泄漏？
代码题：给定一个无序的序列，输出最长有序子序列的长度。例如{100,4,200,2,3,1}，最长有序子序列为{1,2,3,4}，输出4。要求时间复杂度不大于O（n).
选做题：关于任务调度。大意：系统中有很多任务，包括CPU密集型和I/O密集型，每个任务执行时间不一样，而且不断产生新的任务。在保证所有任务会被执行到的前提下，设计一个任务调度算法。
整合答案（不一定正确）
http://www.ibm.com/developerworks/cn/java/l-JavaMemoryLeak/index.html
http://www.blogjava.net/shiliqiang/articles/292452.html
Java的几乎所有内存对象都是在堆内存上分配（基本数据类型除外），然后由GC（garbage collection）负责自动回收不再使用的内存。
Java中对内存对象的访问，使用的是引用的方式。在Java代码中我们维护一个内存对象的引用变量，通过这个引用变量的值，我们可以访问到对应的内存地址中的内存对象空间。在Java程序中，这个引用变量本身既可以存放堆内存中，又可以放在代码栈的内存中（与基本数据类型相同）。GC线程会从代码栈中的引用变量开始跟踪，从而判定哪些内存是正在使用的。如果GC线程通过这种方式，无法跟踪到某一块堆内存，那么GC就认为这块内存将不再使用了（因为代码中已经无法访问这块内存了）。当一个内存对象失去了所有的引用之后，GC就可以将其回收。反过来说，如果这个对象还存在引用，那么它将不会被GC回收，哪怕是Java虚拟机抛出OutOfMemoryError。
Java内存泄露
主要原因：
一、如在C/C++语言中的，在堆中的分配的内存，在没有将其释放掉的时候，就将所有能访问这块内存的方式都删掉（如指针重新赋值）；例如：申请Object对象,并将所申请的对象放入一个 Vector中,如果仅仅释放对象本身,但因为Vector仍然引用该对象,所以这个对象对GC来说是不可回收的。
二、在内存对象明明已经不需要的时候，还仍然保留着这块内存和它的访问方式（引用）
几种典型的内存泄漏：
一、全局集合
在大型应用程序中存在各种各样的全局数据仓库是很普遍的,比如一个JNDI-tree或者一个session table.在这些情况下,必须注意管理储存库的大小.必须有某种机制从储存库中移除不再需要的数据.
通常有很多不同的解决形式,其中最常用的是一种周期运行的清除作业.这个作业会验证仓库中的数据然后 清除一切不需要的数据.另一种管理储存库的方法是使用反向链接(referrer)计数.然后集合负责统计集合中每个入口的反向链接的数目.这要求反向链 接告诉集合何时会退出入口.当反向链接数目为零时,该元素就可以从集合中移除了.
二、 缓存
缓存一种用来快速查找已经执行过的操作结果的数据结构.因此,如果一个操作执 行需要比较多的资源并会多次被使用,通常做法是把常用的输入数据的操作结果进行缓存,以便在下次调用该操作时使用缓存的数据.缓存通常都是以动态方式实现 的,如果缓存设置不正确而大量使用缓存的话则会出现内存溢出的后果,因此需要将所使用的内存容量与检索数据的速度加以平衡.
常用的解决途径是使用java.lang.ref.SoftReference类坚持将对象放入缓存.这个方法可以保证当虚拟机用完内存或者需要更多堆的时候,可以释放这些对象的引用.
三、 类装载器
Java类装载器的使用为内存泄漏提供了许多可乘之机.一般来说类装载器 都具有复杂结构,因为类装载器不仅仅是只与"常规"对象引用有关,同时也和对象内部的引用有关.比如数据变量,方法和各种类.这意味着只要存在对数据变 量,方法,各种类和对象的类装载器,那么类装载器将驻留在JVM中.既然类装载器可以同很多的类关联,同时也可以和静态数据变量关联,那么相当多的内存就 可能发生泄漏.
如何检测和处理内存泄漏
如何查找引起内存泄漏的原因一般有两个步骤:第一是安排有经验的编程人员对代码进行走查和分析,找出内存泄漏发生的位置;第二是使用专门的内存泄漏测试工具进行测试.
一、在代码走查的工作中,可以安排对系统业务和开发语言工具比较熟悉的开发人员对应用的代码进行了交叉走查,尽量找出代码中存在的数据库连接声明和结果集未关闭、代码冗余等故障代码.
二、使用一些工具来检查Java程序的内存泄漏 问题.它们的基本工作原理大同小异,都是通过监测Java程序运行时,所有对象的申请、释放等动作,将内存管理的所有信息进行统计、分析、可视化.开发人员将根据这些信息判断程序是否有内存泄漏问题.这些工具包括Optimizeit Profiler,JProbe Profiler,JinSight , Rational 公司的Purify等
处理内存泄漏的方法
一旦知道确实发生了内存泄漏,就需要更专业的工具来查明为什么会 发生泄漏.JVM自己是不会告诉您的.这些专业工具从JVM获得内存系统信息的方法基本上有两种：JVMTI和字节码技术(byte code instrumentation).Java虚拟机工具接口(Java Virtual Machine Tools Interface,JVMTI)及其前身Java虚拟机监视程序接口(Java Virtual Machine Profiling Interface,JVMPI)是外部工具与JVM通信并从JVM收集信息的标准化接口.字节码技术是指使用探测器处理字节码以获得工具所需的信息的技 术.
Optimizeit是Borland公司的产品,主要用于协助对软件系统进行代码优化和故障诊断,其中的Optimizeit Profiler主要用于内存泄漏的分析.Profiler的堆视图就是用来观察系统运行使用的内存大小和各个类的实例分配的个数的.
首先,Profiler会进行趋势分析,找出是哪个类的对象在泄漏.系统运行长时间后可以得到四个内 存快照.对这四个内存快照进行综合分析,如果每一次快照的内存使用都比上一次有增长,可以认定系统存在内存泄漏,找出在四个快照中实例个数都保持增长的 类,这些类可以初步被认定为存在泄漏.通过数据收集和初步分析,可以得出初步结论:系统是否存在内存泄漏和哪些对象存在泄漏(被泄漏).
接下来,看看有哪些其他的类与泄漏的类的对象相关联.前面已经谈到Java中的内存泄漏就是无用的对 象保持,简单地说就是因为编码的错误导致了一条本来不应该存在的引用链的存在(从而导致了被引用的对象无法释放),因此内存泄漏分析的任务就是找出这条多 余的引用链,并找到其形成的原因.查看对象分配到哪里是很有用的.同时只知道它们如何与其他对象相关联(即哪些对象引用了它们)是不够的,关于它们在何处 创建的信息也很有用.
最后,进一步研究单个对象,看看它们是如何互相关联的.借助于Profiler工具,应用程序中的代码可以在分 配时进行动态添加,以创建堆栈跟踪.也有可以对系统中所有对象分配进行动态的堆栈跟踪.这些堆栈跟踪可以在工具中进行累积和分析.对每个被泄漏的实例对 象,必然存在一条从某个牵引对象出发到达该对象的引用链.处于堆栈空间的牵引对象在被从栈中弹出后就失去其牵引的能力,变为非牵引对象.因此,在长时间的 运行后,被泄露的对象基本上都是被作为类的静态变量的牵引对象牵引.
总而言之, Java虽然有自动回收管理内存的功能,但内存泄漏也是不容忽视,它往往是破坏系统稳定性的重要因素.
代码题见下一篇。