滴滴秋储开发java一面

说明暑假实习java,然后值得一提的是面试官非常好!最后还跟我探讨了一下算法的实现,然后给了我非常多的建议,说实话这对我个人提升很有帮助

八股

1. 说一下Mysql与Redis的区别

当时说的有点莽撞了,下面是对重新的补充

1. 以使用上来说: mysql是我了解得比较早的,从最开始的原生的jdbc再到使用上的druid连接池,然后再是mybatis以及说现在比较常用的mybatis-plus等orm框架redis的话,首先在使用上基本上是使用的spring的springdata其中的redistemplate,以及说stringtemplate或者说我自己封装了bitmaptemplate,然后更具体的比如说我之前尝试用redis设计一个分布式锁其中对比的一些思想好比说redisson
2. 以他们的实现上来说的话: mysql首先是多线程的,然后他其实分为了server层和存储引擎层,然后mysql是关系型数据库,再回到其中的一个存储引擎innodb,innodb的话他是支持事务的,例如说acid特性,然后另外值得一提的是mysql是最终存储在我们磁盘的也就是更具有可靠性redis的话,首先redis是kv,然后主要单线程,有些时候会用多线程,然后他是不支持像mysql那种类型的事务的,在官网中他对于自身事务的描述也说明了这一点,虽然他不支持事务但是他有丰富的数据结构来提供高性能例如zset,hash等
3. 在要细说的话: 这里就不说了,明儿更新一篇博客来讲讲这个链接在这:海山了- - 博客园 (cnblogs.com)

1. redis中的SDS是什么意思?

simple dynamic string

1. 介绍下设计模式中的责任链,以及策略模式

在第一个项目中,采用到了该责任链设计模式,例如说评论相关的内容,我是在时间维度上以及内容维度上来限制用户发放评论,然后还有结合AC自动机来实现对应的敏感词检测,这其实就是天然的责任链设计模式,然后我相对考虑多的一点是,进行了部分的测试,为了减少服务器的压力嘛,对各个阶段的处理时间进行压测,去网上爬了对应的leetcode的评论,包括一些短评论以及长评论,进行测试,最终对这个责任链的顺序进行了编排,然后值得一说的是,虽然说看起来好像是三个部分,但是实际上是只有两个filter,因为我把对应的时间维度和对应的评论内容用redis的zset来存储了,对应的member是评论的前50个字符,然后score是对应的时间戳,话说这里突然又想到一个点如果之后又需要实现新功能,在目前的zset还可以再操作(利用评论不能包含脏话的特性),然后就是另外一个项目中也是类似的流程不赘述

策略模式的话,说了一下我项目关于sql语言与其他编程语言在这里的分开操作,然后在下一层对于其他编程语言又采用了不同语言不同策略的方式,然后提了一下学校的项目oomall之中老师提到的策略模式的使用,但是呢...忘记了,就直说了,刚刚看了下,原来是我对策略模式记错了...,老师那里用到的也就是运费然后有多种算法,当时好像是算法大牛学长们搞得,然后当时记错了老师是还结合了桥接器模式,他主要完成的是把两个维度的策略选择进行了考虑,看了会忘了在哪了...,看了点课件在上限打包 • 均匀打包， • 费用最优打包这也用了策略模式,不过这不是惊艳我的地方,惊艳我的是当时的那个结合桥接器的案例,类似笛卡尔积的作用,然后我在自己的项目也使用了类似做法,不过我的更像责任链改,或者说桥接器转责任链,大差不差,我是三个维度

1. 介绍下,缓存雪崩,缓存击穿,缓存穿透

相对简单,但是后两者我记反了,问题不大,面试官说不用记这种死记硬背的

1. 知道哪些避免缓存穿透的方案吗?

首先要避免这个缓存穿透的影响,在我们nginx或者说网关层其实都应该会做对应的限流,防止说如果被攻击的话,造成的伤害过大再者说比如:bloomfilter,他具有假阳性但是不具有假阴性,也就是说我们把对应的mysql中的数据存放到这个bloomfilter中,首先不存在假阴也就是说如果我们mysql中存在的数据,那么是不会被过滤掉的,但是他具有一定的假阳性,也就是说仍然会有部分击穿存在,不过我在项目中运用到的是布谷鸟过滤器

下面是当时没有说的补充:对于这部分击穿我们可以采取说,即使不存在那么我们也可以直接给redis中返回一个-1,这个-1相比于说一个字符串在redis内存空间上的占用会少很多,然后我们服务端嘛,得到对应的-1后,可以进行对应的处理比如说封禁啦之类的

1. 你能说说布隆过滤器和布谷鸟过滤器的区别吗?

