逆天公司 让我填高考排名分数就算了，还问我大学努不努力～

网上有人吐槽一家公司：先让你填高考排名分数，接着追问大学努不努力，还要你写“有没有ACM队”。我觉得这面试官不是在招人，是在开“人生复盘发布会”。

网友们也挺会补刀：有人说“下一步是不是要交小学奥数奖状”；还有人笑到不行，“真打ACM的人，谁来这种中厂刷水面试经验啊”。

我觉得最离谱的是它把你当成可检索的简历数据库，问题越问越像在做画像。 碰上这种，我也支持“先瞎填”，反正面试就是互相试探：你看我简历，我看你有多抽象。至少好处是省时间，几道题就能判断这家公司值不值得继续聊。

算法题：灯泡开关

那天晚上我正准备关电脑啊，准备溜回去刷个剧，结果隔壁测试小妹突然丢过来一句： “东哥东哥，你帮我看个算法题，灯泡那个啥…我手机上看半天没想明白。”

我一听，哦，这不是经典面试题嘛：

有 n 个灯泡，从 1 到 n 编号，一开始全关。 第 1 轮，把所有灯泡状态反转一次； 第 2 轮，反转编号是 2 的倍数的； 第 3 轮，反转编号是 3 的倍数的…… 一直到第 n 轮。 问：最后亮着的灯有几个？是哪些？

听起来挺像运维半夜在机房里一排排关灯，对吧……

先别急上数学，我第一反应跟你们一样： “这不就俩 for 循环的事么，写就完了。”

我随手就敲了一个最土的版本，现场演示给她看：

defbulbs_bruteforce(n: int):
# False 代表关，True 代表开，下标 0 占位不用
    bulbs = [False] * (n + 1)

for i in range(1, n + 1):      # 第 i 轮
for j in range(i, n + 1, i):   # 反转 i 的倍数
            bulbs[j] = not bulbs[j]

# 返回亮着的灯的编号
    on_indices = [idx for idx, status in enumerate(bulbs) if status and idx != 0]
return on_indices

我跑了个小例子：

print(bulbs_bruteforce(10))
# 输出 [1, 4, 9]

我跟她说：你看，前 10 个灯，最后亮的是 1、4、9。 小妹嗯了一声，说：“东哥，这要是 n=10^9 呢？”

我…沉默一秒。 O(n²) 的算法，一眼体验派，面试官直接把你灯给关了。

这个时候就得装一装“多年搬砖经验”，开始假装推理。 其实也不难，你想想，每个灯泡被按几次，完全取决于它有多少个“约数”。

比如编号 6： 能整除 6 的数有 1、2、3、6，一共 4 个，所以这个灯会被反转 4 次，偶数次，最后还是关的。

亮灯需要什么条件？ ——被反转奇数次。

那什么时候约数个数会是奇数呢？ 绝大多数数的约数都是成对出现的：

• 2 × 6 = 12
• 3 × 4 = 12 所以 2 和 6 一对，3 和 4 一对，一来一回刚好两次。

只有一种特殊情况： 当这个数是完全平方数的时候，比如 9：

• 1 × 9
• 3 × 3 你看 3 自己跟自己配对，只算一个约数，所以总数是奇数。

所以结论就很清晰了： 最后亮着的灯，就是编号是完全平方数的灯： 1, 4, 9, 16, 25, ...

那问题就从“模拟全场关灯开灯”变成了： “1 到 n 里面有多少个完全平方数？”

这个就简单多了啊， 最大的不超过 n 的平方数，是 ⌊√n⌋²。 所以亮灯的数量，就是 ⌊√n⌋，整数部分。

我当场又写了个“看起来就很聪明”的版本：

import math

defbulbs_fast(n: int):
# 亮着的灯数量，其实就是 sqrt(n) 向下取整
    count = int(math.isqrt(n))  # 等价于 int(math.sqrt(n))

# 顺便把亮着的灯编号也算出来，方便对拍
    on_indices = [i * i for i in range(1, count + 1)]

return count, on_indices

顺手对拍一下，防止我这种困得要死时把数学也写错了：

if __name__ == "__main__":
    n = 100
    brute_on = bulbs_bruteforce(n)
    fast_count, fast_on = bulbs_fast(n)

    print("暴力亮灯：", brute_on)
    print("优化亮灯：", fast_on)
    print("数量是否一致：", len(brute_on) == fast_count == len(fast_on))

跑完一看，全对。 这会儿再跟面试官说复杂度从 O(n²) 干到 O(√n)，气势就不一样了。

其实这题的“味道”，跟我之前做数据库压测的时候有点像，表面上看是“循环很多次的性能问题”，实际上绕了一圈发现根本不该真循环，直接找数学规律干掉一大半操作就行了。

群里有人看了代码跟我说：“东哥，这能不能用什么位运算啊，感觉更高端一点。” 我说兄弟别这会儿装，面试官要的是你脑子里那点数论直觉，不是你会写 x & (x - 1)。 你连为啥是完全平方数都没想明白，上来折腾 bit 操作，纯属给自己加戏。

再啰嗦两句实战里会踩的坑：

• 别用 math.sqrt(n) 直接转 int，浮点有时候会给你来个 3.999999 这种鬼东西，保险点就用 math.isqrt。
• n 要是特别大（10^12 这种），暴力模拟就别想了，for 两层都能把你 CPU 烤熟。
• 写暴力版不是没用，它是你验证“数学优雅解法”的小对照组，线上出事的时候你还能拿它做个简单对拍。

最后测试小妹看懂了，跟我说一句：“原来你们老程序员写代码之前真的会先想一会儿啊。” 我心里想的是：那当然了，不想的话，灯是亮了，工资可能要暗一点了…

行了，这会儿我得去处理真正会把生产线灯泡搞黑的那种 bug 了，这种面试题就先到这儿，你要是想整点进阶版的（比如随机关一部分再算之类），下次再聊。