BIGO 安卓岗笔试 合并区间与滑动窗口

《面试题目》

1. 单选题 10 道。
2. 多选题 5 道。
3. 编程题（ACM 模式）：合并区间。
4. 编程题（ACM 模式）：滑动窗口最大值。
5. 编程题（ACM 模式）：给 n 行输入，每行包含 SUCCESS、FAIL、PEND 之一，输出各出现多少个。

《参考解析》

合并区间：先按左端点升序排序，再线性扫描：维护当前区间 [l, r]，如果下一个区间的左端点小于等于 r 就合并（r = max(r, next.r)），否则把当前区间收进答案并开启新区间。时间复杂度 O(n log n)，瓶颈在排序。边界条件是空数组返回空、单区间原样返回、包含关系（[1,10] 与 [2,3]）以及端点相接（[1,2] 与 [2,3]）该不该合并——按题目通常「相接即合并」，用 <= 判定。ACM 模式下要自己处理输入输出：先读行数 n，再循环读 n 行两个整数，用 BufferedReader 比 Scanner 快，输出按题目要求的格式（区间之间用空格还是换行、是否要保留原顺序）逐行打印，不要自己加多余的空格。

滑动窗口最大值：暴力每次扫窗口是 O(nk)，会超时。标准解法是单调双端队列：队列里存下标，保证队列对应的值单调递减。遍历每个元素时，先从队尾弹出所有比当前值小的元素（它们不可能再成为最大值），再把当前下标入队；然后从队首弹出已经滑出窗口的下标（deque.peekFirst() <= i - k）；当 i >= k - 1 时队首就是当前窗口的最大值。时间 O(n)、空间 O(k)。注意队列里存的是下标而不是值，否则无法判断过期；窗口大小 k 大于数组长度时直接返回空。Android 岗写 Java 时可以用 ArrayDeque 而不是 LinkedList，前者基于数组、没有额外节点分配。

字符串行统计的输入处理：这题本身不难，难在输入格式。稳妥写法是先读第一行拿到 n，然后循环 n 次读一行，用 trim() 去掉行尾的 \r（Windows 换行很容易在这里翻车），再用 switch 或 HashMap 计数，最后按题目规定的顺序输出三个数字。行数很多时不要用 Scanner.nextLine() 混用 nextInt()（前者会读到 nextInt 留下的空行），改用 BufferedReader.readLine() 统一按行解析。如果是多组测试数据（读到 EOF 为止），要写成 while ((line = reader.readLine()) != null)。这类题失分几乎都在输入的边界上，而不是逻辑本身，平时练习时特意用「行尾空格」「末尾没有换行符」「n 与后续行数不一致」三种输入自测一遍。