面试小结之综合篇

作者: ginobefun | 来源:发表于2017-06-14 16:28 被阅读329次

最近面试一些公司，被问到的关于编程基础、数据库、Redis和系统设计相关的问题，以及自己总结的回答。

介绍一下你熟悉的几种排序算法以及它们的时间复杂度。

冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换。
算法的平均时间复杂度为O(n^2)。
但是若在某趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，即为正序。则冒泡排序过程可在此趟扫描后就终止，基于这种考虑，提出了第一种改进的算法。

    public static void bubbleSort(int[] numbers) {
        int size = numbers.length;
        boolean isSorted = false;
        for (int i = 0; i < size - 1 && !isSorted; i++) {
            isSorted = true;
            for (int j = 0; j < size - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    swap(numbers, j, j + 1);
                    isSorted = false;
                }
            }
        }
    }

快速排序

快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n^2）。
快速排序时基于分治模式处理的，在数据集之中，选择一个元素作为”基准”（pivot），所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
快排的局限性：快排是一个效率很高的排序算法，但是对于长度很小的序列，快排效率低；pivot选择不当，将导致树的不平衡，这样导致快排的时间复杂度为o(n^2)；当数组中有大量重复的元素，快排效率将非常之低；改进方法可以参考java.util.DualPivotQuicksort：小数组使用插入排序、双枢轴（快速三向切分）、划分策略优化（五取样划分）。

    public static void quick(int[] numbers) {
        if (numbers.length > 0) {
            quickSort(numbers, 0, numbers.length - 1);
        }
    }

    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            int middle = getMiddle(numbers, low, high); //将numbers数组进行一分为二
            quickSort(numbers, low, middle - 1);   //对低字段表进行递归排序
            quickSort(numbers, middle + 1, high); //对高字段表进行递归排序
        }
    }

    public static int getMiddle(int[] numbers, int low, int high) {
        int temp = numbers[low]; //数组的第一个作为中轴
        while (low < high) {
            while (low < high && numbers[high] > temp) {
                high--;
            }
            numbers[low] = numbers[high];//比中轴小的记录移到低端
            while (low < high && numbers[low] < temp) {
                low++;
            }
            numbers[high] = numbers[low]; //比中轴大的记录移到高端
        }
        numbers[low] = temp; //中轴记录到尾
        return low; // 返回中轴的位置
    }

堆排序

堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。
二叉堆一般分为两种：最大堆和最小堆。最大堆：最大堆中的最大元素值出现在根结点（堆顶）；堆中每个父节点的元素值都大于等于其孩子结点（如果存在）；
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
Parent(i) = floor((i-1)/2)，i 的父节点下标
Left(i) = 2i + 1，i 的左子节点下标
Right(i) = 2(i + 1)，i 的右子节点下标

堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。

谈谈对Spring IoC的理解。

IoC不是什么技术，而是一种设计思想，它意味着将你设计好的对象交给容器控制，而不是传统的在你的对象内部直接控制。
理解好Ioc的关键是要明确：

谁控制谁 -- IoC容器控制了对象
控制什么 -- 主要控制了外部资源获取（不只是对象，包括比如文件等）
为何是反转 -- 由容器帮我们查找及注入依赖对象，对象只是被动的接受依赖对象
哪些方面反转了 -- 依赖对象的获取被反转了

传统做法

IoC做法

IoC能做什么：把创建和查找依赖对象的控制权交给了容器，由容器进行注入组合对象，所以对象与对象之间是松散耦合，这样也方便测试，利于功能复用，更重要的是使得程序的整个体系结构变得非常灵活；IoC很好的体现了面向对象设计法则之一 -- 好莱坞法则；
IoC和DI是同一个概念的不同角度描述，“依赖注入”明确描述了“被注入对象依赖IoC容器配置依赖对象”。
在Spring里，BeanFactory提供了IoC容器最基本功能，而 ApplicationContext 则增加了更多支持企业级功能支持。ApplicationContext完全继承BeanFactory，因而BeanFactory所具有的语义也适用于ApplicationContext。ApplicationContext实现包括FileSystemXmlApplicationContext、ClassPathXmlApplicationContext、WebXmlApplicationContext；
Spring框架中bean的生命周期：

