字节跳动，PDD后端开发面经分享

kafka:
发消息的流程
comsumer group vs partition
comsumer rebalance?
ISR?

消息堆积处理方法？ 要么加线程(partitoin) 要么批量
成批poll, 事务功能关闭
增加partition，consumer数量，consumer用工作线程加阻塞队列来接收

如果是有大量提交失败导致重复消费，需要看一下原因session.timeout.ms

es:
es 倒排索引，支持事务支持吗

从节点可以写入吗？
写入流程？写到内存还是磁盘？ 写入buffer 和translog -> 定期同步buffer到os cahce, 在此期间translog保证数据可靠
还要调用fsync才能把数据刷到磁盘中

一条日志记录了，用户使用app的开始和结束的时间，用户时间可表示为[start..end]的区间
求一堆日志里面，用户在线人数最多的时间和数量：

所有用户的总时间区间可以为[L..R]
利用倒排索引思想，将每个区间按照下标对应加起来，找出[L..R]中的最大值下标(优化 利用数据结构堆)

---
先闲聊 花旗 字节跳动的区别

高工要求 压力面
LinkedList 循环链表 foreach栈爆问题 -> 编译原理 AST nfa/dfa
ArrayList 连续内存，CPU cache加速

注册到多路复用器
NIO/高并发 =>  epoll vs poll:
epoll 就绪链表
eventLoop 轮询对CPU的消耗
Netty的 API gate 设计 性能问题http协议解析压力，IP白名单过滤
异步事件处理: 一般有一个event[fd]的数组，将回调函数与fd进行绑定

进程的文件描述符

M的线段，分成N份的分法
C m (n-1)

回溯算法就是一颗决策树，回溯算法的关键：路径(已经做过的选择)，可选列表，结束条件
result = []
def backtrack(path, select):
  if(end condition):
    result.add(path)
    return
  for (s in select):
    做出选择
    backtrack(path, select)
    撤销选择

backtrack 函数其实就像一个指针，在这棵树上游走
---
编译原理知识回顾
词义分析
语法分析
语义分析 -> 文法分析树 不确定分析(回溯分析) 确定分析(预测分析)  正则表达式(nfa/dfa)

编译时常用代码优化:
局部公共子表达式替换
复制传播删除无用代码/常量合并/代码移动(减少循环内执行的指令数)，循环不变计算/强度削弱


java 的编译原理: JIT
逃逸分析，循环优化


---
三面: 交叉

自我介绍做的项目，和我在其中所做的工作
选一个项目(yume, citi hawk数据质量可视化)说一说项目结构
数据输入，输出，如何处理freemark的rule形式，为什么用template？
规则引擎的怎么设计的，有哪些类？怎么判断消息应该用什么rule校验

研究过什么开源项目？提交了code吗?(spring/vertx/netty/apache geode)

你有什么问题？


四面:

你对现有的项目有什么改进？或者你觉得你们项目还需要完善的地方
你考虑的出发点是什么

广告消息系统过滤设计？
kafka, 分流

高吞吐量系统应当注意什么？
如何保持稳定，高可用
监控/fail over

新功能如何稳定发布，降低风险？
多个环境测试/发布的时机应该是闲时/开发和support权限隔离，维护prd环境的稳定

算法: 数组子序列最大和(dp秒了)
sum(n) = if sum(n-1) > 0:  sum(n-1) + arr[n] else: n

说一下你的优点和缺点
问答环节:讲解了一下广告相关的，计算广告(归因，追溯，dpa, 对照试验)

hr面:
自我介绍下最近两年的情况
印象深刻并且有收获的项目
在team中充当什么角色


-------------
PDD:

一面：
算法： 具体啥忘了， 反正就是一个树递归的样子，比较简单
ELK, zipkin, hystrix滑动窗口(基于错误率和流量)，ribbon负责均衡常用的算法


二面：
算法： 找区间内地波峰波谷： 其实就是一个肯定有至少一个极值读区间，如何快速找到之后任意一个极值(logN 二分)
事务 RR隔离级别具体实现： 
幻读(
读偏差: 只读事物 MVCC
写偏差: 2PL, SSI(基于冲突检测读乐观事物并发控制)
)
数据库自增主键ID的原因，顺序写入，避免B树页拆分(前提是非堆集表)
redis 大量过期key怎么删除? 单线程不能执行太久， 堆？
淘汰机制lru, ttl, random
cas的应用，高并发和高qps的区别？线程一定多吗？

高QPS需要的是no-blocking 而不是频繁的线程阻塞并切换，这样才适合cas进行同步
项目经验
MQ怎么处理消息重复(全局id的保存)，消息丢失(recon 统计)
吐槽项目: DBA保守，用geode， 规则引擎扩展性不高，描述能力过时



三面：

数据仓库项目中用了什么技术?

发行版（CDH这一套）hive, sparkSQL, impala



hive和impala 区别是使用场景： 可共享meta数据， 

hive是横向切分MR架构(模型更加通用，支持的数据格式更general, 当然速度肯定也慢)，适用于批处理job

impala是竖向切分MPP架构，有点交互式查询的味道，操作都在内存，且有数据格式优化(支持的数据格式少)，容错也低



最近开了什么比较有收获的书, 推荐一下，好在哪里？ ddia



hr：

想在哪里发展？

有没有女朋友？

有没有其他offer?