2016-01-15 金蝶随手记 - 面试笔记
一、Java 基础
1、& 与 && 的区别？
& 与 && 都可以表示逻辑与运算符，他们的区别是当第一个运算符返回的是false时，&会继续第二个表达式的运算再返回结果，而&&则直接返回false。此外 & 还可以当作位运算符，进行位运算。在C语言中，&运算符还可以进行赋值操作。
2、Java 中基本的数据类型有哪些？
Java 一共有 8 种基本数据类型，分别是：
byte short int long 字节型 短整型 整型 长整型
float double 浮点型 双精度型
boolean char 布尔型 字符型
3、重载（Overload）和重写（Override）的区别。重载的方法能否根据返回类型进行区别？
重载一般指的是具有同样方法名，但是方法携带的参数个数、顺序、类型不同，重载一般出现在构造方法比较多。而重写指的是子类重写父级的方法，重写要求方法名、方法参数个数、方法参数类型、方法参数顺序都完全一致，重写一般出现在父类子类继承这种情况。重载的方法是不可以根据返回类型进行区分的。
4、抽象类（abstract class）和接口（interface）有什么异同？
相同点：抽象类和接口都可以定义抽象方法。抽象类和接口都不能实例化
不同点：第一，接口中只可以定义抽象方法，而不能定义非抽象方法。而抽象类中不但可以定义抽象方法，也可以定义非抽象方法。第二，抽象类中可以定义构造方法、成员变量、静态变量，而接口中不能定义构造方法、成员变量，接口只能定义静态的不能被修改的变量（也即是 static final 变量）。第三，使用的时候抽象类更多的出现在父子继承关系中，而接口更多是出现在接口调用中。 总的来说，接口可以说是一种特殊的抽象类。
5、如何实现对象克隆？
克隆需要被克隆的对象实现 Clonable 接口，并重载 clone() 方法。克隆又分为浅克隆（影子克隆）和深度克隆。浅克隆只克隆基本数据类型，对象中的引用类型引用的还是原来的对象。而深度克隆无论基本数据类型还是引用类型都是新的对象，与原来的对象没有任何关联。
6、一个".java"源文件中是否可以包含多个类（不是内部类）？有什么限制？
可以有多个类。但限制是只能有一个类是 public 的。
7、Java 中的 final 关键字有哪些用法？
final 关键字可以修饰 类、方法、属性。
当用final修饰一个类时，表明这个类不能被继承。
当用final修饰一个方法时，表明这个方法不能被重写。
当用final修饰一个属性时，表明这个属性的内容不能被修改。
8、列出一些你常见的运行时异常？
Java 中的异常分为 Error 和 Exception 两大类，其中 Exception 又分为 IOException 和 RuntimeException 两大类。其中常见的RuntimeException 有：
ArithmeticException 除数为0异常
ClassNotFoundException 无法找到类异常
NullPointerException 空指针异常
ArrayIndexOutOfBoundsException 数组越界异常
IllegalArgumentException 非法参数异常
UnknowTypeException 未知类型异常
ClassCastException 强制类型转换时发生
9、Collection 和 Collections 的区别？
Collection 接口 是集合 List/Set/Queue 接口的父级接口，而 Collections 是一个工具类，可以对集合进行排序等操作。
10、Thread 类的 sleep() 方法和对象的 wait() 方法都可以让线程暂停执行，它们有什么区别？
sleep() 方法就是正在执行的线程主动让出 CPU，CPU去执行其他线程，但是 sleep() 方法并不会释放同步锁。而 wait() 方法指的是一个已经获得同步锁的线程将其同步锁释放，给其他线程使用，当其他线程使用完毕后，通过 notify() 方法通知线程继续执行。
11、当一个线程进入一个对象的 synchronized 方法 A 之后，其它线程是否可进入此对象的 synchronized 方法 B？
要分情况说明。如果其他方法前加了 synchronized 关键字，并且内部没有调用 wait() 方法，则不能进入方法 B。因为如果都加了 synchronized 关键字，那么它们或的的锁都是该对象，也就是 this。当这个this对象被调用方法A的线程获取后，其他线程是无法获取这个线程的。但是如果调用方法A的线程在方法A中调用 wait() 方法释放了同步锁，那么其他线程就可以进入该对象的 synchronized 方法 B了。这里要注意几种不同情况下，它们获取的锁定对象是什么。
//锁定的对象是 Hello.classpublic static synchronized void syn1(){}//锁定的对象是 Hello.classpublic void syn2() { synchronized (Hello.class) { }}//锁定的对象是 this（Hello的实例对象）public synchronized void syn3(){}//锁定的对象是 this（Hello的实例对象）public void syn4() { synchronized (this) { }} 当然了，你也可以自己声明一个对象作为锁：
//自己声明一个对象作为锁Object lock = new Object();public void syn5() { synchronized (lock) { }} 12、Java 的 HashMap 是如何工作的？
在说 HashMap 的工作原理之前，我们要了解 HashMap 的存储结构：HashMap 使用一个数组来存储所有的数据，而数组中的每一个元素都是一个链表。当我们往 Map 中插入一个元素时，Map 会调用对象的 hashCode() 方法计算出其哈希码，根据这个哈希码来确定这个元素应该放在数组的哪一个位置上。如果两个 key 计算出同一个哈希码，也即其要存储的位置上已经有元素存在了，那么它就以链表元素的形式放在原来元素的后面。
（画出结构示意图）
13、用最有效的方法计算 2 乘以 8？
使用位运算：2 << 3 （8 是 2 的 3 次方。左移一次乘以 2，要乘以8，就左移 3次）
14、如何避免死锁？
首先我们理解死锁产生的 4 个必要条件：
互斥：指的是一个资源同时只能被一个线程使用
持有：指的是当一个线程因为申请资源而阻塞时，它不但不需要释放原有的资源，还可以继续持有这些资源并申请新的资源
不可剥夺：指的是一个线程的资源只能由线程自己释放，不能被外接强制剥夺
环形等待：指的是若干个线程以不同次序获取互斥资源，从而形成环形等待的局面
上面 4 个条件，只要有一个不成立，那么死锁就不会发生。因此我们一般可以有以下一些方法避免死锁：
- 破坏持有条件、破坏不可剥夺条件。当一个线程申请的资源在一定时间内还无法得到满足时，就应该自动回滚该事务，从而避免死锁。
- 破坏环形等待。这种方式需要我们请求资源的顺序必须一致，而且在一个系统中只允许出现一种资源请求顺序。这种方式实现起来比较简单，但是需要团队成员之间统一配合。
16、数据库的 ACID 特性是什么，数据库事务隔离级别都有哪些？
Atomicity：原子性。事务中的所有操作要么全部完成，要么全部不完成。
Consistency：一致性。无论同一时间内并发事务有多少，同样的输入在同样的环境下都会有同样的输出。例如：有3个银行账号，它们一共有 500 元的总额。它们在一定时间内相互转账，那么无论它们怎么进行并发转账，它们的账户总额加起来也应该是 500 元。这就是一致性。
Isolation：独立性。每个事务都应该是独立运行，互不影响的。
Durability：持久性。事务完成后，其对数据库做的操作应该持久化到数据库中，不会被回滚。
数据库的隔离级别有四种，分别是：
READ UNCOMMITTED（读取未提交的内容）
在 READ UNCOMMITTED 隔离级，事务可能会读取到未提交事务的执行结果，造成“脏读”。线程AB读取账户的余额，账户余额是400元。首先A线程存进了100元，但未提交事务。此时B线程读取账户余额，读取到的数据是 500元。此时如果A线程回滚，那么B线程读取到的数据就是错误的。这就是“脏读”。
READ COMMITTED（读取提交内容）
在 READ COMMITTED 隔离级，它只能读取到已提交事务的执行结果，这是大多数数据库系统采用的隔离级别，但是这种情况会造成“不可重复读”。线程AB读取账户的余额，账户余额是400元。线程B读取账户余额，读取到的数据是 400 元。此时线程A存进 100 元并提交事务，此时账户余额 500 元。之后线程 B 再次读取账户余额，读取到的数据是 500 元。前后两次读取到的数据不一样，这就是“不可重复度”。
REPEATABLE READ（可重读。MySQL默认隔离级别）
REPEATABLE READ 隔离级解决了 READ COMMITTED 的“不可重复读”问题。在 REPEATABLE READ 隔离级别下，线程AB读取账户的余额，账户余额是400元。线程B读取账户余额，读取到的数据是 400 元。此时只要线程 B 的事务还未完成，其他所有线程对账户余额的操作就会失败（确切地说是所有线程B事务引用到的数据行都不可以被修改或删除）。只有等到线程B事务提交或回滚之后，其他线程才可以进行更新或删除操作。这样就确保了线程B两次读取的数据都是相同的。但是这种方式会导致幻读。幻读是指当事务不是独立执行时发生的一种现象。例如第一个事务对一个表中的数据进行了修改，比如这种修改涉及到表中的“全部数据行”。同时，第二个事务也修改这个表中的数据，这种修改是向表中插入“一行新数据”。那么，以后就会发生操作第一个事务的用户发现表中还有没有修改的数据行，就好象发生了幻觉一样。
SERIALIZABLE（可串行化）
SERIALIZABLE 是最高级别的隔离级别，它通过在每个读的数据行上加锁使得脏读、不可重复读、幻读都不存在。但这个级别下，可能会导致大量的超时和锁竞争。一般很少选择这个级别，如果用户的应用为了数据稳定性，需要强制减少并发的话，可以选择这种方式。
二、数据库
1、写出查询表 `table1`，按每页 5 条数据的第二个分页的 sql
select * from table1 limit 5,5;
这里要注意 limit 后第一个参数表示下标，第二个参数表示获取的条数。不要写成 limit 5, 10 了！
2、用一个 SQL 语句查询出每门课都大于 80 分的学生姓名
name course scorer
| 张三 | 语文 | 81 |
| 张三 | 数学 | 75 |
| 李四 | 语文 | 76 |
| 李四 | 数学 | 90 |
| 王五 | 语文 | 81 |
| 王五 | 数学 | 100 |
| 王五 | 英语 | 90 |
用 not in 实现：
select distinct name from table2
where name not in (select name from table2 where score <= 80);用 not exists 实现：
select distinct name from table2 t1
where not exists (select * from table2 t2 where t1.name = t2.name and t2.score <= 80);3、删除除了 id 不同，其他都相同的学生信息（除 ID 外其它都一样）
基本思路是用 EXISTS 去比较所有列。参考SQL如下：
-- 简单版delete from table3where id in ( select id from table3 t1where exists ( select * from table3 t2 where t1.id != t2.id and t1.stuNo = t2.stuNo and t1.name = t2.name and t1.courseId = t2.courseId and t1.courseName = t2.courseName and t1.score = t2.score));
上面的 SQL 能够很好地描述出此题的思路，但是因为 MySQL 的一个限制，使得执行上面的 SQL 时会出现 1093 错误：You can't specify target table 't1' for update in FROM clause。意思是说，你不能从 table 表查询出数据，然后又更新它。但是，如果我们通过把从 table 表查询出来的数据作为一个临时表，然后再删除它是可以的，即：我们用临时表的方式来绕过这个限制。修改后的 SQL 如下：
-- 实践版delete from table3where id in ( select id from ( select id from table3 t1 where exists ( select * from table3 t2 where t1.id != t2.id and t1.stuNo = t2.stuNo and t1.name = t2.name and t1.courseId = t2.courseId and t1.courseName = t2.courseName and t1.score = t2.score ) ) tem);
4、如果要生成下列结果，该如何写 SQL 语句？
| 2005-05-09 | 浏览 |
| 2005-05-09 | 浏览 |
| 2005-05-09 | 点击 |
| 2005-05-09 | 点击 |
| 2005-05-10 | 浏览 |
| 2005-05-10 | 点击 |
| 2005-05-10 | 点击 |
这道题的关键是要分列处理，先查出时间、浏览数这个结果，再查出时间、点击数这个结果，再用左连接将其连接起来。
select t1.eventDate, t1.count, t2.count from( select eventDate, count(eventDate) count from table4 where eventType = '浏览' group by eventDate) t1 left outer join( select eventDate, count(eventDate) count from table4 where eventType = '点击' group by eventDate) t2 on t1.eventDate = t2.eventDate;
我把所有表的创建和数据都放这里了，需要的话可以下载。
链接： 密码：wx9g
三、算法
1、请写出一个单例模式（写出代码）？
2、找出链表中倒数第 K 个元素（写出代码）？
一共有 3 种方式。
第一种。最简单的方式，遍历一下链接所有的个数，之后从头开始遍历 n - k + 1次得到的元素就是倒数第 K 个元素。这种方式需要对链表遍历两次，遍历元素个数为 n + n - k + 1 = 2n + 1 - k 个。
第二种。使用两个指针，让它们之间保持的距离为 k - 1，同时对它们进行遍历，当后面的指针到达链表的最后一个元素（即倒数第一个元素时），第二个指针刚好停留在倒数第K个元素上。此种方式在时间上只对链表遍历了一次，但因为使用了两个指针，所以实际遍历的元素个数仍然是：n + n - k + 1 = 2n + 1 - k 个。但比起第一种时间更快。
第三种。使用一个指针，每次遍历k个元素，遍历m次（m=n/k），最后一次遍历的个数为i个（i=n%k），我们只需记录最后一次遍历k个元素的起始位置，然后再遍历i个元素，此时的位置即为倒数第k个元素。此时，对链表遍历的元素个数为n+i（i为n除以k的余数）。
实现代码如下：
package com.mszz.promotion.test;/** * Created by Administrator on 2016/2/21. */public class MyLinkedList { Node head; Node current; int size; public MyLinkedList(){ head = null; current = head; } public Node add(Node node) { if (size == 0) { head = node; current = head; }else{ current.setNext(node); current = node; } size++; return current; } //方式2 public Node getLastObj2(int index) { Node node1 = head; Node node2 = head; //相差index个 for (int i = 0; i < index - 1; i++) { if(node2 != null){ node2 = node2.getNext(); } } //遍历 while (node2.getNext() != null) { node1 = node1.getNext(); node2 = node2.getNext(); } return node1; } //方式3 public Node getLastObj3(int index) { Node node = head; //最后一个位置 Node lastIndexNode = node; int yushu = 0; while (node.getNext() != null) { for (int i = 0; i < index; i++) { if(node.getNext() != null){ node = node.getNext();a }else{ yushu = i; break; } } if (node.getNext() != null) { lastIndexNode = node; } } for (int i = 0; i < yushu + 1; i++) { lastIndexNode = lastIndexNode.getNext(); } return lastIndexNode; } public static void main(String args[]) { MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.add(new Node("1")); myLinkedList.add(new Node("2")); myLinkedList.add(new Node("3")); myLinkedList.add(new Node("4")); myLinkedList.add(new Node("5")); //获取倒数第二个 Node node = myLinkedList.getLastObj3(2); System.out.println("result:" + node.getData()); }} 3、不用 Java API 实现字符串逆序发，输入"abcde"，输出"edcba"（写出代码）？
public class StringTest { public static void main(String args[]) { String str = "abcde"; System.out.println(reverse(str)); } public static String reverse(String str) { char[] chars = str.toCharArray(); int length = str.length(); str = ""; for (int i = length - 1; i >= 0; i--) { str += chars[i]; } return str; }} 4、给定 100 亿个网址，如何检测重复？重复是指URL完全相同（简述思路）。
5、打印出 10 亿个整数中的最大 10 个整数（简述思路）。
最容易想到的方法是将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间，对于一些可用内存小于400M的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求（我机器内存都是8GB），该方法也并不高效，因为题目的目的是寻找出最大的10000个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。
第二种方法为局部淘汰法，该方法与排序方法类似，用一个容器保存前10000个数，然后将剩余的所有数字——与容器内的最小数字相比，如果所有后续的元素都比容器内的10000个数还小，那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。
第三种方法是分治法，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*4=4MB，一共需要101次这样的比较。
第四种方法是Hash法。如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。
参考：