- Meituan
Meituan
- 作者：愿闻其详 https://www.nowcoder.com/discuss/129446?type=post&order=time&pos=&page=1来源：牛客网
1.讲一下MapReduce的过程，是在一台主机上reduce吗？可不可以多台？数据怎么汇总？
数据被分割后通过Map函数将数据映射成不同的区块，分配给计算集群进行处理，以达到分布运算的效果，再通过Reduce函数将结果进行汇整，从而输出开发者所需要的结果。
2.有了解Spark吗？Spark为什么比Hadoop要快？
###3.谈谈poll和epoll，epoll是同步还是异步
IO多路复用的机制
###4.JMM、老年代在什么情况下会触发GC、对老年代的GC会不会导致程序卡顿？（最优吞吐量和最短停顿时间）
###5.谈谈你所掌握的数据结构
###6.讲一讲红黑树
搜索二叉树插入随机数据，效果很好；但是有序数据的话，插入执行速度比较慢；为了保证树的平衡性，即保证某一节点左子树和右子树节点数目大致相等，就有了红黑树。
- 节点有颜色。boolean 型变量，以此来表示节点的颜色信息。
- 在插入和删除的过程中，要遵循规则：
- 每个节点不是红色就是黑色的；
- 根节点总是黑色的；
- 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
- 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
由于这些特征，红黑树中插入的节点都是红色的，红色违背规则可能性更小，违背的话也更容易修复。
平衡性修复
改变节点颜色 左旋 右旋
如果是第一次插入，由于原树为空，所以只会违反红-黑树的规则2，所以只要把根节点涂黑即可；如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；下面情况需要变色和旋转，
- 插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的；
- 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点；
- 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。
###7.红黑树插入一个结点的时间复杂度
$O(logn)$
8.你所知道的算法的时间复杂度有哪些？快排的复杂度是多少？为什么？
###9.HashMap的实现，为什么结点插在链表的头部容易导致死锁
HashMap使用指针数组table[]来分散key，
当key加入时，通过hash算法算出数组下标[i]，然后把<key, value>插入table[i]
如果有两个不同的key被算在了同一个i，就叫冲突，又叫碰撞，这样会在 table[i]上形成一个链表。
如果 table[]的尺寸很小，比如只有2个，如果要放进10个 keys 的话，那么碰撞非常频繁，于是一个 O(1)的查找算法，就变成了链表遍历，性能变成了 O(n)，这是 Hash 表的缺陷。
一般来说，Hash 表这个容器当有数据要插入时，都会检查容量有没有超过设定的 thredhold，如果超过，需要增大 Hash 表的尺寸，但是这样一来，整个 Hash 表里的无素都需要被重算一遍。这叫 rehash，成本很大。
###10.HashMap扩容
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值，就要自动扩容。
在对 HashMap 进行扩容时，阀值会变为原来的两倍，HashMap的容量也会变为原来的两倍；
扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
###11.手撕代码：
- 字符串a和b，假设只由26种小写字母组成，且a比b长，判断b中字符是否在a中都有出现
###12.平时怎么学习
###13.堆栈和线程的关系
堆： 分全局堆和局部堆。全局堆就是所有没有分配的空间，局部堆就是用户分配的空间。堆在操作系统对进程初始化的时候分配，运行过程中也可以向系统要额外的堆，但是记得用完了要还给操作系统，要不然就是内存泄漏。一般由程序员分配释放。
栈：是个线程独有的，保存其运行状态和局部变量的。栈在线程开始的时候初始化，每个线程的栈互相独立，因此，栈是 thread safe的。操作系统在切换线程的时候会自动的切换栈，就是切换 ＳＳ／ＥＳＰ寄存器。由编译器自动分配释放。
###14.Java类加载过程
###15.手撕代码：双向有序链表，去除有重复值的所有结点
###16.说你熟悉的几种设计模式，手写单例设计模式
###17.ConcurrentHashMap的实现有了解吗
###18.画B+树的底层框图，B+树的叶子结点是什么结构
###19.给已经存有0-99的索引的B+树，查询3-30的索引对应的记录
20.你未来半年的计划
###21.将项目中用到的SIFT的原理，要很详细
###22.手撕代码：给定整型数组，构造搜索二叉树
###23.你的博客一般写什么，讲几个，讲容器，类加载
数据开发工程师
1.线程和进程的区别
- 地址空间和其它资源：进程间相互独立，同一进程的各线程间共享。某进程内的线程在其它进程不可见。
- 进程是资源分配单元，线程是执行单元。
- 通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性。
- 调度和切换：线程上下文切换比进程上下文切换要快得多。
2.网络协议
3.动态规划和递归哪个好，有什么区别
4.数组和链表的区别？应用场景是什么？读取和插入的复杂度？
5.Python常用的5个库
设计模式
902大面筋
1.Java类加载
2.内核态怎么到用户态
什么时候转换？
- 系统调用：为了使上层应用能够访问到这些资源，内核为上层应用提供访问的接口。
- 异常事件： 当CPU正在执行运行在用户态的程序时，突然发生某些预先不可知的异常事件，这个时候就会触发从当前用户态执行的进程转向内核态执行相关的异常事件，典型的如缺页异常。
- 外围设备的中断：当外围设备完成用户的请求操作后，会像CPU发出中断信号，此时，CPU就会暂停执行下一条即将要执行的指令，转而去执行中断信号对应的处理程序，如果先前执行的指令是在用户态下，则自然就发生从用户态到内核态的转换。
怎么转换？
通过中断机制实现
- 从当前进程的描述符中提取其内核栈的ss0及esp0信息。
- 使用ss0和esp0指向的内核栈将当前进程的cs,eip，eflags，ss,esp信息保存起来，这个过程也完成了由用 户栈找到内核栈的切换过程，同时保存了被暂停执行的程序的下一条指令。
- 将先前由中断向量检索得到的中断处理程序的cs，eip信息装入相应的寄存器，开始执行中断处理程序，这 时就转到了内核态的程序执行了。
3.定位到占用大量资源的某一行代码
- 使用top命令定位异常进程
- 使用
top -H -p 进程号查看异常线程 - 使用
printf "%x\n 线程号将异常线程号转化为16进制 - 使用
jstack 进程号|grep 16进制异常线程号 -A90来定位异常代码的位置（最后的-A90是日志行数，也可以输出为文本文件或使用其他数字）。可以看到异常代码的位置。
4.MySql索引
目的：帮助MySQL高效获取数据的排序的数据结构。减少磁盘IO操作。
hash表：内存型存储引擎使用哈希表，速度快。无法范围查找和排序。
常使用的数据结构是B+树，
- 搜索二叉树：查询性能与高度成反比
- 红黑树：高度平衡，但是数据量大时高度仍然很大；红黑树相比于AVL树，牺牲了部分平衡性，以换取删除/插入操作时少量的旋转次数，整体来说，性能优于AVL树。
- B树：一个节点存多个元素（16k），矮胖树，不支持范围查找
- B+树：更矮胖，非叶节点不存数据，只存索引；叶节点链表方便范围查找。
inodb
- B+树存储引擎
- 聚集索引：索引和数据聚集在一起，叶节点存储了所在行的所有信息
- 必须有主键：整型的自增主键（防止分裂），如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。
myiasm
-
B+树存储引擎
-
非聚集索引：叶节点的data域存放的是数据记录的地址