Google NG Online Assessment 复盘：前缀后缀两道真题 + 找规律解题心法

Google New Grad 的 OA 在八月底才开，比其他大厂晚不少。题型延续以往风格——逻辑清晰的算法题，核心在「找规律 → 转化问题」。整理两道做过的真题，思路很有代表性。

一、Google NG OA 概览

核心提醒：题目看着简单，关键在快速发现数学规律或前缀后缀关系，O(n) 或 O(n log n) 才能过，暴力会 TLE。

二、题 1：翻转一个元素后最小化绝对和

给一个整数数组，最多翻转一个元素（乘以 -1）。求翻转后数组和的最小可能绝对值。

例：[2, -3, 5] → 输出 0。原和 = 4。翻 5 → 和 = -1，abs = 1；翻 2 → 和 = 0。最优结果 0。

def minAbsSum(arr):
    s = sum(arr)
    best = abs(s)                       # 不翻转的基准
    for x in arr:
        # 翻转 x 等价于 和 变化 -2*x
        best = min(best, abs(s - 2 * x))
    return best

思路转化：把「乘以 -1」转成「和变化 -2*x」。遍历每个元素取 min(abs(s - 2*x))，再和 abs(s) 比较。复杂度：时间 O(n)，空间 O(1)。

三、题 2：统计有序拼接的分割方式

给一个数组，分成两个非空部分 left 和 right，各自排序后拼接。求有多少种分割方式使最终拼接数组整体有序。

例：[2, 1, 3, 5] → 输出 2。在 index 2 分（[2,1]|[3,5]）→ [1,2,3,5] 有序 ✅；在 index 3 分（[2,1,3]|[5]）→ [1,2,3,5] 有序 ✅。

def countSortedSplits(arr):
    n = len(arr)
    # prefix_max[i]：前 i+1 个元素的最大值
    prefix_max = [0] * n
    prefix_max[0] = arr[0]
    for i in range(1, n):
        prefix_max[i] = max(prefix_max[i - 1], arr[i])
    # suffix_min[i]：从 i 到末尾的最小值
    suffix_min = [0] * n
    suffix_min[n - 1] = arr[n - 1]
    for i in range(n - 2, -1, -1):
        suffix_min[i] = min(suffix_min[i + 1], arr[i])
    # 在 i 和 i+1 之间切，只要 左段最大 <= 右段最小
    count = 0
    for i in range(n - 1):
        if prefix_max[i] <= suffix_min[i + 1]:
            count += 1
    return count

思路转化：排序后拼接是否有序，等价于 左段最大值 <= 右段最小值。预处理 prefix_max 和 suffix_min，遍历每个切点判断。复杂度：时间 O(n)，空间 O(n)。

这题表面是「模拟排序」，本质是前缀/后缀信息的经典套路。

四、找规律解题心法

FAQ

Q1：Google NG OA 在哪个平台？

部分批次用 Codility，部分用 HackerRank，按邀请邮件为准。两者环境略有差异，提前熟悉编辑器和提交方式能省时间。

Q2：题目看着简单为什么还挂？

因为暴力会 TLE。Google NG OA 表面简单，但要求 O(n) / O(n log n)。挂的人多半是没找到数学规律或前缀后缀转化，硬写双重循环超时。

Q3：前缀最大 / 后缀最小套路常考吗？

很常考。凡是涉及「分割数组」「左右两段比较」的题，多半能用 prefix_max / suffix_min 预处理 O(n) 解决。这是 Google NG OA 的高频套路，务必练熟。

Q4：75 分钟想不出思路怎么办？

最耗时的就是卡在「找规律」这一步。我们提供 OA 辅助：题型预测 + 限时陪练 + 卡壳时实时点拨转化思路，帮你避免在一道题上耗光时间。

正在准备 Google NG OA？

Google NG OA 考的是找规律和问题转化，不是死刷题。如果你想要这两道真题的限时陪练、前缀后缀套路专项，或需要 OA 辅助 的实时对接，欢迎联系交流，发岗位 JD 先做题型预测，再排练习计划。

立即添加微信 Coding0201，获取 Google NG OA 真题与陪练。

联系方式

• 微信：Coding0201
• Email：[email protected]
• Telegram：@OAVOProxy