Senior SWE · Technical Screen Coding

Airbnb Board Game:同类型连通区域格数 × 皇冠总数

Senior Tech Screen 给 5×5 区域类型/皇冠格,按每个连通区域单独计算面积与皇冠总数。

题目重点:Senior Tech Screen 给 5×5 区域类型/皇冠格,按每个连通区域单独计算面积与皇冠总数。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 每格是一个区域类型字符加非负整数皇冠数,皇冠数可能不止一位;按上下左右四连通,不含对角。
  • 同类型但不相邻的格子属于不同区域,各自算分;空棋盘返回 0,行宽一致。

解题路线

  1. 遍历每格,若未访问就以其类型启动 BFS/DFS;只走相同类型的四邻居并即时标 visited。
  2. 对每个连通块累计 areaCells 和 crowns,出队完毕把 areaCells×crowns 加入总分。
  3. 每格恰进入一个连通块,且搜索只沿同类型边扩展,所以找到的恰是该格所属的极大连通区域;各区域不重叠、覆盖全图。
  4. 测试单格 0 皇冠、同类型对角接触、长条区域、多位皇冠和多个隔开的 G 区域。

手动走一遍

题目首个 G 区域 4 格、皇冠总数 8,得 32;首个 W 区域 4 格、皇冠总数 2,得 8。需要继续遍历其余不相连区域并累加,而不是按类型把全图 G 全合并。

规模与取舍

R×C 棋盘每格只访问一次,O(RC) 时间;visited 与 BFS 队列最坏 O(RC) 空间,可原地标记则减少 visited 但会改输入。

易错点与追问

容易失分的边界

  • 把对角接触视为相连。
  • 按类型全局汇总而不是逐连通块。
  • 用皇冠数之和替代面积×皇冠和。
  • 假设 token 永远只有两字符,皇冠≥10 时解析错误。

继续深挖

  • 若改成八连通怎么变?
  • 棋盘局部更新时如何维护分数?
  • 若区域值很大,如何避免递归栈溢出?
✓已复制微信号!