面试填高考排名和ACM经历？中厂招聘逻辑引发技术圈热议

我最近在网上刷到一位网友的吐槽，说是面试前填资料，让他写高考排名和分数还不够，后面还接着追问大学到底努不努力、有没有打过 ACM（国际大学生程序设计竞赛）、带没带过队。

这位哥们当场就CPU冒烟了：我要是真能在ACM赛场上熬到进队打题，手里的项目和奖牌都够写成小作文了，还用得着来投这种“中厂”积累所谓的“水面试经验”吗？图啥，图简历表格能多一行吗？

评论区也挺精彩。有网友说这是“考古式背调”，恨不得把你小学奥数名次也填上；还有人说这属于“筛人不筛能力，筛你愿不愿意配合尬聊”。

说实话，我觉得面试前先把候选人当问卷题库来填，多少有点抽象了。一个人的技术能力和潜力，真的能通过这些“古早”信息衡量吗？大家在面试求职时还遇到过哪些更离谱的问题，不妨分享一下。

面试题：灯泡开关

扯远了，咱们聊回技术。说到面试，就不得不提一道堪称“杀熟”的经典算法题：灯泡开关。哪怕是老程序员，一紧张也可能在这儿翻车，我自己就翻过。

那天同事让我在白板上写这个题，我一拍大腿：“这还不简单，两层for循环不就完了？”结果写完一看时间复杂度 O(n²)，面试官笑而不语，我整个人都麻了。

先把题意捋一下，免得跑偏：

• 有 n 个灯泡，初始状态都是关着的。
• 然后进行 n 轮操作：
  • 第 1 轮，把所有灯泡切换一次（关→开，开→关）。
  • 第 2 轮，把编号为 2 的倍数的灯泡切换一次。
  • 第 3 轮，把编号为 3 的倍数的灯泡切换一次。
  • …
  • 第 n 轮，把编号为 n 的倍数的灯泡切换一次。
• 最后问：有多少个灯是亮的？

刚入行的时候，我真的会老老实实写这么一个玩意儿：

public int bulbSwitchNaive(int n) {
    boolean[] bulbs = new boolean[n + 1]; // 从1开始用
    for (int round = 1; round <= n; round++) {
        for (int i = round; i <= n; i += round) {
            bulbs[i] = !bulbs[i]; // 切换开关
        }
    }
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (bulbs[i]) count++;
    }
    return count;
}

逻辑上一点问题没有，但那个时间复杂度直接干到了 O(n²)。想象一下，当 n = 10⁹ 的时候，你这个方法还没跑完，人事那边估计已经把简历放进“已读不回”的文件夹了。

后来我冷静下来想了一下：到底什么情况下，灯泡最后会是亮的？

关键在于，灯泡 k 会被切换几次？每一轮，只要轮次 round 是 k 的约数（即 k % round == 0），这个灯泡就会被切一下。所以，灯泡 k 被切换的次数，就等于它的约数个数。

那么：

• 被切换偶数次 → 最终回到“关”的状态。
• 被切换奇数次 → 最终停在“开”的状态。

也就是说，只有约数个数是奇数的灯泡，最后才会亮。

哪些数的约数个数是奇数呢？大多数数字的约数都是成对出现的，比如 12：

• 1 × 12
• 2 × 6
• 3 × 4
  约数总是成双成对，所以总个数是偶数。

唯一的例外是完全平方数。比如 9：

• 1 × 9
• 3 × 3
  这里的 3 自己和自己配对了，相当于一个约数顶了两个的位置，导致总约数个数变成了奇数。

所以，整个题的答案呼之欲出：最后亮着的灯，其编号一定是完全平方数：1， 4， 9， 16， 25， …

那么问题就变得极其简单：在 1 到 n 之间有多少个完全平方数？就是 1²， 2²， 3²， …， k²，其中最大的 k 满足 k² ≤ n，即 k = ⌊√n⌋。

于是，我们把上面那个“折磨 CPU”的两层循环，干净利落地换成了这样：

public int bulbSwitch(int n) {
    // 其实就问：1 到 n 之间有多少个完全平方数
    return (int) Math.sqrt(n);
}

第一次写出这行代码的时候，我整个人是懵的：“啊？这就是传说中的数学思维降维打击算法题？那我前面吭哧吭哧写循环是在健身吗？”

当然，面试时如果你直接甩出这行代码，最好嘴上再补充两句推导过程，不然容易被当成“背答案的选手”。可以按这个思路解释：

1. 每个灯泡被切换的次数等于其编号的约数个数。
2. 只有完全平方数的约数个数为奇数（因为有一个成单的平方根）。
3. 因此，只有完全平方数编号的灯最后会亮。
4. 1 到 n 之间的完全平方数个数就是 ⌊√n⌋。

如果你担心面试官觉得你只是记住了结论，也可以随手写一个小的验证函数，模拟一下前 20 个灯的情况：

public static void debugCheck(int n) {
    boolean[] bulbs = new boolean[n + 1];
    for (int round = 1; round <= n; round++) {
        for (int i = round; i <= n; i += round) {
            bulbs[i] = !bulbs[i];
        }
    }
    System.out.print("ON bulbs: ");
    for (int i = 1; i <= n; i++) {
        if (bulbs[i]) System.out.print(i + " ");
    }
    System.out.println();
    System.out.println("count = " + (int) Math.sqrt(n));
}

运行一下 debugCheck(20)，输出会是类似 ON bulbs: 1 4 9 16 的结果，正好对应 1², 2², 3², 4²，数量是 4，也就是 Math.sqrt(20) 取整的结果。

这道题的两个层次就很清晰了：

• 朴素模拟法：时间复杂度 O(n²)，用来验证思路，写给自己看。
• 数学分析法：时间复杂度 O(1)，洞悉问题本质，写给面试官看。

弄懂这道题，不仅是学会了一个技巧，更是对算法中数学思维的一种训练。你还可以自己延伸一下，比如要求输出亮着的具体是哪些灯，或者当 n 极大时思考一下 double 转 int 的精度问题，这些都是面试官可能追问的小细节。

无论是面对抽象的面试提问，还是具体的算法考题，保持清晰的逻辑和挖掘问题本质的能力，可能比单纯的知识储备更重要。关于Java的更多面试题和实战技巧，也欢迎到云栈社区和其他开发者一起交流探讨。