快手春招多轮面经：信号量、Top-K 与实验分流
本场面试题
- Java 信号量如何保证线程安全，volatile 为什么不够？
- 巨大数组的 Top-K 怎样用快速选择或堆处理，动态变化时要注意什么？
- 多个实验各有多个分组，如何分配用户并减少相互影响？
面经与参考答法
快手春招多轮面经：信号量、Top-K 与实验分流
快手春招同一流程的多轮记录，岗位名称未注明。正文分别给出3月30日、4月3日、4月8日和4月14日，但未写年份；实验平台是第三轮自述中的业务描述。以下选录Java信号量、Top-K和实验分流三组。
以下短答、详解和示例均为编辑教学补充，不代表候选人现场回答、实际项目实现或企业标准答案。
（1）Java 信号量如何保证线程安全，volatile 为什么不够？
volatile 建立可见性和顺序关系，但不会把“检查许可是否足够，再扣减”合并成一个原子操作。信号量需要用锁或原子条件更新维护许可计数，并安排等待与唤醒；业务中优先使用 java.util.concurrent.Semaphore，许可控制与资源内部数据的一致性仍需分别处理。
详解
设一个自写计数器初始只有1个许可。线程A读取到1，线程B也读取到1，两者都通过检查并各自写回0，于是两个任务获得了本来只允许一个任务占用的资源。即使计数器是volatile，这个读、判断、写的整体仍可能交错。Java内存模型对volatile的happens-before保证，不等于为复合操作提供互斥。JLS17.4.5说明的是同步顺序关系。
一种底层思路是用CAS把“旧计数仍等于预期时扣减”作为原子条件更新；CAS失败后重读计数。但这只解释成功抢占许可的一部分：没有许可时怎么排队、被中断或超时怎样退出、释放后唤醒谁、公平与饥饿怎样处理，都还要设计。不能把一个自旋循环说成完整的阻塞信号量实现。
使用标准Semaphore时，成功acquire后在finally归还对应许可；没有成功获取就不能无条件release。它限制同时进入者数量，却不会自动保护资源池列表等其他共享结构。单许可信号量也没有mutex那样的所有者约束，其他线程可以release，不能把二者完全等同。JavaSE21 Semaphore合同明确了这些区别。这里按JavaSE21解释API合同，原文未给JDK版本，不推断具体内部源码。
（2）巨大数组的 Top-K 怎样用快速选择或堆处理，动态变化时要注意什么？
若教学约定是保留最大K个独立值，可用容量K的最小堆流式扫描，时间O(n log K)、额外空间O(K)；静态数组也可用随机化快速选择，期望O(n)，最坏O(n²)。动态删除、改分和并行合并都要另行明确数据身份与状态，不能只保留K项就承诺支持任意删除后的精确结果。
详解
原文没有给K值或“最大/最小”方向，下面明确采用“最大K个、重复值按出现次数计”的教学合同。最小堆的根是当前入选者里最小的阈值：先填满K项，以后只在新值大于根时替换，再下沉恢复堆序。最后若要有序输出，还需排序K项，不能直接把堆数组当排序结果。K=1可线性求最大值，空输入及K超范围要定义返回或报错规则。heapq文档解释了根与替换不变量。
快速选择通过一次partition确定枢轴位置，只继续处理包含目标边界的一侧；选出K个后仍未必内部有序。随机化选择的期望线性与最坏二次应分开，不能把它与普通全量排序O(n log n)混为一谈。Quickselect课程说明给出了单侧递推。
动态插入堆只需追加并上浮；删除根可用末项补根后下沉。若按任意ID删除，先查找可能需要O(m)，要有ID到堆位置的映射才能将定位与修复组合起来。更关键的是，若入选者被删除或分数下降，只保存K项时无法知道原先被丢弃者谁应补入；精确动态Top-K需全量有序索引、候补结构或重新扫描。
并行扫描独立记录时，各分片先留本地Top-K，再合并候选求全局Top-K；使用一致的并列顺序时，全局入选记录不会在其分片内排到K名之后。这一推理不适用于需要跨分片累计同一实体频次的榜单，后者必须先正确聚合。
（3）多个实验各有多个分组，如何分配用户并减少相互影响？
用稳定用户标识和实验标识做确定性分桶，使同一用户在同一分配版本中保持组别；不同实验使用独立命名空间。允许重叠的实验可独立分流，修改同一体验且会冲突的实验应先进入互斥层再分组。随机分组互相独立，不等于业务效果绝对没有交互。
详解
一种教学方案把决策拆成“有资格→进入哪个实验→属于哪个组”。实验内部可把稳定哈希映射到固定桶，再按冻结比例划区间；输入包含实验ID、用户ID和明确的分配版本。不要在每次请求临时随机，否则同一用户会在A/B间跳动；也不要使用跨进程不稳定的语言默认hash。这个哈希方案是编辑示例，不绑定某个产品实现。
并行实验分两种处理。如果搜索排序和页面文案允许重叠，用各自命名空间分组，新增一个实验不改已有实验的分桶规则；若两个实验都替换同一支付按钮，先按互斥层划出不相交的实验流量，再在各实验中分控制组和处理组。Eppo的实验分配及互斥层说明展示了分配与互斥是不同配置层次。
分配配置应不可变地标版本，变更比例时明确哪些用户允许迁移，必要时保存已入组记录维持粘性。缓存配置和批量计算可以降低请求开销，但缓存键也要带配置版本。日志区分被分配与实际曝光，并记录用户单位、实验、组、版本和时间，检查比例异常和丢失曝光。
最后，命名空间只解决分流算法不共用随机数或配置的问题；两个处理仍可能通过共享库存、社交关系或服务负载互相影响。出现这种干扰时，应改变随机化单位、隔离资源或采用互斥设计，而不是声称哈希函数已经保证因果独立。