Spring容器从XML文件中读取bean的定义，并实例化bean。
Spring根据bean的定义填充所有的属性。
如果bean实现了BeanNameAware接口，Spring传递bean的ID到setBeanName方法。
如果Bean实现了BeanFactoryAware接口，Spring传递beanfactory给setBeanFactory方法。
如果有任何与bean相关联的BeanPostProcessors，Spring会在postProcesserBeforeInitialization()方法内调用它们。
如果bean实现IntializingBean了，调用它的afterPropertySet方法，如果bean声明了初始化方法，调用此初始化方法。
如果有BeanPostProcessors和bean关联，这些bean的postProcessAfterInitialization() 方法将被调用。
如果bean实现了DisposableBean，它将调用destroy()方法。

谈谈对Spring AOP的理解。

方面（Aspect）：一个关注点的模块化，这个关注点实现可能另外横切多个对象。事务管理是J2EE应用中一个很好的横切关注点例子。方面用Spring的Advisor或拦截器实现。
连接点（Joinpoint）: 程序执行过程中明确的点，如方法的调用或特定的异常被抛出；
通知（Advice）: 在特定的连接点，AOP框架执行的动作。许多AOP框架包括Spring都是以拦截器做通知模型，维护一个“围绕”连接点的拦截器链。Spring中定义了四个advice: BeforeAdvice, AfterAdvice, ThrowAdvice和DynamicIntroductionAdvice；
切入点（Pointcut）: 指定一个通知将被引发的一系列连接点的集合。AOP框架必须允许开发者指定切入点：例如，使用正则表达式。 Spring定义了Pointcut接口，用来组合MethodMatcher和ClassFilter，可以通过名字很清楚的理解，MethodMatcher是用来检查目标类的方法是否可以被应用此通知，而ClassFilter是用来检查Pointcut是否应该应用到目标类上；
切点标志符(designator)：execution、within、this 与 target、bean、args、@annotation；
JDK动态代理和CGLib代理。

// 定义接口
public interface ForumService {
    public void removeTopic(int topic);
    public void removeForum(int forumId);
    
}

// 接口实现类
public class ForumServiceImpl implements ForumService{
    public void removeTopic(int topic){
        System.out.println("模拟删除主题"+topic);
        try{
            Thread.currentThread().sleep(20);
        }catch(Exception e){
            throw new RuntimeException(e);
        }
    
    }
    public void removeForum(int forumId){
        System.out.println("模拟删除论坛"+forumId);
        try{
            Thread.currentThread().sleep(20);
        }catch(Exception e){
            throw new RuntimeException(e);
        }
    }
}

// 工具类用于打印接口调用信息
public class PerformanceMonitor {
    private static ThreadLocal<MethodPerformance> performanceRecord=new ThreadLocal<MethodPerformance>();
    
    public static void begin(String method){
        System.out.println("begin monitor...");
        MethodPerformance mp = new MethodPerformance(method);
        performanceRecord.set(mp);
    }
    public static void end(){
        System.out.println("end monitor...");
        MethodPerformance mp = performanceRecord.get();
        mp.printPerformance();
    }
}

public class MethodPerformance {
    private long begin;
    private long end;
    private String serviceMethod;
    public MethodPerformance(String serviceMethod){
        this.serviceMethod = serviceMethod;
        this.begin = System.currentTimeMillis();
    }
    
    public void printPerformance(){
        end = System.currentTimeMillis();
        long elapse = end - begin;
        System.out.println(serviceMethod + "花费" + elapse + "毫秒");
    }
} 

// JDK动态代理需要实现InvocationHandler
public class PerformanceHandler implements InvocationHandler {
    private Object target;

    public PerformanceHandler(Object object) {
        this.target = object;
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args)
            throws Throwable {
        PerformanceMonitor.begin(target.getClass().getName() + "." + method.getName());
        Object obj = method.invoke(target, args);
        PerformanceMonitor.end();
        return obj;
    }
}

