笔试部分是做了10道题目, 主要是类似于LeetCode上的题. 也包含了一些设计题目, 比如说怎么设计一个爬虫系统的去重. 在面试的时候答题纸也被送过来, 面试官会选择里面一个问题(主要是没做出来的)来问你.
题目我会记录下来放到GitHub上.
一面一面聊的时间很长, 总共70分钟左右.
总共问了三个大题吧. 发现在面试的过程中, 有一些问题是一开始没有思考到的, 在交流想法的时候发现漏掉了. 可能是没有一开始去设计测试用例, 或者去思考当前的可能的场景或者情况.
60分钟 限制用户访问不能超过5次以上
hashmap
目录树打印
一开始做了一个设计的题目. 场景是一些关键操作, 要对用户的访问次数或者访问时间做出限制. 给出的例子是要设计一个函数或者功能, 限制单一用户在60分钟之内不能访问超过5词以上. 类似实现一个函数, 输入是用户的 uid. 返回一个布尔值用于表示是否应该 block 掉该次访问.
当时一开始的想法是把记录存在一个数据库表里, 类似<访问时间, uid, 状态(block/OK)>
然后每次去数据库查, 获取到当前的60分钟之内的数据, 大于5条就选择block掉.
后来觉得放在MySQL这种数据库中太慢, 因为这个函数肯定是一个热点, 在每次接受请求的时候都会调用. 可以放在Redis这种内存数据库中.
此外, 由于这种规则的限制只考虑比如 x 分钟之内的记录. 可以只保存一定时间之内的访问记录, 超时就做一个失效的处理.
后来要求用一种数据结构实现, 在内存中直接计算.
发现可以做一个HashMap的形式, 里面保存的是 uid和一个表示访问记录的队列.这个队列里保存一些过去的访问记录. 可以通过时间和数量来选择最大的容量.
比如说我现在需要考虑过去60分钟的5次数据. 我可以选择容量是5, 最多容纳五条.我直接选取队列中最早插入的(时间距离现在最久)看这条记录时间是否比当前时间早60分钟. 如果超过了就说明最近60分钟的访问次数少于5次. 如果没超过说明需求被block.
在每次接受请求的时候都需要把访问记录放到这个队列中, 也就是会退出一个最早插入的, 再在队尾加一个当前的访问记录.
在手写代码的时候发现没有思考冷启动的问题, 需要判断如果队列不满, 就应该直接放入数据.这也是考虑欠妥当的地方.
第二个问题, 面试官问我是否了解 HashMap . 其实不很了解, 没看过源代码, 看过一些文章.说了一下链表过长会树化,有开放寻址和链表法解决Hash冲突的问题. 然后问我map里桶的数组保存的是什么, 我说是链表的头结点. 面试之后看了一下源码分析的文章, 其实map里就是保存了一个 Entry的数组, 每个Entry有指向下一个Entry的引用, 也就是一种链表的数组. 好像还问我什么时候扩容, 这个我答的不对. 后来看过是在map的大小超过阈值之后, 且发生了Hash冲突,才扩容. 在没超过阈值, 但是某个链表长度过长的时候发生树化.
第三个问题是问类似一个Linux的目录树, 怎么从[父目录, 子目录]这种信息构建出来.
提供的数据[[A,B],[B,C],[C,D],[D,E]] 这种, 构建出类似 Linux tree命令的结果.
需要考虑怎么构建树形结构, 还要考虑怎么能从树输出结果.
构建树, 把所有没出现过的父目录作为森林里的一个树的root节点. 如果出现过就把子目录放到对应的位置.
合并森林, 寻找一个只出现只出现在树根的节点, 表示全局的根目录. 然后不断的合并, 如果图是连通的. 那么肯定能合并成一个多叉树
对树做一个先序遍历, 输出结果. 递归的时候要传进去层数, 以便控制缩进
二面二面感觉面的不好, 很多问题都没回答上来.
问数组与链表的区别 寻址访问和插入删除的一种trade off
问怎么能实现一个 插入删除搜索都是o(1)的数据结构 好像hashmap可以符合 但是还问有没有其他的数据结构
做一个题 寻找数组中两个数的和 最接近指定数字. 提示可以排序
问编程语言 用过哪些 了解哪些