记录一些面试中记忆比较深刻的问题

本贴最后更新于 1549 天前,其中的信息可能已经时过境迁

前言

最近在广东找工作,天天疲于奔波各种面试,大大小小的公司零零总总,记录一些自己感觉有意思的面试/笔试题/机试题。根据各个面试官的提问,做了一部分汇总,所以记录中是所有公司面试的一个超集,不代表某一个公司。

题目来自记忆,并不是照抄,只表达含义。

更重要的是,我记录的大多来自记忆,有些可能已经有错了,如有遗漏/错误,请留言更正,帮助我以及更多的人纠正,谢谢!

因面试未完成,持续更新~

向大家请教以下面试经验

如何回答以下两个问题,真心求解,一直感觉答不好:

  • 介绍一下自己
  • 开发过程中遇到过什么问题,怎么解决的?

正文

一些笔试

实现两个大整数相乘,不能使用 BigInteger 之类的现有 api,需适当考虑效率

自己用的竖式做出来,时间复杂度为 O(n^2),其实当第一次看到这个问题时,首先就想到分段计算了,但是仔细想了想,仍然是 O(n^2)的时间复杂度,优化空间并不大,具体代码很简单,就不赘述了。

在与小伙伴们聊到这个问题时,帮我提供了一种算法:Karatsuba(分治算法)。

中心思想是这样子:将大数分成两段后变成较小的数位,然后做 3 次乘法,并附带少量的加法操作和移位操作。

首先,有两个大整数 a,b。

可以写成:


a = a0 * 10^m + a1;

b = b0 * 10^m + b1;

其中 m 是最小的正整数,使得 a0,a1,b0,b1 < B^m,也就是把 a,b 切成了两半。接下来推导:


a * b = (a0 * 10^m + a1)(b0 * 10^m + b1)

      = a0 * b0 * 10^2m + (a0 * b1 + b0 * a1) * 10^m + a1 * b1

      = a0 * b0 * 10^2m + (a0 + a1)(b0 + b1)* 10^m - (a0 * b0 + a1 * b1)*10 ^ m + a1 * b1

在这之后,发现只需要计算三次乘法 a0 * b0a1 * b1(a0 + a1) * (b0 + b1) 以及六次加法。

时间复杂度为:

T(n) = 3T(n / 2) + 6n = O(n^log3) ~= n ^ 1.585

一些面试

讲述一下 hashmap

没看过 jdk7 的源码,只看过 jdk8 的,所以我的描述来自 jdk8。

jdk 提供的键值对容器,内部使用数组加链表结构存储,通过对键进行 hash 均匀分布在数组中,当出现 hash 冲突时,进行链表链接,当链表达到一定长度之后,转换为红黑树。

默认大小?负载因子?

默认大小是 16,负载因子是 0.75

转换成红黑树的时机

链表长度大于等于 8 时转化为红黑树

线程是否安全,如何在线程安全下使用

线程不安全,可以有以下几种方式:

  • Collections.synchronizedMap 包装
  • 使用 HashTable
  • 最主流的还是使用 ConcurrentHashMap 类

说说 ConcurrentHashMap 如何实现线程安全?

ConcurrentHashMap 使用了大量的 volatile,final,CAS 等无锁技术减少锁竞争。在不得不加锁的情况下:例如 put,使用了局部加锁而不是全局加锁。

说说 synchronized 关键字

synchronized 是用来保证同一时刻只有一个线程可以执行它修饰的方法和代码块,具有可重入性。

说说单例模式?多线程下怎么使用?

单例模式分为懒汉模式和饿汉模式。

饿汉模式是在类初始化时即初始化,没有线程安全问题。

懒汉模式是延迟加载的,多线程下会有线程安全问题,简单的可以直接使用 synchnoized 方法修饰获取方法或者代码块,为了效率进行优化,可以使用两层检查,也就是一层不加锁的情况下保证在已经初始化之后的获取性能,在判断中加入同步代码块再进行一次检查,保证多个线程都在第一次获取时的线程安全问题。

synchronized 实现原理了解过吗?

