蚂蚁实习一面复盘总结4.13
算法题
1、设计一个算法，求第k个最大的数；
- 直接排序求第k个
- 使用选择排序、冒泡排序、插入排序等排到第k个就返回
- 更快的方法：快排的分治法、最小堆最大堆法，当场写出来还是很难的
2、写单例模式
面试部分
1、RabbitMQ如何保证消息可靠性？
- 生产者、消费者、消息队列本身
2、RabbitMQ如何保证消息有序性？
- 出现乱序的情况：一个队列多个消费者、一个队列对应一个消费者，但预取消息prefetch>1
- 解决办法：拆成多个队列，一个队列对应一个消费者；设置prefetch=1
3、保证消息不重复消费？
- Redis去重；redis去重存在问题：
- 当消息消费出现了异常，一般是需要broker重推消息，但是这个这个时候发现redis中已经存在消息id；所以redis去重不支持重复处理；
- 如果在处理的过程中，如果redis宕机了，redis的数据没有恢复，那么redis去重失效；
- 所以redis去重一般来说只适合短时间内的大量重复请求；这种情况下不够好，所以需要使用另一种方案：幂等性；
- 利用幂等性；利用数据库键的唯一索引特性，消息重复插入报错，不再消费；
4、缓存的一致性怎么保证？
- 旁路缓存模式
- 缓存双删模式
- 分布式锁
5、缓存存在ABA问题怎么解决？
- 线程1写DB更新为A，线程2写DB更新B，此时B先更新缓存，A再更新缓存，缓存中一直存的是A（本来应该为B）
6、分布式锁原理？
- set、set nx ex 、线程标识锁、lua脚本原子性判断释放
- 使用lua脚本有什么问题吗？
- 某些真正的线上运行是禁止lua脚本的；因为安全、性能、维护等原因？可恶啊应该问问面试官到底是什么原因的。
7、redis常用数据结构？
8、跳表？
9、场景题：给一台云端的2CPU4G阿里云机器，有20亿个整数，从中找到出现次数最多的一个数据是什么？有什么办法？
参考：
经典面试问题: Top K 之 ---- 海量数据找出现次数最多或，不重复的。 - 指尖下的幽灵 - 博客园 (cnblogs.com)
如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数 - 腾讯云开发者社区-腾讯云 (tencent.com)
大数据相关题目
第一眼思路：
可以采用哈希表来统计，把这个数作为 key，把这个数出现的次数作为 value，之后再遍历哈希表哪个数出现最多的次数最多就可以了。
但是内存不足。算一下，key 和 value 都是 int 型整数，一个 int 型占用 4B 的内存，所以哈希表的一条记录需要占用 8B，最坏的情况下，这 20 亿个数都是不同的数，大概会占用 16GB 的内存。（1GB= 10^9B, 10亿=10^9）
真正解法：
通过哈希法分成8份小文件, 一份小文件就是2GB,；装入到4GB内存中，2GB是key, 2GB是value。
通过哈希函数，一般整数能按照顺序均匀的分布在不同的文件中。比如-21亿~-15亿分布在文件1，-15亿~-10亿分布在文件2…15亿~21亿分布在文件8。因为hash函数使得同一种数不可能被散列到不同的小文件上。
然后对每一个小文件用哈希表来统计其中每种出现的次数，这样我们就可以得到16个小文件中各自出现次数最多的数，还有各自的次数统计，接下来选出16个小文件各自的第一名中谁出现的次数最多即可
如果这 20 亿个数数值比较集中的话，怎么优化？
如果给的这 20 亿个数数值比较集中的话，可以先把每个数先做哈希函数映射，根据哈希函数得到的哈希值，再把他们存放到对应的文件中，如果哈希函数设计到好的话，那么这些数就会分布的比较平均。
如果给的这 40 亿个数中数值都是一样的，那么哈希表中，某个 key 的 value
存放的数值就会是 40 亿，然而 int 的最大数值是 21 亿左右，那么就会出现溢出，该怎么办？
- (把 int 改为 long 会占用更多的内存，同时拆分成更多文件，但不是最佳答案)，可以把 value 初始值赋值为 负21亿，这样，如果 value 的数值是 21 亿的话，就代表某个 key 出现了 42 亿次了。
那我如果把 40 亿增加到 80 亿呢？
以一边遍历一遍判断，如果在统计的过程中，发现某个 key 出现的次数超过了 40 亿次，那么，就不可能再有另外一个 key 出现的次数比它多了，那我直接把这个 key 返回就搞定了。
聊天环节
-
我：笔试做的很差，笔试占比重要性多大？
-
面试官：看情况，横向对比，可能题目难别人分也不高。考差了也没事，你才大三，还有机会。（婉拒了呗T_T）
-
你有什么打算吗以后？打算考研保研工作？
-
喜欢搞算法吗？ -也挺有趣的
-
关注chatGPT吗？-天天用
-
chatGPT出来以后，很多东西不一样了，简单的代码、基础工程工作容易被替代
-
算法、AI的应用、智能化的应用是未来的一个趋势
-
这些方面的应用需要更高的背景，因为现在工程技术红利时代已经过去。
-
-
所以就是叫我去深造、读研是把T_T , 真是为我考虑啊，用心良苦T_T
-
本科生和研究生投递简历比例不足 1 : 1 ，本科生简历少，连面试官都感到夸张，因为本科生基数大呀！简历却那么少。
-
本文链接：https://my.lmcjl.com/post/4798.html
4 评论