// JDK动态代理使用
ForumServiceImpl target = new ForumServiceImpl();
PerformanceHandler handler = new PerformanceHandler(target);
ForumService proxy = (ForumService)Proxy.newProxyInstance(target.getClass().getClassLoader(),
    target.getClass().getInterfaces(), handler);
proxy.removeForum(23);
proxy.removeTopic(678);
        
// CGlib动态代理需要实现MethodInterceptor
public class CglibProxy implements MethodInterceptor{
    private Enhancer enhancer = new Enhancer();
    public Object getProxy(Class clazz){
        enhancer.setSuperclass(clazz);
        enhancer.setCallback(this);
        return enhancer.create();
    }
    
    @Override
    public Object intercept(Object proxy, Method method, Object[] args,
            MethodProxy methodProxy) throws Throwable {
        PerformanceMonitor.begin(proxy.getClass().getName() + "." + method.getName());
        Object obj = methodProxy.invoke(proxy, args);
        PerformanceMonitor.end();
        return obj;
    }
}

// CGlib动态代理使用
CglibProxy proxy2 = new CglibProxy();
ForumServiceImpl forumServiceImpl = (ForumServiceImpl)proxy2.getProxy(ForumServiceImpl.class);
forumServiceImpl.removeForum(456);
forumServiceImpl.removeTopic(987);

两种动态代理的比较：CGLib所创建的动态代理对象的性能比JDK所创建的代理对象性能高不少，大概10倍，但CGLib在创建代理对象时所花费的时间却比JDK动态代理多大概8倍，所以对于singleton的代理对象或者具有实例池的代理，因为无需频繁的创建新的实例，所以比较适合CGLib动态代理技术，反之则适用于JDK动态代理技术。另外，由于CGLib采用动态创建子类的方式生成代理对象，所以不能对目标类中的final，private等方法进行处理。所以，大家需要根据实际的情况选择使用什么样的代理了。同样的，Spring的AOP编程中相关的ProxyFactory代理工厂内部就是使用JDK动态代理或CGLib动态代理的，通过动态代理，将增强（advice)应用到目标类中。

Spring MVC的核心流程是什么样的？

核心流程

具体步骤：

首先用户发送请求——>DispatcherServlet，前端控制器收到请求后自己不进行处理，而是委托给其他的解析器进行处理，作为统一访问点，进行全局的流程控制；
DispatcherServlet——>HandlerMapping，HandlerMapping 将会把请求映射为 HandlerExecutionChain 对象（包含一个 Handler 处理器（页面控制器）对象、多个 HandlerInterceptor 拦截器）对象，通过这种策略模式，很容易添加新的映射策略；
DispatcherServlet——>HandlerAdapter，HandlerAdapter 将会把处理器包装为适配器，从而支持多种类型的处理器，即适配器设计模式的应用，从而很容易支持很多类型的处理器；
HandlerAdapter——>处理器功能处理方法的调用，HandlerAdapter 将会根据适配的结果调用真正的处理器的功能处理方法，完成功能处理；并返回一个 ModelAndView 对象（包含模型数据、逻辑视图名）；
ModelAndView 的逻辑视图名——> ViewResolver， ViewResolver 将把逻辑视图名解析为具体的 View，通过这种策略模式，很容易更换其他视图技术；
View——>渲染，View 会根据传进来的 Model 模型数据进行渲染，此处的 Model 实际是一个 Map 数据结构，因此很容易支持其他视图技术；
返回控制权给 DispatcherServlet，由 DispatcherServlet 返回响应给用户，到此一个流程结束。

Redis和Memcached的异同。

Memcached

可以利用多核优势，单实例吞吐量极高，可以达到几十万QPS；
只支持简单的key/value数据结构，不像Redis可以支持丰富的数据类型。
无法进行持久化，数据不能备份，只能用于缓存使用，且重启后数据全部丢失。
无法进行数据同步，不能将MC中的数据迁移到其他MC实例中。
Memcached内存分配采用Slab Allocation机制管理内存，value大小分布差异较大时会造成内存利用率降低，并引发低利用率时依然出现踢出等问题。需要用户注重value设计。

