小游戏公司后端一面面经

《面试题目》

1. 从 52 张扑克牌中抽两张，抽出一红一黑的概率是多少？
2. 六个羽毛球中四个全新，第一次使用两个后放回，第二次抽到两个全新的概率是多少？
3. 单向链表按 n 个一组翻转应该如何实现？
4. 如何求 N 的阶乘转成十二进制后的位数、末尾零个数和末尾首个非零值？
5. 两个坐标系之间的点坐标如何转换？
6. 点乘和叉乘分别表示什么？
7. 数据库常见存储引擎有什么区别？
8. Java 集合框架中 List、Set 和 Map 如何选择？
9. 哈希冲突有哪些解决策略？
10. WebSocket 与传统 HTTP 通信有什么区别？

《参考解析》

1. 一红一黑的组合数为红牌数乘黑牌数，除以从全部牌中任取两张的组合数即可。组合计数时要保证分母和分子使用同一种“无序抽取”口径。
2. 第一次取出的球可能是全新或已使用，放回后状态改变；应按第一次取到全新球的数量分情况，再计算第二次取到两个全新的条件概率并求和。
3. 用哨兵节点逐段定位长度为 n 的区间，原地反转后接回前后链表；不足 n 个节点时按题意保留或反转。全程只需常数额外空间。
4. 不能直接构造完整阶乘时，可用质因数分解计算位数和末尾零，再用高精度分块乘法求末尾非零数字。十二进制的零由因子 12 的个数决定，即同时受 2 和 3 的指数限制。
5. 若变换为旋转矩阵和平移组成的齐次变换，先把点扩展为齐次坐标，再左乘从 A 到 B 的变换矩阵。矩阵方向和坐标系约定必须保持一致。
6. 点乘结果是标量，常用于投影和夹角判断；叉乘结果是向量，方向遵循右手规则，常用于求法向量和判断平面朝向。
7. InnoDB 支持事务和行级锁，适合高并发写入；MyISAM 结构简单但以表锁为主且不支持事务。选择应基于一致性和并发写需求。
8. List 保持顺序并允许重复，Set 强调唯一性，Map 按键查值。还要考虑访问复杂度、排序需求、线程安全和是否需要并发集合。
9. 常见方法有链地址法、开放寻址、再哈希和树化。需要根据装载因子、删除语义、内存局部性和最坏情况复杂度选择。
10. WebSocket 在 HTTP 握手后升级为双向长连接，服务端可主动推送；HTTP 更适合请求响应。长连接仍需心跳、断线重连和连接数控制。