布谷鸟算得上是布隆过滤器的升级版,支持了删除操作,以及说在空间上更加压缩,bloomfilter的原理比较简单,是多个hash函数映射到不同的插槽,然后添加的时候是这样的我们我们添加值后会把不同hash映射的插槽设置为1,这里插一嘴底层为了节约空间使用的是bitmap,从这里我们也能看出bloomfilter其实已经在他使用数据结构这个方向已经相对挺极限了,然后查看是否bloomfilter中是否存在的话,是同样根据hash函数来获取到对应的插槽,然后一一查看对应的槽有没有置成1嘛,然后如果有一个没有那么就是不存在,同时我们也可以通过这个机制来发现说存在假阳性,而不存在假阴性嘛,**下面是没有说的部分:**做的复习不够充分,其实我有点忘了布谷鸟过滤器的原理(这几天应该会补),所以顺便扯了扯guava的bloomfilter与redis的区别,只记得布谷鸟也是和hash有关来着,然后可能涉及对hash出来再操作还是说凑成一个序列什么的,记不清了,所以没提,感谢面试官"不杀之恩",其实我之前中间件大实验还打算改进一下布谷鸟过滤器来着,还下了篇论文

场景题

自我检讨:面试官对我说的建议挺中肯的,我确实有点急了,几乎他说完之后我马上要回答,下次面试争取改掉这个缺点

榜单之文章浏览量排序

说的就好比csdn等等博客或者新闻网站,统计的是pv,而不是uv,然后挺好的

我说的是zset,这里要感谢一下b站,之前曾经看过b站设计的榜单系统,他用的也是zset,这让我很放心,然后就关于zset说一下

这里给大家提个醒,不要直接说zset就行,你可以展开说说,虽然你说zset面试官是懂的,但是面试官主要是要知道你懂不懂,我之前线下面的时候就这事吃过大亏

王者荣耀的好友榜怎么设计

这里也犯了面试官说的过急的问题,下次应该思考更加全面再回答

我是更具体地说了:王者可能单个英雄有区榜还有省榜等等,不过可能偏题了,现在发现,主要是王者上次玩估计也是在大一了,然后还有好友榜,然后面试官说都可以,让我随便讲一个

结果我讲着讲着就讲混了.....

我是这么说的如果是一个用户和该用户的一个英雄的话,他应该是作为我们榜单的一个单位,然后下面是我没讲到的(这里该考虑的是数据冗余以及说该不该省空间,我是直接按数据冗余的来说了)

然后我说的是还是redis的zset(没办法,孩子才疏学浅....),然后额外提了一句这个榜单的更新应该是每晚12点更新的,那么我们应该能定个定时任务之类的,同时为了减少这个计算量,例如说国榜,其实我们可以说筛出分数断层比较大,我们可以让他达到这个分数(而且这个分其实是只有少数人能达到的)后再进行一个新zset的统计

然后尴尬的事发生了,没有任何转折(当时好像突然意识到我原本说要讲的是好友榜来着...)突然聊到了好友榜....

好友其实数量基本上不多,mysql建个表,然后按照对应的分数排序一下应该也不会浪费太多时间,而且好友的话,访问量应该不大,而且根据不同用户获得的数据也不同,这如果用redis的话,得不偿失,而且这样的话,对应的空间也比较省

补充一下原本该提的(省空间玩法),统一用存zset的话,那么在聚合操作出结果是极其耗费时间的

回忆面试所学(小知识非算法)

面试官非常好,其中教会了我许多,且个人由于有那么一点社恐,所以在与人沟通的情况下,记忆力几乎比以往高出非常多,甚至达到快全记住的情况(主要是脑子会不断回放...):happy:

ON DUPLICATE KEY UPDATE

当时场景我是对于这个进行了猜测,虽然我不太懂mysql的所但是还是猜测了一下,首先是由于duplicate猜测是主从复制之类的update猜测是读写锁(由for update猜测得出)

然后面试官说是当我们有一个联合唯一索引作为主键时,然后这个语法的作用是如果这个联合索引存在那么他会更新对应的其他行的记录(注:这里应该是主键之外的,毕竟主键没有必要更新),如果没有的话呢,那么就是插入的效果了

事后学习补充

待我后来补充,看到别人说可能有bug,之后看我博客

算法

算法问到的是LRU,虽然我了解过,不过一看两眼一黑,不过万幸的是不是LFU,如果LFU那就真得从0造起了

当时面试官说不用考虑时间复杂度和空间复杂度

然后我就直接写了暴力了

写完后让我说一下思路(因为代码没写完,手速过慢),分析一下时间复杂度,空间复杂度

用了hashmap,和list(甚至用的是arraylist,当时面试官提了一嘴,不过提的好,并且极其有深度,他说lru当时是面向内存比较紧缺的一个情况,用arraylist应该是不行的,他说arraylist的话,底层是数组,要么是删除后,整体左移,要么就是不左移直接移动头指针),然后他提示了我用linkedlist(这里真的是很有深度的面谈了!,我以往一直认为顶多java就在线程池中使用linkedlist,没想到在这也有细节)

然后我在之中没有使用双向链表而是使用单链表遍历,问问我说有没有办法提升,我说了使用priorityQueue,然后他说这个应该顶多也是O(nlogn),然后提醒了我说双向链表(在这之中我也突然说了map中可以存list中的索引),然后他说也行,然后另外能做的是比如说map存对应的节点,然后还告诉我说可以了解一下LinkedHashMap只需要重写一下方法就行,很少代码

最后再感谢一下面试官包容了我在这之中大量的答非所问,以及过度紧张导致的扩展的过多的现象,争取下次把这些毛病都改了!