Java面试数据结构与算法笔试&&面试经验

面试小结之综合篇

2017-06-14  本文已影响329人  ginobefun

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

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

冒泡排序

    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;
                }
            }
        }
    }

快速排序

    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 的右子节点下标

谈谈对Spring IoC的理解。

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

传统做法

传统做法

IoC做法

IoC做法 
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的理解。

// 定义接口
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);

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

核心流程

具体步骤：

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

Redis和Memcached的异同。

Memcached

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

Redis

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

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

谈谈对Mysql索引的认识。

MySQL索引

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

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

MySql的MVVC有什么作用？

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

其他面试小结

扫一扫 关注我的微信公众号
上一篇下一篇

猜你喜欢

热点阅读