好久没记录面试,上一次写面试过程是在毕业左右找工作的时候,祥见:《广州银行信用卡中心 数据挖掘 笔试题》,转眼已经两三年了。今天就记录一下吧。

自我介绍

讲了下从大学以来的工作经验和项目经历:

  • 大学
    • 数据挖掘比赛
    • 机器人比赛
    • 信息攻防比赛
  • 工作
    • 爬虫
    • 数据清洗
    • 创业:区块链
    • 问答机器人(自然语言处理)
    • 大数据开发及运维
    • 高并发服务
    • 各种技术研究
    • 其他

简单介绍后就进行细节的技术问题了

自认为答得比较好的问题

  • java常用数据结构之HashMap
    • 这个看过点源码,还算可以。网上有一篇比较好的博客介绍,详见《Java集合框架——Java Collections Framework》
    • HashMap的原理:哈希函数
    • 长度resize什么时候触发:loadFactor扩容阈值
    • 如何平滑resize而不影响线上业务:调大loadFactor,设置自己的loadFactor2,其中loadFactor2 < loadFactor,当到达loadFactor2时,则拷贝新map,新map的容量大于旧map容量,之后再切换map到新map上实现平滑更新。
    • HashMap线程不安全,如何使之线程安全:
  • MySQL索引
    • 比较详细地讲了innodb和myiram两种引擎的原理,B+树(第一次口误说成红黑树,红黑树是HashMap Java 8 的哈希碰撞时的实现)
      • innodb:适合读写都多的场景,也是默认选项。数据在叶节点。支持事务。
      • myiram:适合读多写少的场景。数据在外存。
      • 注意mysql的cache值,不对字段长的键进行索引,innodb主键尽量使用id。
      • 参考《mysql 数据库引擎》
  • SQL优化
    • 建表时考虑读取的QPS、where语句,对其进行索引和考虑设置缓存/批量读取。
    • where语句中,筛选度大的写前面。
    • 能分开查的尽量分开查,尽量减少一大坨sql的情况。
    • 涉及到计算的尽量交给语言去处理,sql查询比较擅长。
  • 高并发架构
    • 原则很简单:尽量将请求进行批量、挡在最外层(防止请求穿透)
    • 由外到内 == 存取速度由快到慢
      • cpu
      • 内存
      • 缓存
      • i/o
      • 远程rpc网络传输
    • 使用高效的第三方库,如golang的jsonitor和java的fastjson。
    • 减少无用日志输出
    • 批量读写
    • 异步
    • 用了两台机器实现了3.1k QPS的golang服务,如何优化的?提到了因为go的效率比较高,并发好。(在这里衍生到了协程和线程的话题
  • ETL流程
    • APP日志上报、在线业务更新数据库
    • 上报日志 -> Kafka -> Flink/Flume -> S3 -> Hive查询
    • 在线MySQL数据库 -> binlog -> offline数据库 -> DataX -> S3 -> Hive查询
    • MongoDB/Elasticsearch/Redis -> DataX/python脚本 -> S3 -> Hive查询
    • 最终的目的是在一个平台上可以查询到各个异构数据源的数据,进行数据分析,用presto/spark查询的效率更快。
    • 这里有个关于Hive的问题:group by和sorted by的概念,没细答。

答得一般的问题

  • group by和sorted by的概念
  • 死锁的概念及其解决办法
    • 概念还是回答得可以,一个单向有环图,环里的每一个节点都掌握上一个节点的资源,并等待下一个节点释放其手中的资源。这种情况叫死锁。
    • 我提到的解决办法1:每个节点/实例都设置超时时间,超过了就放弃本次任务,释放资源。
    • 我提到的解决办法2:每个节点都向一个宏观决策者发送心跳,由宏观决策者调度该哪个节点释放资源(为了任务不失败,可以先释放并挂起丢入等待队列,等待下一次唤醒。)
    • TODO 更好的办法呢?
  • Java框架(只用过Spring boot 2)
    • 用Bean等注解有什么优势?
      • 我的答案:方便,减少代码量
      • TODO 更好的答案呢?
    • Spring boot 相对于其他框架有什么优势?
      • 我的答案:方便,集成tomcat和Mybatis等常用框架,快速上手和部署。
      • TODO 更好的答案呢?
  • Java经验的问题:用得少,接触到现在有3年了。如果进去可以学Java,不局限于语言,学习速度快。
  • 推荐系统icf和ucf的区别
    • icf
    • ucf
    • 用户多的时候用哪个算法?
    • 物品多的时候用哪个算法?我回答icf
    • 那个效率高?
    • 实验结果哪个好?我回答icf,这是实践中得出的结论,指标包括召回率、覆盖率、点击率等。
  • 以及聚类的算法有哪几种?
    • 答了K-Means
    • 如何确定K?
      • 我的答案:业务/观察数据分布进行调参
      • TODO 更好的答案呢?
    • 适合什么样的数据场景?
      • 我的答案:数据密集型,有可观的密集簇。不适合稀疏数据。
      • TODO 更好的答案呢?
  • 协程和线程的区别:
    • 感觉用全局锁和记录级别锁的关系来理解线程和协程的区别???
    • 我的回答
      • 线程依赖于CPU核数,协程不依赖
    • 更好的回答:看下文。
  • 数据库事务
    • 没了解 TODO 需要研究

结尾

今天的记录就到这里了,接下来需要对这次面试遇到的问题进行研究:

  • 线程/协程
    • 参考文章:《进程、线程和协程之间的区别和联系》《进程、线程、协程之概念理解》
    • 进程(系统控制级别)
      • 所维护的是程序所包含的资源(静态资源), 如:地址空间,打开的文件句柄集,文件系统状态,信号处理handler等;
      • 资源分配的最小单位;
      • 系统开销:大于线程的开销;
      • 安全性:一个进程崩溃后,在保护模式下不会对其他进程产生影响。多进程的程序要比多线程的程序健壮,但在进程切换时,耗费资源比线程较大,效率比在线程切换要差一些。
      • 一个进程至少一个线程
      • 同一进程的多个线程共享该进程资源。
    • 线程(系统控制级别)
      • 有时被称为轻量级进程(Lightweight Process,LWP),是真正在处理机上运行的单位,是操作系统调度(CPU调度)执行的最小单位。
      • 所维护的运行相关的资源(动态资源),如:运行栈,调度相关的控制信息,待处理的信号集等;
      • 在执行过程中,需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。
      • 系统开销:上下文切换开销,任务少创建太多线程,会造成大量的线程处于等待状态(CPU通过时间分配算法来执行任务,在切换前会保持上一个任务状态,在单核处理器中,并发其实也是串行执行。)
      • 安全性:一个进程死掉,其所有线程都死掉。
      • 多个线程相对独立,有自己的上下文,切换受系统控制
      • 由于线程之间的相互制约,致使线程 在运行中呈现出间断性。
      • 一个线程可以创建和撤消另一个线程,同一进程中的多个线程之间可以并发执行。
    • 协程(程序控制级别)
      • 又称微线程,纤程。英文名Coroutine。
      • 子程序,或者称为函数,在所有语言中都是层级调用,比如A调用B,B在执行过程中又调用了C,C执行完毕返回,B执行完毕返回,最后是A执行完毕。所以子程序调用是通过栈实现的,一个线程就是执行一个子程序。子程序调用总是一个入口,一次返回,调用顺序是明确的。而协程的调用和子程序不同。
      • 协程看上去也是子程序,但执行过程中,在子程序内部可中断,然后转而执行别的子程序,在适当的时候再返回来接着执行。
      • 极高的执行效率:因为子程序切换不是线程切换,而是由程序自身控制,因此,没有线程切换的开销(更没有进程切换的开销),和多线程比,线程数量越多,协程的性能优势就越明显(充分利用CPU分片时间,使CPU总是有事做,而不会历经等待线程的过程);
      • 不需要多线程的锁机制:因为只有一个线程,也不存在同时写变量冲突,在协程中控制共享资源不加锁,只需要判断状态就好了,所以执行效率比多线程高很多。
      • 一个程序可以包含多个协程,可以对比与一个进程包含多个线程
      • 协程也相对独立,有自己的上下文,但是其切换由自己控制,由当前协程切换到其他协程由当前协程来控制。
    • 并发与并行
      • 实现并发技术相当复杂,最容易理解的是“时间片轮转进程调度算法”,它的思想简 单介绍如下:在操作系统的管理下,所有正在运行的进程轮流使用CPU,每个进程允许占用CPU的时间非常短(比如10毫秒),这样用户根本感觉不出来 CPU是在轮流为多个进程服务,就好象所有的进程都在不间断地运行一样。但实际上在任何一个时间内有且仅有一个进程占有CPU。 如果一台计算机有多个CPU,情况就不同了,如果进程数小于CPU数,则不同的进程可以分配给不同的CPU来运行,这样,多个进程就是真正同时运行的,这 便是并行。但如果进程数大于CPU数,则仍然需要使用并发技术。 进行CPU分配是以线程为单位的,一个进程可能由多个线程组成,这时情况更加复杂,但简单地说,有如下关系:
      • 总线程数 <= CPU数量:并行运行
      • 总线程数 > CPU数量:并发运行
      • 并行运行的效率显然高于并发运行
    • 知乎上的引用

      一开始大家想要同一时间执行那么三五个程序,大家能一块跑一跑。特别是UI什么的,别一上计算量比较大的玩意就跟死机一样。

      于是就有了并发,从程序员的角度可以看成是多个独立的逻辑流。内部可以是多cpu并行,也可以是单cpu时间分片,能快速的切换逻辑流,看起来像是大家一块跑的就行。但是一块跑就有问题了。我计算到一半,刚把多次方程解到最后一步,你突然插进来,我的中间状态咋办,我用来储存的内存被你覆盖了咋办?所以跑在一个cpu里面的并发都需要处理上下文切换的问题

      进程就是这样抽象出来个一个概念,搭配虚拟内存、进程表之类的东西,用来管理独立的程序运行、切换。

      后来一电脑上有了好几个cpu,好咧,大家都别闲着,一人跑一进程。就是所谓的并行。因为程序的使用涉及大量的计算机资源配置,把这活随意的交给用户程序,非常容易让整个系统分分钟被搞跪,资源分配也很难做到相对的公平。所以核心的操作需要陷入内核(kernel),切换到操作系统,让老大帮你来做。(即进程/线程的管理是属于系统态的)

      有的时候碰着I/O访问,阻塞了后面所有的计算。空着也是空着,老大就直接把CPU切换到其他进程,让人家先用着。当然除了I\O阻塞,还有时钟阻塞等等。一开始大家都这样弄,后来发现不成,太慢了。为啥呀,一切换进程得反复进入内核,置换掉一大堆状态。进程数一高,大部分系统资源就被进程切换给吃掉了。

      后来搞出线程的概念,大致意思就是,这个地方阻塞了,但我(进程)还有其他地方的逻辑流可以计算,这些逻辑流是共享一个地址空间的,不用特别麻烦的切换页表、刷新TLB,只要把寄存器刷新一遍就行,能比切换进程开销少点。

      如果连时钟阻塞、线程切换这些功能我们都不需要了,自己在进程里面写一个逻辑流调度的东西。那么我们即可以利用到并发优势,又可以避免反复系统调用,还有进程切换造成的开销,分分钟给你上几千个逻辑流不费力。这就是用户态线程

      从上面可以看到,实现一个用户态线程有两个必须要处理的问题:一是碰着阻塞式I\O会导致整个进程被挂起;二是由于缺乏时钟阻塞,进程需要自己拥有调度线程的能力。

      如果一种实现使得每个线程需要自己通过调用某个方法,主动交出控制权。那么我们就称这种用户态线程是协作式的,即是协程。本质上协程就是用户空间下的线程。

      线程用得好确实比协程效率高,但是开发麻烦。因为能达到真正的并行计算;而协程是非抢占式的,同一时间只有一个协程拥有控制权,因此相当于单线程的能力。

      说协程性能好的,大部分是因为瓶颈在I/O上面。协程的切换顺序很难保证,需要做一些同步操作。协程安全和兼容性问题?

    • 协程,本质上是子函数,是一种合理使用了goto语法的函数。 “一种拥有上下文环境的goto,而且是可以goto到具体哪一个函数的哪一行代码的那种,且开发效率高的那种。”

  • 分布式

  • 数据库事务
  • Java基础/框架
  • 聚类的常见算法
  • icf和ucf
  • group by和sorted by的概念
  • 死锁的概念及其解决办法
  • Java框架(只用过Spring boot 2)
    • 用Bean等注解有什么优势?
    • Spring boot 相对于其他框架有什么优势?
  • B+树和红黑树的区别?
    可能会不定期更新本文,也可能新建一篇文章,也可能默默研究不发表。不管怎么说,这次学到不少!