字节跳动中国广告后端一面面经

《面试题目》

1. 手写单例模式（懒汉式），面试官反复说有问题
2. CAS 底层：两个线程真实交互的过程是什么样子的？
3. MySQL 中的 binlog 和 redo log 的二阶段提交，谁先提交？
4. HashMap 底层，为什么 ConcurrentHashMap 是线程安全的？
5. 限流 100 QPS 情况下，如何实现限流？滑动窗口的问题？令牌桶可以解决吗？
6. synchronized 是怎么样的？懒汉式中，如果一千个请求打过来怎么办？
7. 算法：求最长递增子序列，要求复杂度 O(n log n)

《参考解析》

1. 懒汉式单例的常见漏洞：最基础的懒汉式（判断实例是否为空再创建，不加同步）在多线程环境下会出现线程安全问题——多个线程同时判断实例为空，都会各自创建一个实例，破坏单例约束；正确实现需要双重检查锁定（Double-Checked Locking）：方法内 synchronized 同步块+volatile 修饰实例变量（防止指令重排序导致其他线程拿到未初始化完成的对象引用）。
2. binlog 与 redo log 二阶段提交顺序：MySQL 事务提交采用两阶段提交协议保证 binlog 与 redo log 的一致性——先写 redo log 并标记为 prepare 状态，再写 binlog，binlog 写入成功后才将 redo log 标记为 commit（真正提交）；这个顺序保证了即使中途宕机，也能通过判断 redo log 是否处于 prepare 状态、binlog 是否完整写入来决定崩溃恢复时是提交还是回滚，避免主从数据不一致。
3. 限流：滑动窗口 vs 令牌桶：滑动窗口按固定时间窗口统计请求数，存在窗口边界突刺问题（窗口切换瞬间可能允许双倍请求量通过）；令牌桶按固定速率生成令牌放入桶中，请求需要拿到令牌才能通过，桶满则丢弃多余令牌，既能限制平均速率又允许一定程度的突发流量（桶中已有的令牌可以被瞬时消耗），因此令牌桶在应对短时突发流量方面比滑动窗口更平滑、更常用于生产级限流方案（如 Guava RateLimiter）。
4. 最长递增子序列 O(n log n) 解法：维护一个”tails”数组，tails[i] 表示长度为 i+1 的递增子序列中最小的结尾元素；遍历原数组，对每个元素用二分查找在 tails 中找到第一个大于等于它的位置并替换（如果该元素比所有元素都大则追加到末尾），最终 tails 数组的长度即为最长递增子序列的长度，二分查找将每个元素的处理降至 O(log n)，总体复杂度 O(n log n)。