笔试
1 | 5.14 20:00 华泰证券 |
面试
1 | 6.6 14:00 华泰一面 |
24届秋招
1.美团
8.12笔试
- 1.给一个数组和x、y，判断值为x、y的成员是否相邻
- AC
- 2.给一个数组表示从i走到i+1的距离，末尾下一个点是起点，求从x走到y的最短距离
- AC，分情况模拟即可，用前缀数组降低复杂度
- 3.给一个矩阵，只能切一刀，横着和竖着都可以，求最后分割出来的两个子矩阵成员和的差值最小
- AC，行压缩和列压缩后分别模拟即可
- 4.给一个字符串，你可以任意将其转成矩阵x*y的形式，转成矩阵后相邻的相同字符可以连通，求最少连通块的数量
- 50%，枚举x和y情况
- 为什么只过50%，是因为只考虑了x > y的情况！！！！！ 下一次一定要记住如果没超时，就不要去瞎剪枝，可能会有遗漏
- 5.给树染色，若相邻2个节点都是白色且val之积为完全平方数，则可以把这两个节点染成红色，求最多能染成红色的节点数
- 10%，dfs+回溯只过10
- 正确解法是树形dp
8.19笔试
- 1.有一个m的循环，求n号数字是哪个元素
- AC，/m后求余数即可
- 2.给一个数组，可以在两个数字间加一个运算符，要求乘号只能有一个，其他全为加号，求最大的结果
- AC，遍历即可
- 3.
- AC
- 4.
- AC
- 5.
- 骗66.6%
9.4 优选一面(仓储、订单方向java)
- 自我介绍
- 每年都有去实习，为什么实习这么多
- 介绍一下你觉得对你提升最大、有挑战的项目
- 本科和研究生专业不一样，为什么这么选择
- 算法题：给一个字符串，找这个字符串中的最长不含重复字符的子串
- OSI七层模型
- TCP/IP靠什么保证可靠性
- MySQL的引擎有哪几种，innodb比起myISAM好在哪，innodb的索引数据结构是什么
- 进程的状态有哪些
- 就绪态、运行态、阻塞态
- 还有挂起和睡眠，阻塞态不耗CPU但是耗内存，挂起和睡眠不耗CPU也不耗内存
- 挂起要去主动唤醒，睡眠是到时间自动唤醒，阻塞不需要唤醒资源释放了自动去执行
- 进程共有资源有哪些、通信方式有几种，进程切换怎么进行
- 进程阻塞是怎么发生的，资源释放了具体怎么去唤醒阻塞的进程的
- 检测到资源可用，系统会检查等待队列里的进程
- 根据优先级策略决定哪个进程获得资源
- 虚拟内存具体怎么映射到物理内存
- 是CPU里一个名叫MMU的硬件通过放在主存里的查询表来翻译成物理地址
- linux你用过的命令有哪些
2.京东
8.12笔试
- 20道选择题，3道算法(60分)
- 1.给一个小写字母组成的字符串，你可以有两种操作：1.把头字符放到尾部，2.把一个字符换成任意字符，求把这个字符串变成回文串的最小操作数
- AC，枚举以i位置为回文中心点，可以直接计算出1操作的次数，然后两边扩展就得到2操作的次数
- 2.给一个数组，每次你可以进行两种操作：1.把数组末尾两个数加起来，然后结果取个位数放进数组。2.把数组末尾两个数承起来，然后结果取个位数放进数组，求最后数组只剩下一个数时，这个数个位数为0 1 …. 9的方案数
- 3%，二维dp，当前个位数只取决于dp[i-1]状态的个位数情况和自身值nums[i]的计算结果
- 没时间调了，最后因为没取余只过了3%，应该是能AC的
- 3.给一个矩阵，为1表示该位置有棋子，求四个棋子能围成一个正方形的方案数
- 20%，模拟枚举最左上的棋子去判断只过了20，
- 正确解法是多考虑其他正方形的情况
3.大疆
8.13笔试
- 20道选择题，2道算法
- 1.加油站经典问题，给一个加油站列表和每个站可以加的油数及开往下一个站要花费的油数，求从哪个点出发可以绕一圈
- AC
- 模拟+贪心算法，如果能从i最多走到j的话，那么下次直接从j开始往下走就行了
- 2.给n个充电桩，每个充电桩充单位电花费的时间不一样，给充电桩i跑到充电桩j需要耗费的电，电量有最大限制，求从s充电桩跑到t充电桩需要花费的最少时间
- 骗20%，直接返回测试用例答案骗20
4.米哈游
8.13笔试
- 15道单项，15道多项，3道算法
- 1.给一个左右互通的矩阵，然后给s1，s2，s3的坐标，求从s1到s2再到s3的最短路程是多少
- AC，简单模拟+考虑左右边界互通即可
- 2.给一个树，你可以进行任意次操作：在一个叶子节点下新增一个叶子节点，操作完成后求与根节点距离为k以内的节点数
- AC，先加上所有距离为k的节点数，在加上所有叶子节点的k - distance
- 3.给一个概率p，抽到常驻五星的概率为p/2，抽到限定五星的概率为p/2，前89抽都没抽中五星的话下一抽必定抽中五星，上一个抽中五星是常驻五星的话，下一个五星必定是限定五星，求抽中限定五星的抽卡期望次数
- 0%
5.阿里灵犀
8.19笔试
- 20道选择题，4道算法
- 1.
- AC
- 2.
- AC
- 3.
- AC
- 4.给一个数字n，求n条直线的交点数有多少中情况，不允许出现三条直线交于1点的情况
- AC
9.04一面
- 游戏经历和游戏机制背后的设计思想
- vector、list什么情况下迭代器会失效
- 红黑树的概念和特点，怎么使用
- C++的内存对齐
- 智能指针
- 移动语义
- 虚保护
- 堆排序、快速排序
- 快速排序是稳定的么，什么是排序的稳定性
- 常见的算法中只有冒泡、插入、归并是稳定的
- 排序算法的稳定性通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同
6.网易雷火
8.20笔试
- 1.
- AC
- 2.卡牌组合
- AC
- 3.队伍匹配
- 93.3%，超时
- 4.水池链接
- 骗3.3%
11.13一面
- 1.给前序遍历和中序遍历，求后序遍历
- 2.ICMP协议是在哪一层
- 网络层，ICMP协议是IP网络的核心协议所以和IP协议在同一层，用来传输错误和操作信息
- 3.青蛙每次可以跳1层或2层，求跳n层的方案数
- 4.盒子里有绿球5个、白球5个、红球5个，抽三次，每次抽完不放回，求正好每个颜色各一个的概率
- ans = 5/15 * 5/14 * 5/13 * 6
11.14二面
7.OPPO
8.20 笔试
- 1.循环数组，找f = (nums[i] + nums[j]) * abs(i - j)的最大值
- AC
- 2.给一个字符串，求满足长度为4，1、4是元音，2、3不是元音的回文子序列数量
- 暴力10%，应该用二维dp做
- 3.给一个数组和一个k，每次可以对和乘2或者/2，求最后的数组和的因子数最接近k时，操作1和操作2的次数
- 骗10
9.18 一面
- 如果让你设计一个RPC框架里的client端，要考虑什么问题
- 一个秒杀系统需要考虑哪些问题
- Innodb的MVCC机制
- 聚簇索引和非聚簇索引
- JVM由哪几部分组成
- JAVA的垃圾回收是怎么样的
8.bilibili
8.20 笔试
- 1.给一个含video_id、upload_id、video_duration的up主上传视频表，求平均上传视频时长>300秒的up主上传视频的video_id
- AC
- 2.给两个字符串，求把他俩变成相同字符串的最小ACII码开销是多少
- AC，动态规划求出相同字符串，最后再用原始ACII码之和减去相同字符串的ACII码之和
- 3.给一颗二叉树，只有相邻且值相同的节点才能连接，求最长路径
- AC，dfs()
9.高德
8.31 一面
- 自我介绍
- 讲一下字节的全链路
- 讲一下携程的全链路
- GMP模型
- 除了使用锁，go语言里保证并发安全还能怎么写
- 管道channel、waitgroup、sync.map、原子操作
- 讲一下git rebase(说是加分项)
- 将开发分支的基准换成最新的线上分支，再去MR，免得MR出现一堆diff
- 场景题：1G内存的机器，有1000G的日志文件(每一条有ip属性)，怎么得到出现次数前10的ip
- hash分桶法，先切片按ip哈希分成1000个桶，每个桶里计算前10的ip，最后再汇总得到总前10的ip
- 场景题：go引包会出现循环依赖问题，怎么判断，具体怎么实现
- dfs，先随机从某节点出发往下走，并记录走过的节点，走到头回到上一节点走下一条路，如果走到了重复的点就说明有环
- 部门介绍高德是阿里系Go最多的，很多SDK都是高德开发的，也说出来就是Go很正确
9.06 二面
- 自我介绍
- go的面向对象怎么实现
- 继承：通过组合的形式来模拟继承，例如A类里面包含了B类成员
- 封装：通过首字母大小写来实现，包内、外访问权限的控制
- 多态：使用多个接口来实现多态，定义多个类实现同一个接口，那么就可以在不同类型对象上调用相同名称的方法
- 有的结构体里面内嵌了一个interface叫a，为什么这样做
- 作用是把这个a作为匿名成员，实现的场景是：
- 该结构体没有实现a内所有的方法，按理说是不能声明该结构体为a的，但是如果内嵌了，那么就可以声明了
- 只是在运行中去调用这个没有实现方法时才会报错
- 作用是把这个a作为匿名成员，实现的场景是：
- GMP模型
- 有缓冲的channel和无缓冲的channel区别
- select会把所有case计算出来么
- case的表达式会在select执行之初就计算出来
- 如果多个满足，那么就以伪随机算法选取分支执行
- go内部根据满足分支的数量生成一个随机数，然后用这个随机数来选择分支
- 如果一个都没满足且没有default分支，那么select就会阻塞，直到其中某一分支满足
- 什么情况下切片的len和cap相等
- make只指定了len，会默认cap=len
- make指定了len和cap相同
- append后切片正好满了、直接截取某个数组的一部分时、用字面量定义时，字面量指的是直接列出来成员有哪些但是不写长度例如[]int{1,2}
- 函数、切片、字典、通道能做map的key么
- 能做map的key的类型需要满足可比较这个条件
- 只有通道channel可以做map的key，因为只有channel是可比较的
- ps：channel是引用类型实质上是一个指针，所以比较其实比的是内存地址
- 条件变量的wait方法具体做什么
- 1.把当前协程放到当前条件变量的通知队列里
- 2.解锁该条件变量绑定的互斥锁
- 3.让当前协程阻塞
- 4.如果有通知到来就唤醒该协程继续执行，并重新锁定该条件变量绑定的互斥锁
- 因此在调用wait()之前，需要先锁定这个条件变量的互斥锁
- 别名类型和源类型的关系
- type MyString = string，MyString是string的别名类型，他俩是完全相同的，只是名字不一样
- type MyString string，这种又叫类型定义，string是MyString的潜在类型，潜在类型指的是本质是什么类型，他俩属于不同类型不能比较、互相赋值，但是可以强转
- sync.Pool是一个对象池
- 本地池列表的长度与调度器P的数量相同
- 并且如果已经开始使用，就不应该再被复制
9.15 三面
- 机票的列表逻辑，用的哪个框架，RPC调用呢
- java的开源源码看过哪些
- GMP模型
- redis的传输协议，你觉得最大的问题在哪
- 不支持压缩：其实可以压缩后再传输，收到后再用特定算法解压
- 文本传输开销大：可以采用二进制编码
- 没有加密措施：可以在协议里加入加密算法
- 支持数据类型过少：可以新增支持浮点数、日期时间等
- http2.0和http1.1有什么区别，服务端主动推送具体是怎么做的，1.1为什么不可以？
- 服务器推送允许服务器预先发送客户端尚未明确请求的资源。例如，当客户端请求 HTML 页面时，服务器可能知道客户端很快会需要页面中引用的 CSS 文件，因此可以立即将其推送到客户端，而不需要等待客户端明确请求它
- HTTP/1.1 无法进行服务器推送，主要是因为它是基于传统的请求/响应模型设计的，而这个模型中服务器只在响应客户端请求时发送数据
9.19 HR面
- 你觉得自己的优势和不足在哪
- 自律、自学能力强、不玻璃心
- 不足在于实践经验少
- 不玻璃心这一点具体是什么事情
- 业余有什么兴趣爱好
- 你觉得自己性格是什么样的
- 手上现在有哪些offer
- 考虑的城市是哪些
- 未来的职业规划是怎么样的
10.腾讯
9.02 一面(国际发行平台-账号相关)
- 算法题：给一个数字字符串和一个n，实现除法
- 题不难，20分钟，主要考察：1.异常值处理 2.负数处理 3.n=0处理
- 全连接和半连接
- server收到第一次握手的SYN，把这个socket放进半连接队列里
- server收到第三次握手的ACK，把这个socket从半连接放到全连接队列里去等待accept
- 这个时候如果全连接队列满了，那么就会丢弃这个第三次握手的ACK，并向client重发第二次握手SYN+ACK
- TCP三次握手，三次的报文具体是什么，二次会怎么样
- SYN、SYN+ACK、ACK。两次会产生历史连接
- TCP四次挥手，close_wait、time_wait，2MSL，为什么是2MSL，这个怎么修改
- MSL意味最大报文生存时间2分钟，默认2MSL是为了防止第四次挥手c->s的ack包丢失导致服务端未进行关闭，2MSL = 判断客户端第四次挥手丢失(MSL) + 服务端重传第三次挥手(MSL)
- 修改2MSL，widows直接修改注册表，linux要去内核修改宏定义
- 出现大量的time_wait状态，可能是什么原因
- 通信采用的是短连接
- 大量地建立连接和关闭连接
- 短连接和长连接
- 短连接是传一次数据建一次TCP连接，长连接是一个TCP连接承担多次传数据任务
- 短连接需要频繁建立、关闭连接，有资源浪费。长连接需要进行连接管理，空闲的长连接也会导致资源浪费
- 滑动窗口，发送端怎么知道接受端的接受能力的呢，在哪个包里面，是单独的一个包么，发送窗口为0怎么样
- 报文里有接受窗口大小，表示未被ack确认的数据最大可为多少
- 例：接受窗口大小为10，第一次发送了6，第二次最多只能发4，然后此时收到了确认6的ack，那么第三次就又可以发6
- 这个接受窗口大小是在上一次接收端发的包里面附带过来的
- 报文里有接受窗口大小，表示未被ack确认的数据最大可为多少
- 拥塞控制，什么时候算拥塞
- 维护一个慢开始门限，小于这个门限采用慢开始(*2)，大于这个门限采用拥塞避免(+1)
- 判断拥塞有两种：1.超过了超时重传的时间还没收到ack 2.连续收到了3个重复的ack
- 快速恢复：发生拥塞后将发送窗口和慢开始门限减半，并执行拥塞避免
- 大端小端
- 大端是高地址存低字节；小端是低地址存低字节，反人类
- 大端优势是固定第1位为符号位，便于判正负和人类阅读；小端优势是强制类型转换不需要调节字节内容
- 判断：新建一个int i = 3，然后把它强转成char*再判断是不是3，如果不是3说明是大端，因为大端的第1位是用来表示符号的
- 网络字节序
- 采用大端序，是为了避免不同CPU采用大小端不一致而约定的TCP/IP数据格式
- 字节对齐
- 网卡收到一个包，这个包处理的过程(需要讲怎么送进协议栈和协议栈OSI的处理)
- 硬中断：调用网卡驱动注册的硬中断函数
- 软中断：网卡驱动注册的poll函数，并把包发送到网络协议栈处理
- IP->TCP/UDP->socket
- 进程、线程、协程
- 硬中断和软中断
- 中断是指运行过程中，某个时刻需要内核操作，这时候需要把当前程序暂停保存，然后转去内核态执行特定操作，处理完成后再回到之前状态
- 硬中断是CPU硬件实现的中断
- 软中断是软件模仿硬中断去实现的中断
- epoll的两种模式
- 堆和栈
- static声明的局部变量在栈上还是堆上，讲一下static成员和static函数
- 一致性哈希，和普通哈希区别在哪
- 口述堆排序和快速排序的运行过程
- 场景题：给1万亿个整数，一台小内存机器，怎么找出前100个最小的数字，复杂度多少，追问有没有更快一点的方法
- 前100个建小根堆，堆顶和第101个比较，如果堆顶大于当前遍历数，压出堆顶，压入当前树，并重新调整堆，时间复杂度nlogk
- 说了快速选择，把前100个排满就不继续进行下去
9.05 二面(国际发行平台-账号相关)
- 场景题：给一个字符串”level > 100 or (ip > c1 and ip < c2)”和一个玩家的结构体，写一个函数判断该玩家是否符合该表达式
- 类似“简易计算器”的解决思路，遍历到or、and这种运算符的时候，做一个分割计算已保存的状态和后面的状态再比较，遍历到()的时候递归调用
- 场景题：有一本英文书籍，怎么压缩它来存储？
- 1.把常用的单词建一个字典，用字典的索引来表示该单词
- 2.使用变长编码，例如霍夫曼编码，使得频率高的单词变成较短编码，频率低的单词变成较长编码
- 3.使用压缩算法，例如LZ77去识别字符串中的重复模式和冗余数据，将其替换成更短的表达形式
- 如果某个进程发生了内存占用太大、CPU占用大，用什么工具去找问题，我想问的是linux下怎么去调试代码定位问题，除了top呢
- 首先通过任务管理器、top命令等去查找是哪个进程出现问题
- 其次日志文件检查是否有错误信息
- 最后在代码里断点调试找到占用资源过多的函数
- gdb具体怎么调试
- 启动gdb并在里面加载可执行文件
- 然后加断点，并一行一行往下执行
- 过程中用info proc和backtrace分别查看资源占用情况和函数调用栈情况
- 指针占多少位，32位机器和64位机器呢？
- (x86)32位机器4字节，(x64)64位机器8字节
- http协议里面的内容有什么，怎么知道http包的长度
- line-header-body
- 小点的文件用content-lenth字段直接知道，单位是8位字节的数量
- 大点的文件用Transfer-Encoding:chunked表示用分块传输，采用约定好的协议，客户端收到了会进行组装再读取
- 首部行是什么格式
- 键值对
- 怎么实现记录玩家的登录状态的
- cookie和token，cookie存在首部行里面
- https具体怎么握手的
- https怎么认定服务端是可信的，你说追溯到根CA来判断，但是一次https去访问这么多地址，不是会很慢吗？
- 根CA证书是内置在操作系统里面的，所以根据服务器证书去请求CA拿到中间证书就可以用本地的根CA证书去判断了
- 中间CA一般是机构在颁发服务器证书的时候一起给服务器的，是静态存储在服务器上的，在https请求的时候会把服务器证书和中间CA一起发过去，用户只需要用内置的根CA去验中间CA，然后中间CA再去验服务器证书
- 如何保证CA证书不被篡改
- 验证签名，任何对证书的修改都会导致签名失效
- 根CA证书是内置在操作系统里面的，所以根据服务器证书去请求CA拿到中间证书就可以用本地的根CA证书去判断了
- 非对称加密为什么比对称加密开销大
- 1.非对称加密密钥长度比较长，需要解密加密更多计算资源
- 2.非对称加密计算复杂度高，算法实现通常涉及大数分解、离散对数等；而对称加密算法通常是基于位运算和异或操作等简单运算
- https怎么减少开销
- 非对称加密算法从RSA换成ECD，证书从RSA换成ECD
- 会话重用
9.19 一面(腾讯广告-数据平台)
- 进程的状态有哪些，它们是怎么切换的
- 硬连接和软连接有什么区别
- OSI五层模型，TCP三次握手、四次挥手
- 网络接口层、传输层、网络层、数据链路层、物理层
- 三次挥手什么情形下会出现
- 两方同时决定要关闭连接时，同时向对方发了FIN
- 这样的话挥手就变成了
- c->s:FIN
- s->c:FIN+ACK
- c->s:ACK
- TCP和UDP有什么区别，UDP有校验和吗
- UDP也存在校验和机制
- 粘包怎么处理，TCP为什么会出现粘包，UDP有粘包么
- 粘包本质上是因为网络延迟导致接收方一次性接受到多个包导致的
- TCP是面向流的协议，不保存包的边界，所以可能会导致粘包
- 而UDP是面向消息的协议，保存了消息的边界，所以不存在粘包
- 说一下TCP的拥塞控制
- Mysql有哪几种引擎，各有什么区别，他们的锁都各自是哪种
- MyISAM：读速度快、写速度慢，表级锁(Mysql5.5版本之前默认引擎)
- Memory：内存型，服务器崩溃重启会丢数据，表级锁
- Innodb：支持ACID事务、MVCC，支持表级锁、行级锁和意向锁
- 意向锁指的是允许事务显示对指定行的锁定意图，如果其他事务要对行上锁的话要先去获取意向锁，表级锁要上的话要去检测意向锁，这可能会导致表级锁延迟
- Redis为什么快，跟它底层的数据结构有关系么
- 讲一下跳表，它的查询时间复杂度是多少
- C和C++的栈帧过程
- 把返回地址推到栈上，CPU指针指向新调用函数的入口
- 函数开始创建新栈帧
- 函数的参数通过寄存器或直接推送到栈，来传递
- 执行完函数体后，通过移动栈指针来销毁栈帧
- C++的多态怎么实现，虚函数具体怎么起作用
- 场景题：给一堆相同的绳子，密度不均匀，已知一根绳子烧完是1小时，如何得到15分钟烧完的绳子
- a绳两头烧，b绳一头烧，a绳烧完后b绳剩余长度就是30分钟，如此反复就可得到15分钟的绳子
- 场景题：有10000瓶液体，和10只小白鼠，测哪瓶是毒药
- 算法题：给一个数组，求最大的连续子数组和
11.小米
笔试9.02
- 19道单选，6道多选，2道算法25分
- 1.给一个目标频段target和一组频段:loss的数据，求与目标频段相差距离最小的频段的loss
- 67%，遍历即可，思路没问题可能处理输入卡了
- 2.给一组任务，每个任务有最低执行电量和运行总共消耗电量，求执行完所有任务需要的起始电量
- 67%
- 思路写错了，不应该是按最低执行电量升序、耗电量降序排序，而是应该按最低执行电量-耗电量的结果升序、最低执行电量降序来排序，因为门槛和消耗固定，那么完成这个任务之后的电量也就相当于固定！！！
12.微众银行
笔试9.03
- 20道单多选，3道算法60分
- 1.给一个糖果数组，切一刀要求左半段没有重复元素，求最长左半段
- AC
- 2.给一个橡皮泥堆数组，可以给任意堆加橡皮泥，要求最后每个堆的大小都是独特的
- AC，先排序然后从1开始遍历，如果当前堆大小<=上一堆大小，就要把当前堆变成上一堆大小+1，然后res += nums[i-1] - nums[i] + 1;
- 3.给一个数组和u、v，求这个数组里面有多少个平均值为u/v的子数组
- AC，前缀和，pre[i]是i前v个数的和，每次遍历到i都会去枚举k，k表示从i往前数多少个v，即把v视作粒度来枚举
1
2
3
4
5
6
7
8
9
10for(int i = v -1; i < n; i++){
int sum = 0;
int k = 0;
while(i - k*v >= v - 1){
sum += pre[i - k * v];
k++;
if(sum == u * k) res++;
}
}
return res;
- AC，前缀和，pre[i]是i前v个数的和，每次遍历到i都会去枚举k，k表示从i往前数多少个v，即把v视作粒度来枚举
13.唯品会
笔试AK
9.5一面(内部开发工具java)
- 自我介绍
- 你认为哪一个项目比较困难/成就感/对你帮助比较大
- java和go有什么区别
- Redis的String底层是什么，和普通的字符串数组实现有什么区别
- MySQL主从同步，如果出现主从数据不一致可能是什么原因，怎么解决
- 事务里面使用了产生随机结果的SQL语句，例如使用了RAND()、NOW()等函数，导致从库重新执行binlog时产生了不一样的结果
- 如果事务在从库binlog执行完后再提交，可不可以实现一致性
- 未来的职业规划
9.13 二面(内部开发工具java)
- 问了一下项目
9.20 HR面
14.小黑盒
笔试AK
9.6 一面(游戏库、战绩、社区)
- redis分布式锁
- 用setnx命令去获取锁，建立一个key为锁名，val为随机数的键值对
- setnx表示只有当这个key不存在时才创建成功
- 获取成功后，再进行读写操作
- 注意这个锁绑定的资源是由你自己代码决定的，例如规定访问商品数量，必须获取lock1，那么这个lock1就相当于绑定了商品数量
- 读写完成后，使用lua脚本去释放该锁(因为在redis里lua脚本默认是原子性的)
- 用setnx命令去获取锁，建立一个key为锁名，val为随机数的键值对
- 内存回收，为什么设计一套这么复杂的内存回收机制
- channel
- gmp模型
- 签到发奖励中消息队列的作用
- 异步：将大流量分配到后面时间去处理，也使得前端请求不用等待数据层处理结果
- 削峰：减小最大峰值
- 解耦：依赖于这个消息的下游各部门可以各自独立消费，不用耦合在一起
9.8 二面
- 算法题：三数之和
- 算法题：给n个球刷n种颜色，有几种刷法？如果不考虑顺序呢
- zset查某个数的排名时，底层跳表是怎么运行的
- 从上往下查找的时候，维护一个计数器用来存每层跳过的节点数之和
- 最后在底层找到目标值时，这个计数器的值就是排名
9.12 HR面
- 早九晚七，开发一周有三天九点下班
15.喜马拉雅
笔试AK
9.8 一面(广告)
- 场景题：有三扇门，其中一扇门背后有奖品，某次选择中，你先选了一扇门，然后主持人打开了另一扇门发现是空的，请问这时候你是维持当前选择，还是选另一扇没打开的门中奖概率更高？
- 延迟双删具体怎么做
- 死锁怎么解决，介绍一下银行家算法
- 破坏死锁的条件之一：互斥、非抢占式、持有且请求、循环等待
- 银行家算法：
- 进程声明自己的最大资源
- 试分配看是否能够成功
- 安全性检查看是否能够成功
- 分配资源运行
16.阿里钉钉
9.8 一面
- 场景题：1000瓶药水，其中一瓶有毒，喝到有毒的24小时之后会死，请问一天之内试出有毒的药水需要几只小白鼠
- 二进制编号
- 场景题：有一个50个球的盒子，每次可以拿1-7个球，你先手拿，怎样保证自己能拿到最后一个球
- 自己拿完之后保证盒子里的球数为8的倍数即可，这样无论对手拿几个，最后都能自己胜利
- 进程和线程区别，切换开销
- C++的智能指针，shared_ptr怎么实现
- 维护一个计数器
- 在复制构造函数里计数器++
- 在析构函数里计数器–，一旦计数器==0就把当前指针删除
- C++中堆和栈的区别，哪个快
- 堆有复杂的内存分配策略，而栈的内存分配只设计栈指针的移动
- 栈上的连续数据大概率是存在连续的物理地址上，CPU硬件更容易命中缓存
- 从输入url开始的全过程
- 四次挥手具体怎么挥，time_wait状态过多会怎么样，怎么解决这个问题
- 开发中内存泄露怎么定位
- 先使用任务管理器、top命令等查看是哪个进程占用内存过多
- 调试该进程的代码，查看是哪个函数占用内存
- 算法题：顺时针打印螺旋矩阵
9.14 二面
- C++的协程
- gdb调试具体命令，一个运行中的linux程序怎么去调试(不能重新运行)
- linux怎么dump一个线程
17.蔚来
笔试AK
9.9 一面
- redis的数据类型有哪些
- mysql的隔离级别有哪些，可重复读+MVCC具体怎么解决幻读
- undolog+next key lock
- 浏览器输入一个url的全链路是什么
9.9 二面
- 分流的技术方案
- 负载均衡：硬件、软件、DNS
- 应用层分流：例如不同uid打到不同后端服务器
- 数据库分片、主从复制
- 设置缓存层
- 做环比监控的话，怎么存数据
- 定时任务从1天一次改成1小时一次怎么改
- http协议是什么
- 算法题：实现一个substr
- 8-9点下班，java互联网技术栈，节奏慢，和产品、用户沟通
- base、薪资都可以和hr聊
9.21 HR面
19.华为
9.21 一面
- 算法题：删除链表的倒数第k个节点
9.21 二面
- 算法题：给一个头尾相连的距离数组和两个下标，求从下标1走到下标2的最短距离
9.21 主管面
- 竞赛经历
- 论文工作进展，论文一个人完成还是有合作
- 家庭情况
- 部门业务：芯片和软件结合，进来后会根据个人意向分配岗位
20.深信服
9.23 一面
- 算法：两个有序数组，找中位数
- 二叉查找+分治思想
- 先各自找出自己的中位数，然后再根据这2个中位数去判断完整的中位数应该落在被分割的4个区域中的哪两个区域，再重复执行，直到找到完整的中位数
- go的singleflight库
- 底层是map + sync.waitgroup，原理是：
- 如果调用map中不存在的call，那么就加锁执行，执行完成后释放done()
- 如果调用map存在的call，那么就wait()，直到释放后就直接取map里的结果即可
- 适用场景是某个用户并发大量地访问redis里不存在的key，导致缓存击穿大请求直接访问到db上，使用这个库就可以保证击穿只访问db层一次
- 底层是map + sync.waitgroup，原理是：
9.23 二面
9.23 HR面
9.24 offercall
- 18*15-18，包三餐
- 一周2天6.30下班，3天8.30下班，每月固定第一个周六上半天班
10.13 已拒
21.字节跳动
9.24 笔试
- 1.给一个01字符串，可以对0、1分别染色，但是如果这个0和1相邻、或者这个1和0相邻就不能染色
- AC，设两个dp数组表示是否给第i位染色
- 2.每次询问推荐内存占用最大的视频，然后求愉悦度之和
- AC，按内存占用和愉悦度排序，然后二分查找找推荐哪个视频，再更新数组
- 3.算经过房子的金额
- AC，用前缀和计算经过每个房屋的次数，然后比较 pre[i]*b[i] 和 a[i] 的大小，贪心取小的即可
- 3.给一个字符串表示指令，求机器人回到原点的方案数
- AC，分成LR、UD、LRUD四种情况，然后组合计数
- LR就是C(1,n)\C(1,m) + C(2,n)*C(2,m)
- AC，分成LR、UD、LRUD四种情况，然后组合计数
10.27 一面
11.1 二面
- redis协议是什么
- 给5张扑克牌，判断是不是同花顺
- 不让用库函数，快排没调出来！！
- 快排一定要先从右开始找，再从左开始找
- 使用swap()的时候一定要注意是交换数组里的成员，千万不要拿局部变量去交换！！！！！
- 不让用库函数，快排没调出来！！
21.滴滴
9.24 笔试
9.26一面
- 算法题：手撕LRU
- go的调度模型
- go的内存模型，分几种对象
9.26二面
- 算法题：快速排序及优化
- 场景题：怎么对一个超出内存的大文件数据进行排序
- 讲了使用外存来进行归并排序
9.26三面
算法题：给一个{ip起始地址，ip终止地址，状态名}数组和一个很大的ip日志，求每一条ip日志的状态
22.得物
8.23笔试
AK
8.27一面
10.14二面
- 索引失效的情形
- redis做缓存组件怎么保证和db层的一致性
- go mod的常见命令有哪些
- go mod init：把当前目录初始化为一个新模块，创建go.mod文件
- go mod tidy：删掉不再依赖的模块
- go mod download：下载go.mod里的依赖到本地
- go get的是模块还是包，mod文件里required的是模块还是包，包和模块有什么区别
- 包是在同一目录下的go文件
- 模块是一个包的集合，在go.mod文件里声明
- go get xx的这个xx如果是模块名那么拉下来的就是模块，如果xx是模块名/包名，那么拉下来的就是这个模块里的特定包
10.22三面
- go前沿的新特性主要集中在改良以下领域
- 模块
- GC
- 错误处理
- 并发模型
- 灰度流量为什么不由你们这边来做，你不可以修改么
23.西山居
10.14笔试
- 1.给一组会议开始和结束时间，求最少需要几个会议室
- 优先队列，AC
- 2.象棋马每次从(0,0)出发，只能按照马走日的策略走下一步，求走到目标坐标的最少步数
- bfs+队列模拟，83%超时
- 3.给一个敌人体力值数组，如果你的体力>=某个敌人，那么你可以击败他，然后你的体力清零但是每日恢复体力+1，请问最优策略下几天可以击败所有敌人
- 二分查找+贪心，90%
- 每次循环都二分查找最大能击败的敌人，并且还要与第二天击败敌人浪费的体力值比较，如果休息一天能浪费更少体力值那么就先休息
24届提前批
1.华泰证券
笔试5.14
- 单选题25道50分+多选5道20分+3道算法30分
- 1.输入一个数字，将其翻转
- AC，签到题
- 2.输入一个01组成的字符串，首尾是连着的，初始所有字符都是白色的，你可以把一段连续范围内字符染成红色，要求最后红色的0和1数量分别等于白色的0和1
- 58.70%，滑动窗口暴力超时
- 3.给一个数组和k，任意选一些数字，使其之和为k的倍数，求这个数字之和的最大值
- 骗18.08%
- 正确做法：二维dp
- dp[i][j]表示从前i个数中选出若干数的和 % k的余数为j的最大和，则dp[i][j] = max(dp[i-1][j] , dp[i-1][(j-a[i]%k+k) % k]) + a[i]
6.6 一面
- 说一说C++你自己常用的数据结构
- vector、stack、queue的底层怎么实现
- vector是动态数组，底层通过空间不够时去动态扩容实现
- stack和queue的底层其实都是deque，分别进行了一些包装限制，deque的底层是数组+多个等长的连续空间，数组里存的是这些连续空间的指针
- map和unordered_map的区别和底层，set的底层，它怎样保持唯一性
- map是红黑树
- unordered_map是底层是hash_map，也就是vector数组+链表，数组里存的是链表的首地址
- set也是红黑树
- 使用过linux下调试C++么，用gdb
- C++的网络编程用的什么函数
- listen、bind、accept
- C++和go的区别是什么
- 他们两种语言底层执行的时候，都是编译成二进制机器码，因此效率相比使用虚拟机的Java和python快很多
- 但是其实golang有一个runtime包，这个包可以理解为go的运行环境，作用上和JVM差不多但是是以包的方式提供的，所以虽然不会有像JVM那样大的开销，但是比起C++而言还是有一定程度的效率损失
- 但Go具有强大的协程设计，它的GMP模型更利于高并发的场景，C++理论上也能实现但是C++的代码维护困难、可解释性不高，更常用来写一些底层的引擎、内核
- go是用什么底层结构来实现高并发的，讲一讲GMP模型和channel
- GMP模型，G代表的是协程，M代表线程，P是送料器
- 拥有一个全局队列和数个本地队列，本地队列处理完毕就去全局队列或者隔壁本地队列里拿协程来处理
- 协程可以看作是轻量级线程，线程之间的切换执行会涉及到CPU的切换，而操作CPU要进入内核态开销极大(保留上下文、恢复现场等)，换成协程后就可以降低这些开销
- 切换内核态开销大也是IO速度受制约的主要原因，但是无法避免，因为读文件、关文件这两步都要进入内核态
- 读文件有两次切换内核态：- 正常运行(用户态)->读文件(内核态)->数据放到内存里(用户态)->关闭文件(内核态)
- 手撕队列的实现
6.7 二面
- 深挖字节和赛诚的项目
6.16 主管面
- 为什么选择华泰
- 问有过互联网为什么还投华泰，项目也需要加班、也有末位淘汰能接受么
- 南京和上海同薪考虑过么，为什么想来上海
- 对华泰有什么了解，金融方面的知识了解么
- 为这次投递准备了什么
6.19 终面
- 和主管面大致相同
2.科大讯飞
笔试7.1
- 20道八股单选，6道C++读代码，3道算法题
- 1.给一个n*n的矩阵，得分是该矩阵每个位置与其转置矩阵相同位置的差的绝对值，求得分，10分
- AC
- 2.给一个当前时间和闹钟列表，求下一个响起闹钟的时间，15分
- AC
- 3.给一个<>{}组成的字符串，求最少几次操作可以把它变成合法字符串，25分
- dfs超时、最长连续1错误，骗10%
3.OPPO
笔试7.7
- 20道八股单选，3道算法题
- 考到了一个sql语法的OVER()用法
- chown能修改权限，但是能修改所有者和用户组么
- sum = ++x + ++x的第二个x是=x+1，还是=x
- 1.给n个长度为m的字符串，求把他们变成一样的字符串的最少修改次数
- AC
- 统计每个下标的最多共同字符数，然后用m-这个数就是把这个下标改成一样的字符所需要的操作数
- 2.f(a,b,c) = a*b + c，给一个数组，求f()的最大值和最小值
- 50%，分各种情况讨论
- 数据范围很恶心，用long long都处理不了乘积，写了一个小时的字符串加减乘除，最后debug太复杂放弃
- ps：下次碰到long long处理不了的数值，用unsigned long long试试
- 3.给一个n*n的矩阵，里面依次用1,2,3….赋值，然后进行q次询问，每次询问给x,y,k，如果某个位置的元素满足abs(x-x1) + abs(y-y1) < k，那么就可以得到这个元素的分值，求每次询问得到的分值和
- 0%
- 模拟法肯定超时，应该是用优化的方法
4.小红书
笔试7.23
- 20到单项和不定项，3道算法题
- Over()的用法
- Between和IN的用法，特别是边界
- KMP算法的next数组怎么算
- 1.给一个n和k，要求构造一个不重复元素组成的长度为n的数组，k是这个数组的最大公约数，求这个数组的最小和
- ac, 直接算和res = k*(n*(n+1)/2)
- 要求是k的倍数，还要最小和，所以数组一定是(k, 2*k, 3*k…..)这种
- 2.给一个区间[0, n]，有m次加精华的操作，每次操作可以把[i,j]之间的帖子加精，例如[1,3]就会产生(1,2)、(2,3)两个精华帖，所有加精操作结束后你可以选一个长度为m的区间，求这个区间的最大精华帖数量
- 正常解法+骗82%
- 用滑动窗口只能过42%，最后针对大用例区间永远取[0, m]多过到82%
- 3.给一个数组和一个int类型target，你可以把其中一个元素用target替换掉，求最大连续子数组和
- ac，类似股票题
- 维护没变数组notHave和已经变了数组have过80%，最后状态压缩用int去取代vector
，和用unsigned long long替代int全通过
5.字节跳动
一面7.26
- 自我介绍一下吧
- 你觉得之前在字节工作的技术架构和流程上有什么问题么
- 聊一聊字节的实习经历、聊聊携程做的比较大的需求
- 要多聊一点技术细节，例如本来耗时1000ms，通过xx技术降低成了200ms，这里面具体是怎么做的
- 深挖秒杀系统
- 从一个用户点下单开始，描述一下整个流程
- 这个go写的数量控制接口很奇怪，为什么这样设计，go接口比起redis来说优势在哪
- 网络有几层，分别描述一下
- Http和Https有什么区别
- TCP和UDP有什么区别
- 操作系统进程切换做了什么
- 内核态里有什么
- 父子进程之间怎么通信
- 聚簇索引和非聚簇索引的区别
- mysql的索引是怎么实现的
- 为什么用B+树来做索引
- 算法题：k个一组反转链表(加分项)
二面8.2
- 自我介绍一下
- 你觉得你技术博客上最有技术含量的是哪个项目
- 说了河海大学的多叉树设计
- redis的list底层是什么结构，为什么要分两种这样实现
- 双向链表和压缩列表，list只支持头、尾操作
- 因为压缩列表存储在一块连续的内存上，所以存储效率很高。而双向链表除了保存数据还要存next、pre指针，内存开销大。但是它不利于修改操作，插入和删除操作需要频繁地申请和释放内存。特别是当zipList长度很长时，一次插入和删除可能会导致大量的数据拷贝
- redis3.2之后出现了快速列表，单节点用压缩列表来存，不同节点之间用双向链表的形式来连接，头部和尾部不能被压缩
- 让你设计一个线程安全的hash map，怎么设计
- 讲了read map和脏map来进行读写分离，说开销太大，有没有一个map实现的
- 讲了加读写锁，说太常规，开销大
- 后面讲了加锁的时候给随机字符串，要写的时候这个字符串和自己本地的字符串相同才表明是自己加的锁可以操作，否则表示其他线程加的锁不可以操作
- 消息队列的作用是什么，为什么用RabbitMQ不用Kafka
- 算法题：二叉树中最大路径和，起点和终点不一定是叶子节点，输出这个路径。要求只遍历一次
一面8.14
- 自我介绍一下
- 聊机票逻辑、聊Data Service逻辑
- B树和B+树的区别
- 跳表有什么特点
- TCP和UDP有什么区别
- HTTP报文的head头里都有什么
- GET和POST的区别
- LRU是什么，一般怎么实现
- ES为什么快，ES的倒排索引是什么
- Go的map底层是什么，如果并发地操作普通map会有什么后果
- context库里有什么方法，context是做什么的
- 算法题：给一个链表，判断是不是回文链表
二面8.15
- 自我介绍一下
- 挖了一些机票的重复订单，考察了一下如果用户多次点击下单的处理过程
- 脏读和幻读的区别是什么
- 什么是当前读和快照读，场景是什么
- 当前读适用于写操作，快照读适用于读操作
- qps是多少，怎么保证这么高请求不打挂
- redis的list底层是怎么实现的
- redis的动态字符串SDS为什么快
- 覆盖索引，后面写了一个sql求平均成绩
- go的defer拷打
- 算法题：旋转数组里面找目标值
- 属于ad_log到日志之间，1.广告数据 2.企业调用 3.用户调用
6.友塔
笔试7.27
- 1.一道简单题
- ac
- 2.有n个路口，给一个matrix[i][j]表示i到j需要花费多长时间，求0到n-1的最少花费时间
- ac
- spfa计算最短路径，一开始用二维数组存边超时，最后换用链式向前星解决
- 3.经典从原点(0,0)走到终点(n,m)问题，特别在加入了一个系列特殊点，位于这个特殊点上时下一步可以走到i+1, j+1
- 20%
- 二维dp爆内存，状态压缩成一维，但是还是因为存特殊点开二维数组爆内存
- 待解决问题：k个二维坐标开销最小的存储方案，条件查询复杂度O(1)
- 4.给一个5*5的矩阵，矩阵由1，2，3，4，5这几个数字组成，划一条线，这条线只能连接相同的数字(注意线可以斜着连)，最后的得分就是线上所有数字的和
- 66.67%
- 一开始准备用dfs做，但是每次递归有8个选择，复杂度太大太大
- 最后用并查集通过66.67%，应该是因为有线不能回头但是并查集不考虑方向导致的
一面8.7
- 自我介绍一下
- 介绍一下MyRedis，数据持久化是怎么做的，如果正在写操作，这时候发送了一个读操作会怎么样
- Redis的数据持久化是怎么做的
- 快排的时间复杂度是多少，具体怎么推导的
- 一个无向图，从起点到终点的最短路径，算法怎么推导的，首先你想怎么做，复杂度是多少
- 讲一下虚拟内存
- 从内网向外网发送一个http请求，会涉及哪些网络过程，内网a机器发出的请求，获得响应后怎么知道要把这个响应返还给a
- 负载均衡
- 后端技术栈：C、lula
- 算法题：给一个0，1，2…..依次顺序组成的无限长的字符串source，再给一个target，求这个target第一次出现的下标。如果是求1的第99次出现的下标呢
二面8.10
- 简单自我介绍
- 这么多段实习的目的是什么，那你觉得自己比较偏向哪种方向，还是偏向做业务而不是做基架是么
- 游戏开发和互联网开发的相同点和不同点，你觉得自己从事游戏开发的优势是什么
- 玩家发起一次攻击，客户端和服务端的处理部分是怎么样的，客户端发送的是操作还是状态，服务端发送的是操作还是状态
- redis+商城秒杀系统的redis和消息队列分别起什么作用
- 用什么技术保证可靠传输，什么场景用TCP，什么场景用UDP
- 游戏里面出现鬼步、走路回退的原因是什么
- 依赖包成环
- 1.如何检测有环
- 拓扑排序
- 2.有环的话怎么解决
- 枚举断边
- 3.如果是多个环耦合的话怎么解决
- 枚举断边
- 4.如果是多个环耦合的话，怎么返回各个环的依赖顺序
- 深搜+回溯
- 1.如何检测有环
- 你觉得手游和pc、主机游戏的区别点有什么
- 反问：主要做手游，客户端和服务端语言统一用lula，降低开销会用C写包装，unity是加分项不是必备项(因为操作很简单，也只有部分需求会涉及)
HR面8.10
- 本科、研究生学历
- 老家在哪，父母从事行业，独生子女
- 婚恋状况
- 对友塔的印象
offer call
- 薪资组成：(18+1)*14
- 朝10晚7，打卡制，周三固定加班
- 福利：每天30餐补，晚上8点半下班额外补30
- 职级：扁平结构
- offer接么
7.百度
一面8.2
- 介绍一下自己，说一个你认为自己最熟的项目，有哪些模块，数据大屏是怎么实现的
- redis缓存一致性问题怎么解决
- 双写、延迟双删，提了强一致性、强及时性的数据不该用缓存
- mysql数据库的引擎有哪些
- myISAM、innodb、memory
- 介绍一下互斥锁和读写锁，他们是怎么用的
- 读多写少的场景用读写锁，写多读少的场景用互斥锁
- context是做什么的，它里面的方法有哪些
- 上下文，树结构实现父子协程之间上下文的传递
- background()、xxWithCancel()、get()、set()
- defer关键字
- 碰到defer的时候会记录地址，然后函数返回的时候调deferreturn()去执行这个地址
- 一般记录在栈上，如果defer里面有recover就放到堆上
- defer的语句如果在执行前就确定了，那么编译器会直接把defer的内容加在函数末尾，这样也叫开放编码
- go的GMP模型，协程的大小是多少
- 几十kb
- 介绍一下channel，如果为0的话能塞进去么，不为0呢，是线程安全的么
- map的底层是什么，map是线程安全的么，如果要线程安全应该怎么用
- sync.map
- interface{}是什么，如果一个结构体只实现了其中一部分方法算实现了这个接口么
- 算法题：两个字符串的最长公共子序列
- 算法题：两个字符串的最长公共子串
二面8.14
- 介绍一下自己
- 阻塞IO和非阻塞IO有什么区别，阻塞的是进程还是什么，如果阻塞了那么还会耗费CPU资源么
- 阻塞是指用户空间里的调用线程一直在等待，而不能干别的事情。阻塞态不占用CPU，它只是在等待某项cpu之外的资源，比如i/o。进入就绪态去执行后才耗CPU
- 非阻塞是指用户空间里的调用线程拿到内核返回的状态值就返回自己的空间，IO操作可以干就干，不可以干，就去干别的事情
- redis是有线程安全的问题么
- 没有，因为它是单线程的
- redis单线程为什么还快，除了内存这个原因呢
- 内存数据库在内存中运行
- redis采用多路复用I/O，底层用的是epoll，所以很快
- 挖了一下机票和ttam的业务场景
- go的go func
- go func表示的是新起一个协程去执行函数，执行的顺序其实是不确定，这时候我们需要用一些mutex、sync、waitGroup这样的关键字来保证部分逻辑按我们设想的并发顺序来执行
- go的contex库怎么用
- go的defer有什么用
- go的垃圾回收GC用的是什么
- 讲一下go中你熟悉的数据结构
- 算法题：求一个字符串里的最长回文子串，如果只遍历一次应该怎么改
- 一开始给的是分别调用expend(i, i)和expend(i, i+1)，如果改成只遍历一次的话那么就改成expend(i)，然后再函数内部每次遍历的时候同时计算i,i和i,i+1两种情况
- 算法题：根据中序遍历和后序遍历数组建二叉树，根据二叉树算出它的前序遍历数组
- 部门业务做的是：搜索中的卡片，对接的业务方很多
三面8.22
- 自我介绍一下吧
- 说一下你对百度的了解吧
- 如果你发现在项目过程中同事有不道德行为，你会怎么处理
- 如果ld让你修改汇报的数据，改成下一个迭代预期能达到的效果，你会怎么处理
- 如果你的方案和ld、老同事的有分歧，怎么处理
- 如果你作为某个项目的owner需要其他部门同事配合，但是他们积极性不是很高，怎么处理
- 你的职业规划是什么样的，或者近几年你希望自己在哪方面发展
- 说出大模型的三个优点和三个卡脖子的缺点
- 优点：1.总结能力强 2.通用性强 3.减少人的重复劳动
- 缺点：1.总结结果不可避免地有错误 2.及时性差，只能用老数据来训练 3.成本高