Redis

支持多种数据结构，如string、 list、hash、set、zset等；
支持持久化操作，可以进行aof及rdb数据持久化到磁盘，从而进行数据备份或数据恢复等操作，较好的防止数据丢失的手段；
支持通过Replication进行数据复制，通过master-slave机制，可以实时进行数据的同步复制来实现HA；
单线程请求，所有命令串行执行，并发情况下不需要考虑数据一致性问题，但性能受限于CPU性能，故单实例CPU最高才可能达到5-6wQPS每秒；
支持pub/sub消息订阅机制，可以用来进行消息订阅与通知；
Redis在string类型上会消耗较多内存，可以使用hash表压缩存储以降低内存耗用。

Redis作为分布式缓存可能会存在哪些问题，怎么解决？

缓存穿透预防及优化：缓存穿透是指查询一个根本不存在的数据，缓存层和存储层都不会命中；缓存穿透将导致不存在的数据每次请求都要到存储层去查询，失去了缓存保护后端存储的意义；解决方法：缓存空对象和布隆过滤器拦截；
缓存雪崩问题优化：由于缓存层承载着大量请求，有效的保护了存储层，但是如果缓存层由于某些原因整体不能提供服务，于是所有的请求都会达到存储层，存储层的调用量会暴增，造成存储层也会挂掉的情况；预防和解决缓存雪崩问题，可以从以下三个方面进行着手：保证缓存层服务高可用性、依赖隔离组件为后端限流并降级、提前演练。
缓存热点key重建优化：开发人员使用缓存和过期时间的策略既可以加速数据读写，又保证数据的定期更新，这种模式基本能够满足绝大部分需求。但如果热点Key和重建缓存耗时两个问题同时出现，可能就会对应用造成致命的危害；解决方法：互斥锁（只允许一个线程重建缓存）、永远不过期（唯一不足的就是重构缓存期间会出现数据不一致的情况）。

谈谈对Mysql索引的认识。

主键查询走索引，我们一般使用的索引都是Btree索引；
MyISAM和InnoDB索引结构有很大差异，这里以InnoDB为例，InnoDB的叶节点存储的是数据的行，而除了主键之外的列索引存储的是主键key，也就是说在查询的时候需要二次查询，先通过列索引找到主键，再通过主键索引找到row。

MySQL索引

针对我们经常查询的多列场景，我们可以建组合索引，组合索引在可以尽可能多的运用列的查询规则。说到组合索引那么必须说一下最左前缀原则：指的的是在sql where子句中一些条件或表达式中出现的列的顺序要保持和多索引的一致或以多列索引顺序出现，只要出现非顺序出现、断层都无法利用到多列索引。
索引的区分度，主要是衡量索引值不相同的程度，区分度越大，越有利于索引的查询。
组合索引的顺序和区分度：对于多个列构成的组合索引，在查询过滤的时候也是和列的位置有关的，这也是最左前缀规则说的事情，也就是说如果在第一次能过滤掉大量的数据，那么后续的索引匹配就能减少很多消耗。所以在选择索引顺序的时候最好是要考虑到区分度的问题，将区分度比较高的列放在前面。
只有当索引的列顺序和Order By子句的顺序完全一致时，并且所有的列的排序方向都一样时，才能使用索引对子句进行排序。
应该注意的几点：在使用索引查询的时候，需要保证索引类型和查询的数据类型一致，经常混用的是用int型查询varchar类型的数据或反过来，这样会导致索引失效；range查询要尽量放在后面，因为在range后面的查询不会走索引，这一点在设计索引时要注意；Like查询不能前缀模糊匹配，也就是说不可以like ‘%123’，因为like的后缀模糊 like ‘123%’可以转化为range查询，但是前缀模糊不可以；索引不是越多越好，索引十分大时不仅会影响查询效率，同时会为数据的插入造成很大的负担；对于重复索引需要删除，规划好索引是高效率的前提。
主键索引和唯一索引的区别：主键一定会创建一个唯一索引，但是有唯一索引的列不一定是主键；主键不允许为空值，唯一索引列允许空值；一个表只能有一个主键，但是可以有多个唯一索引主键可以被其他表引用为外键，唯一索引列不可以；主键是一种约束，而唯一索引是一种索引，是表的冗余数据结构，两者有本质的差别。

