富途后端面经

时间点如下：6.15投递 -> 6.24一面 -> 7.4二面

一点思考

    这也是我第一次面试富途，换平时根本不会看这个公司，但是感觉面试官很傲慢，是我面了这么多个公司最有压力的一次，感觉比面试字节还要难。考了各种概率题，好几道算法题，最后面试官还问我聪不聪明，top几，实在很无语，字节都不敢这么搞。不知道这个公司的面试官为何是这个风格，最后还是挂了，估计也是不缺人吧，大厂一堆裁员的，但是还是很有收获。

    今年找工作十分不易，市场候选人很多，希望这篇面经能帮到大家～

富途一面（6.24 18:50）

1. 给两个数组，每个数组取一个数，求两数相加最小的前n对。

2. 一条路上，一分钟有车经过的概率是p，求三分钟有车经过的概率

3. 介绍一个做的比较有成就感的项目。

   IM聊天系统，长连接断开，消息如何拉取，会离线存储，然后重新连接上后会重新拉取。
   kafka有什么了解，

4. 为什么用双写？写失败了怎么办？

   重试、定时校验最新的数据，死信队列（消费失败的消息存储在特定的主题中，称为死信主题。），定时补偿，有两种，分别是正向补偿和逆向回滚补偿

5. kafka选主怎么实现的？选主过程是否可用？

   raft

6. 限流怎么实现的？

   guava RateLimiter，令牌桶算法

7. java HashMap和redis HashMap rehash怎么实现的？

8. redis为什么用渐进式rehash？

• 避免阻塞和饥饿。

富途二面（7.4 11:00）

1. 自我介绍
2. 多租户隔离，在大用户的数据量比较大时，怎么做隔离。
3. 螺旋矩阵，在矩阵中心从1开始以逆时针方向绕行，逐圈扩大，直到n行n列填满数字，请输出该n行n列正方形矩阵
4. 设计题：1分钟有60w人次的用户登陆，如何快速的判断一个用户5分钟内是否登陆过？

   感觉用redis维护一个string key就可以了，每个用户搞一个key，加个过期时间，或者过期时间作为value，没必要搞那么复杂。。。
   http://www.cppblog.com/zhgw01/archive/2009/05/11/80180.html
   开始时，保留当前时间戳，作为哈希轮的起始时间。可以搞两个HashMap，一个是时间维度的HashMap，大小为300，每秒一个桶；另外一个是用户维度的timeHashMap，大小为300w左右。

• 每次用户登录时，插入到userHashMap进行更新（value为userId,timestamp），同时如果存在的话，找到上一个时间戳（根据开始时间，得到哈希桶），把该用户从timeHashMap删除掉（取消task），重新插入（当前时间+300-开始时间，得到哈希桶，其实就是当前指针上一个位置）一条数据到timeHashMap。查询时从userHashMap看是否存在。
• 另外有个时间线程，每秒执行一次，将当前指针指向的桶上的所有用户删除掉，避免过期时间太多造成内存泄漏，类似哈希时间轮。

https://www.infoq.cn/article/erdajpj5epir65iczxzi

5. 给定n个字符串，如何找到所有以he开头的字符串，例如hello、heabc，复杂度如何

   字典树

6. 有一个苹果，两个人抛硬币，先抛者拿到正面的话，可以吃苹果，否则让另一个人抛，问先抛者吃苹果的概率，如果是m个人吃一个苹果呢，先抛者吃苹果概率多大？