Booking OA 两道题，一道考经典二维 DP，一道考字符串处理 + 排序综合能力。思路清晰但细节多，节奏要稳。以下是完整复盘。
考试概况
| 项目 | 详情 |
|---|---|
| 平台 | HackerRank |
| 题数 | 2 道 |
| 难度 | Medium / Medium |
| 岗位 | SDE |
| 核心考点 | 动态规划、HashMap、HashSet、自定义排序 |
Q1：最大正方形（Maximal Square）
题目核心
给定一个由 '0' 和 '1' 组成的二维矩阵，找出其中只包含 1 的最大正方形，返回其面积。
解题思路
暴力思路（O(mn·min(m,n)²)，会超时）
枚举每个格子作为正方形左上角，尝试扩展边长，统计是否全为 1。当矩阵较大时明显超时。
最优解：二维动态规划 O(mn)
定义：dp[i][j] 表示以 (i, j) 为右下角的最大全 1 正方形的边长。
转移方程：
- 若
matrix[i][j] == '0'：dp[i][j] = 0 - 若
matrix[i][j] == '1'：
$$dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]) + 1$$
直觉：当前格子能构成的最大正方形，受限于左、上、左上三个邻居中最小的那个——只要三个方向都能撑起边长 k 的正方形，当前格子就能形成边长 k+1 的正方形。
最终答案：遍历所有 dp[i][j]，取最大值 side，返回 side * side。
代码框架
def maximalSquare(matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
max_side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side
复杂度分析
- 时间复杂度：O(mn)，只需遍历矩阵一次
- 空间复杂度：O(mn)，可优化到 O(n) 用滚动数组
关键洞察
dp[i][j]的转移只依赖左、上、左上三个格子。取最小值的原因：正方形的边长由最短的那条"木桶边"决定。这是矩阵 DP 中最经典的状态定义之一。
Q2：酒店评论关键词评分排序（Hotel Review Keyword Scoring）
题目核心
给定两组关键词（正面词集和负面词集），以及若干条酒店评论（每条评论关联一个 HotelID）。根据关键词出现情况计算每家酒店的总分，返回得分最高的前 k 家酒店 ID（分数相同时按 ID 升序）。
解题思路
整体流程：
- 将正面关键词和负面关键词分别存入两个
HashSet，实现 O(1) 查询 - 遍历所有评论，对每条评论：
- 用正则去除标点，统一转小写
- 拆分成单词列表
- 遍历单词：命中正面词 +1，命中负面词 -1
- 将分数累加到
HashMap<HotelID, TotalScore>
- 将 Map 转为 List，用自定义比较器排序：分数降序，分数相同则 ID 升序
- 提取排序后的前 k 个 HotelID
代码框架
import re
from collections import defaultdict
def topKHotels(positive_words, negative_words, reviews, k):
pos_set = set(positive_words)
neg_set = set(negative_words)
score_map = defaultdict(int) # HotelID -> TotalScore
for hotel_id, review_text in reviews:
# 去除标点，统一小写，拆分单词
words = re.sub(r'[^\w\s]', '', review_text.lower()).split()
for word in words:
if word in pos_set:
score_map[hotel_id] += 1
elif word in neg_set:
score_map[hotel_id] -= 1
# 自定义排序：分数降序，ID 升序
sorted_hotels = sorted(score_map.keys(),
key=lambda h: (-score_map[h], h))
return sorted_hotels[:k]
复杂度分析
- 时间复杂度：O(W log W)，W 为所有评论的总单词数（排序主导）
- 空间复杂度：O(H + K)，H 为酒店数，K 为关键词总数
关键洞察
用 HashSet 存关键词，查询 O(1)；用 HashMap 累计分数，避免重复遍历。排序时用自定义比较器同时处理"分数降序"和"ID 升序"两个维度，是多键排序的标准写法。
两题核心思路对比
| 题目 | 核心技巧 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| Q1 最大正方形 | 二维 DP，min 三邻居 +1 | O(mn) | O(mn) |
| Q2 酒店评分 | HashSet + HashMap + 自定义排序 | O(W log W) | O(H + K) |
常见思维误区
| 题目 | 误区 | 正确方向 |
|---|---|---|
| Q1 | 枚举所有可能正方形，O(mn²) 超时 | 用 DP 递推，O(mn) 一次遍历 |
| Q1 | 转移方程用求和而不是取最小 | 取 min，正方形由最短边决定 |
| Q2 | 用 List 线性查找关键词 | 用 HashSet，查询 O(1) |
| Q2 | 分数相同时忽略 ID 排序规则 | 自定义比较器同时处理两个排序维度 |
Booking OA 应试策略
临场节奏
- 先读完两题，判断难度分配时间
- Q1 类矩阵 DP：先想「以当前格为右下角」的状态定义，转移方程几乎都是三邻居取 min/max
- Q2 类字符串统计：先确定数据结构（HashSet 查询 + HashMap 累计），再处理排序
- 写完跑样例，注意边界（空矩阵、k 大于酒店数）
相关 LeetCode 练习
| 题号 | 题目 | 对应考点 |
|---|---|---|
| 221 | Maximal Square | Q1 完全相同 |
| 1277 | Count Square Submatrices | Q1 变体 |
| 85 | Maximal Rectangle | Q1 进阶 |
| 692 | Top K Frequent Words | Q2 排序方式 |
| 1 | Two Sum | Q2 HashMap 基础 |
🚀 需要 Booking OA 辅助？
oavoservice 长期稳定承接 Google、Amazon、TikTok、Booking、Uber、Bloomberg、微软 等各大科技公司 OA / VO 辅助，国内外面试笔试均可，高频题库覆盖率极高。
立即添加微信：Coding0201
获取：
- ✅ Booking OA 实时辅助（屏幕共享 + 实时打字提示）
- ✅ HackerRank 真实题库（覆盖 80%+ 高频题）
- ✅ 一对一模拟 OA + 详细反馈
- ✅ VO 面试辅助（算法 + 系统设计）
📱 微信：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected]
联系方式
Email: [email protected]
Telegram: @OAVOProxy