阿里大淘宝技术后端实习笔面经
笔试: 单选6+多选7+编程题3, 满分100, 好像做到40分就能进面试.
! 不能用本地IDE
笔试
选择题
单选和多选感觉挺难, 记录几个知识点.
- 如何根据中序遍历 + 后序遍历 确定唯一的二叉树.
- 基数排序, 高位优先(MSD)和低位优先(LSD).
- Linux grep指令
- 正则表达式
\w等价于[A-Za-z0-9_];\W等价于[^A-Za-z0-9_]. - 分页管理中, 内部碎片和外部碎片.
- 树和森林与二叉树的转换: 左孩子右兄弟法参考
- 循环队列的
front和rear. 当front == rear时, 队列为空;(rear + 1) % size == front时, 队列满;(rear - front + size) % size为队列长度.
算法题
第一题 定义好树是红色节点比蓝色节点多的树。输入一棵好树，想要从其中删去一边后得到的两棵树都是好树，输出有多少种删除的方法。简单的dfs ，0%
用一个数组r[n]存以各个节点为根的子树的红色节点数，一个数组b[n]存以各个节点为根的子树的蓝色节点数，第一次dfs 求出这两个数组的值，第二次dfs 时候，如果要去掉一个节点和它的子节点（设这个子节点是编号为i的节点）之间的一条边，那么得到的一棵树的蓝色节点数为b[i]，红色节点数为r[i]，另一棵树的红色节点数为r[1]-r[i]，蓝色节点为b[1]-b[i]，（1号节点是根节点），然后判断一下这种情况是否满足要求，满足就把结果加一。
第二题 输入一个无符号整数数组，每次操作可以修改一个数的二进制表示的一个位，想要使得数组中每个数都相等，输出最少操作次数。只要看一下各个数位上有多少个数是0，有多少个数是1，将较小者累加到结果就行了。ac
这个题浪费了太久的时间.
Tips:
求二进制的时候, 每次除以2的余数是从后往前写的.
java直接转化的方法 Integer.toBinaryString(5);
java中LinkedList实现了Queue的接口, 所以可以把它当做队列来用.
第三题 输入一个整数，删除其连续的数位，使其成为15的倍数（可以有前导0），输出有多少种删除方法。0%
Tips: 难点: 15的倍数特点是个位数是5或0, 其余各个位之和为3的倍数.
面试 - 一面
面试自我介绍的时候我说我25年才能毕业, 然后面试官说他们只招24年毕业的, 因为那边转正率蛮高的.
我简历上忘了改了呜呜呜… 早知道自我介绍的时候不说了.
然后场面很尴尬, 我说我想练练开发岗的面试, 面试官超级好, 就给我来了一次模拟面试.
他说项目经历一点也不重要, 重要的是基础知识一定一定一定要扎实. 一般基础知识能回答到85%以上就可以进二面, 80%-75%会比较犹豫. 反正在校期间做的项目都没啥卵用, 不用补项目.
数据结构
树
Q: 你了解的树结构有哪些?
A: 二叉树, 多叉树, 完全二叉树, 二叉平衡查找树, B树, B+树, 红黑树.
Tips: 平衡二叉树的常用实现方法有 红黑树、AVL 树、替罪羊树、加权平衡树、伸展树 等。
树的关键词: 完全, 平衡, 查找
Q: 什么是完全二叉树?
A: 按照层序遍历从左到右, 完全没有空隙的树就是完全二叉树. (我当时不知道该怎么形容, 然后百度了一下)对树中的结点按从上至下、从左到右的顺序进行编号，如果编和满二叉树中的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
Q: 怎么向完全二叉树中插入节点?
A: (没答上来, 之后查了下)
两种方式.
第一种利用队列, 把倒数第二行子节点数小于2的节点从左到右入队, 然后最后一层从左到右入队. 插入新节点的时候, 让它作为队头节点的子节点, 如果队头的子节点满了, 则出队. 把新节点入队.
第二种利用二进制. 先遍历一遍求节点数. 插入的节点为第n个节点, 将n转换成二进制, 去掉首位, 从第二位开始, 0往左走1往右走, 最后就能走到自己的位置.
Tips: 树的BFS和层序遍历是一回事.链表
Q: 你了解哪些链表?
A: 单向链表, 双向链表, 循环链表, 双向循环链表.
Q: 好的. 每个链表适用于哪些场景?
A: (懵逼)(不会… 下来整理了一下)双向链表可以在节点前后插入, 也可以删掉前驱和后继. 而单向链表只能向后插入. 双向链表通过增加了一定的空间复杂度, 提升了向前遍历的时间复杂度. 循环链表首尾相连, 可以从任意一个节点出发, 遍历链表全部节点, 适合解决有环装特性的数据(如约瑟夫环). 双向循环链表有循环链表和双向链表的特性.
Q: 循环链表怎样插入?
A: (思考: 我真的好不熟悉, 还要现场思考.) 循环链表一般保存尾节点的指针(因为这样头插和尾插都很快). 实际在任何一个位置插入的方式都是一样的.
Q: 你知道跳表吗?
A: 不知道 (汗)
补充学习:
跳表: 可以实现二分查找的有序链表. 跳表的查找、插入、删除的时间复杂度都是 O(logn)，而且可以按照范围区间查找元素.
为什么Redis使用跳表而不是红黑树来实现有序集合?
当需要按照区间查找元素时, 跳表的效率更高O(logn).
红黑树: 红黑树（Red Black Tree） 是一种 自平衡 二叉查找树，典型的用途是实现关联数组.
它可以在O(log n)时间内做查找，插入和删除，这里的 n 是树中元素的数目.
把二叉树所有结点投射在X轴上，所有结点都是从左到右排好序的，所有目标结点的前后结点就是对应前继和后继结点.
BST, AVL, Red-black tree, B tree, B+ tree
Q: 一般内存和运行内存了解吗?
A: (懵逼… 好像面经里没有这个东西呀) 不了解.
Tips: 实际上就是ROM和RAM. RAM随机存取, 掉电后就丢失数据. RAM的运行速度远高于ROM. 之前就只知道运行内存这个东西, 学os的时候根本没把它和ram联系起来.
Q: CPU的一级缓存二级缓存可以向我介绍一下吗?
A: 不了解.
Tips: CPU缓存
印象里只有Cache了, 不记得它的中文是缓存. CPU缓存（Cache Memory）是位于CPU与内存之间的临时存储器，它的容量比内存小的多但是交换速度却比内存要快得多.
一般有一级二级三级缓存,一级缓存有一级指令缓存和一级数据缓存, 二三级缓存主要都是存储数据.
Q: Java中的锁了解吗?
A: 不…
Q: 这些都是要了解的呀. Java的单机锁, 分布式锁. 还有互斥锁这些…
Q: 再来问一个计网的问题, 当数据从发送端到接收端, 数据经历了哪些部件?
A:…
Q: 丢包之后会发生什么?
Q: 所以是没发送一个数据段, 接收端都会发送一个ACK吗?
A: 是吧.
Q: 再来问问数据库好了, 关于索引的底层实现你知道哪些?
A: B+树, 红黑树.
Q: 它们有哪些特征?
Q: 你这里最好还要补充一下Java中间件 / 开源框架的知识. 去看源文档或者看论坛的解析啦.
后面就是闲聊…