MySql的事务隔离级别有哪几种？

隔离级别用于表述并发事务之间的相互干扰程度，其基于锁机制进行并发控制。
可序列化（Serializable）：事务一个接一个的执行，完全相互独立；实现可序列化要求在选定对象上的读锁和写锁保持直到事务结束后才能释放；在SELECT的查询中使用一个WHERE子句来描述一个范围时应该获得一个“范围锁”。
可重复度（Repeatable Read）：事务A读取数据之后，对涉及的数据加锁，不允许其他事务进行修改，由于其他事务会插入新的数据，因此会产生幻读；对选定对象的读锁和写锁一直保持到事务结束，但不要求“范围锁”，因此可能会发生幻读；可重复读是MySQL的默认事务隔离级别。
读取已提交（Read Committed）：只能看到其他事务已经提交的数据，避免了脏读，但存在不可重复读、幻读；DBMS需要对选定对象的写锁(write locks)一直保持到事务结束，但是读锁(read locks)在SELECT操作完成后马上释放，且不要求“范围锁”。
读取未提交（Read Uncommitted）：可以看到其他事务没有提交的数据，出现脏读、不可重复读、幻读；

[PS补充]
不可重复读的重点是修改：同样的条件，读取过的数据，再次读取出来发现值不一样了。
幻读的重点在于新增或者删除：同样的条件，第1次和第2次读出来的记录数不一样。

MySql的MVVC有什么作用？

多版本并发控制（MVCC），来实现MySQL上的多事务并发访问时，隔离级别控制；
数据版本：并发事务执行时，同一行数据有多个版本；
事务版本：每个事务都有一个事务版本；
版本有序：版本是通过时间来标识的；
通过MVCC实现的效果是同一时刻、同一张表、多个并发事务，看到的数据是不同的。
MVCC本质使用了copy-on-write，为每个数据保留多份snapshot，不同snapshot之间，使用指针连接成链表；update操作，能看到的snapshot是受限的，是链表上小于等于当前事务版本的最大版本（读取已提交：离当前事务最近的已提交版本）；

如何设计高性能、高并发、高可用的系统。

系统架构三个利器：RPC服务组件、消息中间件（交互异步化、流量削峰）、配置管理（灰度发布、降级）；
无状态：接口层最重要的就是无状态，将有状态的数据剥离到数据库或缓存中；
如何改善延时：找关键路径（“28原则”）、空间换时间，如各级缓存；时间换空间，如传输压缩，解决网络传输的瓶颈；多核并行，减少锁竞争；更适合的算法和数据结构；通过性能测试和监控找出瓶颈；减少系统调用和上下文切换；
如何提高吞吐量：复制、扩容、异步化、缓存；
如何保障稳定性：提高可用性、分组和隔离、限流、降级、监控和故障切换；
理解高可用系统：要做到数据不丢，就必需要持久化；要做到服务高可用，就必需要有备用（复本），无论是应用结点还是数据结点；要做到复制，就会有数据一致性的问题；我们不可能做到100%的高可用，也就是说，我们能做到几个9个的SLA；

其他面试小结

扫一扫关注我的微信公众号

面试小结之综合篇

介绍一下你熟悉的几种排序算法以及它们的时间复杂度。

冒泡排序

快速排序

堆排序

谈谈对Spring IoC的理解。

谈谈对Spring AOP的理解。

Spring MVC的核心流程是什么样的？

Redis和Memcached的异同。

Memcached

Redis

Redis作为分布式缓存可能会存在哪些问题，怎么解决？

谈谈对Mysql索引的认识。

MySql的事务隔离级别有哪几种？

MySql的MVVC有什么作用？

如何设计高性能、高并发、高可用的系统。

其他面试小结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java面试

数据结构与算法

笔试&&面试经验

Java学习笔记

程序员

首页投稿（暂停使用，暂停投稿）

Java