简单看过,jvm 对于每个对象都会有一个 monitor 监视器,当使用 synchronized 包装时,实际上就是在与 monitor 进行交流,底层使用操作系统的内核 api,应该是叫 MutexLock,它的数量有限,并且因为调用它的时候会产生用户空间和内核空间的交互,所以效率较低,jvm 为它提供了锁升级过程进行优化。(这里忘了说 jvm 的 moniterenter 和 monitorexit 指令,应该可以加点分吧)

后面为自己加了点戏:

锁的升级过程是无锁-> 偏向锁-> 轻量级锁-> 重量级锁。当第一个线程进入到同步代码块时,jvm 并不会首先为它向内核空间获取锁,而是放置了一个偏向锁标志,然后就直接进入到代码块中,当其他线程来产生竞争时,锁就会升级到轻量级锁,此时也不会去内核空间是申请锁,而是采用自旋的方式,使用 CAS 尝试不断的修改标志中的线程 id 为自己,如果自旋超时,或者还有其他线程过来竞争(也就是竞争太激烈的情况下)就会去回退轻量级锁,去内核申请锁,也就是升级为重量级锁。

设计模式分为哪三大类,分别用来干什么?

设计模式分为创建型模式,结构型模式和行为型模式。

创建型模式主要用来创建对象,屏蔽创建细节,将对象的创建和使用分离

结构型模式主要用来组装(组合?)一系列对象,分为类结构性模式使用继承机制组织接口和类,对象结构型模式使用聚合的方式来组合对象。

行为型模式主要用来控制运行流程,描述如何写作共同完成某个任务。分为类行为模式和对象行为模式,前者使用继承机制在类之间分派行为,后者采用组合或者聚合的形式在对象间分配行为。

看你也有自己的开源项目,举例说说用过哪些模式?如何使用的?举例说说 jdk 中使用哪些模式?描述下某个模式的使用场景

说得有点多,略过。

用过 ThreadLocal 吗?用来干什么?

用过,ThreadLocal 主要用来共享线程私有变量,例如在 Spring Security 中就使用(默认)ThreadLocal 传递当前请求中缓存的权限信息。

ThreadLocal 使用需要注意什么吗?

主要应该是注意内存泄漏或者说脏数据的问题,当在使用它时,线程结束时会自动销毁,但是在线程池情况下,因为线程一般并未销毁,所以数据依然存在,可能发生内存泄漏。如果线程池中可能会有本次并未写数据,但是上次写入了,那么就会产生脏数据。

ThreadLocal 的原理了解吗?

简单了解过,ThreadLocal 实际上使用的是线程本身私有的一个 ThreadLocalMap 对象。当它在进行获取时,是将 ThreadLocal 本身做为键去 Map 中进行查询,这里还有一个延迟加载的初始化操作,如果本次查询未查询到,则会调用可继承实现的 initialValue 方法,我们在使用时也可以重写此方法以赋予初始值。当进行赋值时实际上也是延迟在线程中创建 map 的,默认容量时 16。

ThreadLocalMap 和 HashMap 有什么不同?

  • ThreadLocalMap 是一个完全和 HashMap 不同的实现,它是一个数组结构,存储的对象是一个 Entry,使用 ThreadLocal 作为键,value 作为值,没有 HashMap 那样的链表延长操作,当出现 hash 冲突的时候,它会向后依次寻找合适的位置进行插入,在获取时也是依次向后获取的。
  • 它的负载因子是 2/3 而不是 3/4。
  • 它的 hash 算法也是不一样的,它是每次固定增加一个基准值(不记得是多少)。
  • 它的 key 是弱引用而不是 hashMap 那样的强引用。

说说对 Spring 的 ApplicationContext 的理解

ApplicationContext 是 Spring 的核心 IOC 容器接口,用于生成和管理 Bean。它继承拓展了 BeanFactory 接口,提供了更多的功能。ApplicationContext 下面的具体实现例如 ClassPathXmlApplicationContext 等等用来解析不同的配置文件,也可以使用 GenericApplicationContext 来组合多个配置来源。


...一天写一点吧,今天就这样....

  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    325 引用 • 1395 回帖
  • 经验
    25 引用 • 157 回帖
  • 工作

    快乐工作,认真生活。

    139 引用 • 1469 回帖 • 6 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...