发布于 

阿里大淘宝技术后端实习笔面经

笔试: 单选6+多选7+编程题3, 满分100, 好像做到40分就能进面试.
! 不能用本地IDE

笔试

选择题

单选和多选感觉挺难, 记录几个知识点.

  1. 如何根据中序遍历 + 后序遍历 确定唯一的二叉树.
  2. 基数排序, 高位优先(MSD)和低位优先(LSD).
  3. Linux grep指令
  4. 正则表达式 \w 等价于 [A-Za-z0-9_]; \W等价于[^A-Za-z0-9_].
  5. 分页管理中, 内部碎片和外部碎片.
  6. 树和森林与二叉树的转换: 左孩子右兄弟法参考
  7. 循环队列的frontrear. 当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与内存之间的临时存储器,它的容量比内存小的多但是交换速度却比内存要快得多.
一般有一级二级三级缓存,一级缓存有一级指令缓存和一级数据缓存, 二三级缓存主要都是存储数据.

一条指令在CPU中的执行过程

Q: Java中的锁了解吗?
A: 不…
Q: 这些都是要了解的呀. Java的单机锁, 分布式锁. 还有互斥锁这些…

Q: 再来问一个计网的问题, 当数据从发送端到接收端, 数据经历了哪些部件?
A:…

Q: 丢包之后会发生什么?

Q: 所以是没发送一个数据段, 接收端都会发送一个ACK吗?
A: 是吧.

Q: 再来问问数据库好了, 关于索引的底层实现你知道哪些?
A: B+树, 红黑树.
Q: 它们有哪些特征?

Q: 你这里最好还要补充一下Java中间件 / 开源框架的知识. 去看源文档或者看论坛的解析啦.

后面就是闲聊…