Python技术迷

上周面试一个27岁的前端开发,已敲定要发 offer。结果谈到作息,他说只接受朝九晚六不加班,周末必须双休,连临时支援都不接受

面到最后都准备发 offer 了,结果卡在一句“我只接受朝九晚六,双休,临时支援也不去”。这画面真有点魔幻,HR估计前一秒还在走流程,后一秒眼皮都跳了。

Image

评论区也挺热闹。有人说这哥们儿挺清醒,打工而已,凭啥默认随叫随到。也有人吐槽,前端岗现在卷成这样,你这条件一摆,等于先把自己筛掉一半。

但我看下来,这事最扎心的点不是他提要求,是很多公司直到快发 offer 了,才肯把真实作息往外抖。平时嘴上都写“弹性”“团队氛围好”,一问细节,马上变成晚上得盯群、周末要兜底。那人家提前说清楚,也没啥毛病,省得入职一个月再互相骂。

说白了,这不是谁矫情,是两边都在摊牌。一个想找稳定班表,一个想要高配牛马。没对错,就是不匹配。

算法题:角矩形的数量

这题一上来别急着画矩形。

真按“找左上、找右上、找左下、找右下”这么枚举,代码能写,跑起来也能把你送走。一个 m * n 的 01 矩阵,四层意思差不多都出来了,面试官看你写到一半,基本就知道你还停在“把题做出来”,没到“把题做对还做快”。

这题我第一眼会先盯住一件事:矩形不是重点,两条横线才是重点。

只要两行里,有两列同时为 1,这两行两列就能围出一个角矩形。 比如第 r1 行和第 r2 行,在第 1 列、第 5 列都为 1,那就是一个矩形;如果它们一共有 3 列都同时为 1,那就不是 3 个矩形,而是组合数 C(3, 2),也就是 3 个。

所以做法就顺了:

先枚举两行。 再数这两行有多少列同时为 1。 假设这个数量是 cnt,那这一对行能贡献的矩形数就是:

cnt * (cnt - 1) // 2

代码不用花,直接写核心:

defcount_corner_rectangles(grid):
ifnot grid ornot grid[0]:
return0

    rows, cols = len(grid), len(grid[0])
    ans = 0

for top in range(rows):
for bottom in range(top + 1, rows):
            cnt = 0
for c in range(cols):
if grid[top][c] == 1and grid[bottom][c] == 1:
                    cnt += 1
            ans += cnt * (cnt - 1) // 2

return ans

拿个例子过一下更直观点:

grid = [
    [1, 0, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0],
    [1, 0, 1, 0, 1]
]

print(count_corner_rectangles(grid))  # 1

为啥是 1? 因为只有第 2 行和第 4 行,在第 3 列、第 5 列同时为 1,刚好凑出一个。

这题的时间复杂度是 O(m * m * n),也就是枚举行对,再扫列。大多数面试场景够用了。 但要是我在线上写这种统计题,还会顺手再看一眼数据规模。要是列特别多、1 又比较稀疏,可以只记录每一行值为 1 的列,再去做列对计数,会更省一点。

比如这样:

from collections import defaultdict

defcount_corner_rectangles_v2(grid):
    pair_count = defaultdict(int)
    ans = 0

for row in grid:
        ones = [i for i, v in enumerate(row) if v == 1]
for i in range(len(ones)):
for j in range(i + 1, len(ones)):
                pair = (ones[i], ones[j])
                ans += pair_count[pair]
                pair_count[pair] += 1

return ans

这个写法更像工程里常见的“前面出现过多少次相同模式,就直接累加多少贡献”。看到列对 (c1, c2) 以前出现过 3 次,那当前这一行再碰到它,就新增 3 个矩形,不用回头翻旧账。