java 复习题，

1.final关键字修饰类、方法、变量的意义

根据程序上下文环境，Java关键字final有“这是无法改变的”或者“终态的”含义，它可以修饰非抽象类、非抽象类成员方法和变量。你可能出于两种理解而需要阻止改变：设计或效率。
        final类不能被继承，没有子类，final类中的方法默认是final的。
        final方法不能被子类的方法覆盖，但可以被继承。
        final成员变量表示常量，只能被赋值一次，赋值后值不再改变。
        final不能用于修饰构造方法。
        注意：父类的private成员方法是不能被子类方法覆盖的，因此private类型的方法默认是final类型的。

2.String、String Builder、String Buffer

String是字符串常量。
StringBuffer是字符串变量 ，线程安全。
StringBuilder是字符串变量，线程不安全。
速度：String<StringBuffer<StringBuilder
为什么String速度最慢呢？
因为每次对 String 类型进行改变的时候，等同于生成了一个新的 String 对象，然后将指针指向新的 String 对象，这样，在不断生成新对象的时候旧对象就会在内存中堆积，会造成内存浪费，java的GC垃圾回收器就会对旧对象进行回收，严重拖慢了程序的速度。而StringBuilder就不同了，每次操作都是在同一个对象上，而且StringBuilder不用考虑线程同步（StringBuffer是线程安全的，要考虑线程同步），所以StringBuilder最快。

很多文章都是建议使用StringBuilder，因为StringBuilder是最快的，而且大部分程序都是单线程的。

3.大数据问题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

典型的Top K算法，还是在这篇文章里头有所阐述，详情请参见：十一、从头到尾彻底解析Hash表算法。
    
    文中，给出的最终算法是：
    第一步、先对这批海量数据预处理，在O（N）的时间内用Hash表完成统计（之前写成了排序，特此订正。July、2011.04.27）；
    第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。
        即，借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N为1000万，N’为300万）。ok，更多，详情，请参考原文。

    或者：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

4.两个单链表是否相交怎样知道一个链表里是否有环的存在，以及确定环的位置  如何确定两个链表是否有相同的部分

给出两个单向链表的头指针，判断这两个链表是否相交，如果相交给出相交的第一个结点

方法一：

直接判断第一个链表的每个结点是否在第二个链表中，时间复杂度为O(len1*len2)，耗时很大

方法二：

如 果 两个链表相交，则两个链表就会有共同的结点；而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点，就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序，建立hash表，然后针对第二个链表的每个节点的地址查询hash表，如果它在hash表中出现，则说明两个链表有共 同的结点。这个方法的时间复杂度为：O(max(len1+len2)；但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度，增加 了存储空间。

方法三：

两个没有环的链表相交于一节点，则在这个节点之后的所有结点都是两个链表所共有的。如果它们相交，则最后一个结点一定是共有的，则只需要判断最后一个结点是否相同即可。时间复杂度为O(len1+len2)。对于相交的第一个结点，则可求出两个链表的长度，然后用长的减去短的得到一个差值 K，然后让长的链表先遍历K个结点，然后两个链表再开始比较。

更多参考：http://blog.163.com/song_0803/blog/static/4609759720120910373784/

5.一个有序数组，有一个子项出现的次数在一半以上，如何找出该子项（中间值）

找出有序元素数组中指定元素出现的次数
    遍历数组的方法是最简单的，时间复杂度为O（n）；
    采用二分搜索方法，找到元素，然后左右遍历，时间复杂度为O(logn)；
    既然是有序数组，当然要利用其有序性，采用二分搜索分别找到该元素的开头和结尾，然后相减即可，时间复杂度为O(logn)。
     代码如下，思路比较简单，完全写对我还是花了一定时间的，主要是因为对于low、high和middle之间的赋值时忽略了可能出现死循环的现象。

更多参考：http://blog.sina.com.cn/s/blog_6ddc07d00100uze9.html

无序数组呢？（HashTable、ArrayList不是最优解）

6.用过的java开源框架，Spring的AOP

7.算法的时间复杂度（选择、堆、快速排序）

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
交换	O(n2)	O(n2)	不稳定	O(1)	n小时较好
选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn)	O(ns) 1<s<2	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好

8.

接口和抽象类的区别是什么？

Java提供和支持创建抽象类和接口。它们的实现有共同点，不同点在于：

• 接口中所有的方法隐含的都是抽象的。而抽象类则可以同时包含抽象和非抽象的方法。
• 类可以实现很多个接口，但是只能继承一个抽象类
• 类如果要实现一个接口，它必须要实现接口声明的所有方法。但是，类可以不实现抽象类声明的所有方法，当然，在这种情况下，类也必须得声明成是抽象的。
• 抽象类可以在不提供接口方法实现的情况下实现接口。
• Java接口中声明的变量默认都是final的。抽象类可以包含非final的变量。
• Java接口中的成员函数默认是public的。抽象类的成员函数可以是private，protected或者是public。
• 接口是绝对抽象的，不可以被实例化。抽象类也不可以被实例化，但是，如果它包含main方法的话是可以被调用的。

Difference Between Interface and Abstract Class

1. Main difference is methods of a Java interface are implicitly abstract and cannot have implementations. A Java abstract class can have instance methods that implements a default behavior.
2. Variables declared in a Java interface is by default final. An  abstract class may contain non-final variables.
3. Members of a Java interface are public by default. A Java abstract class can have the usual flavors of class members like private, protected, etc..
4. Java interface should be implemented using keyword “implements”; A Java abstract class should be extended using keyword “extends”.
5. An interface can extend another Java interface only, an abstract class can extend another Java class and implement multiple Java interfaces.
6. A Java class can implement multiple interfaces but it can extend only one abstract class.
7. Interface is absolutely abstract and cannot be instantiated; A Java abstract class also cannot be instantiated, but can be invoked if a main() exists.
8. In comparison with java abstract classes, java interfaces are slow as it requires extra indirection.

9.

表1-1  TCP/IP四层模型和OSI七层模型对应表

OSI七层网络模型	Linux TCP/IP四层概念模型	对应网络协议
应用层（Application）	应用层	TFTP, FTP, NFS, WAIS
表示层（Presentation）		Telnet, Rlogin, SNMP, Gopher
会话层（Session）		SMTP, DNS
传输层（Transport）	传输层	TCP, UDP
网络层（Network）	网际层	IP, ICMP, ARP, RARP, AKP, UUCP
数据链路层（Data Link）	网络接口	FDDI, Ethernet, Arpanet, PDN, SLIP, PPP
物理层（Physical）		IEEE 802.1A, IEEE 802.2到IEEE 802.11

end