Google SWE Intern OA 复盘：30 分钟两题高分 + 四道高频真题完整拆解

刚陪一位学员做完 Google SWE Intern OA，题型还是两道 coding，30 分钟。和 TikTok 比难度略高，两题都是 medium 偏上。以前更偏常规数据结构，今年更强调图算法和变形题。把高频题型整理出来给想投 Google 的同学参考。

一、Google SWE Intern OA 概览

核心特点：Google 不追难题，但喜欢在经典题上做变形，光会原题不够，要能应对改条件。

二、题 1：回文子串计数（DP / 中心扩展）

给字符串 s，返回其中回文子串的个数。

def countSubstrings(s):
    n, count = len(s), 0
    def expand(l, r):
        cnt = 0
        while l >= 0 and r < n and s[l] == s[r]:
            cnt += 1
            l -= 1
            r += 1
        return cnt
    for i in range(n):
        count += expand(i, i)      # 奇数中心
        count += expand(i, i + 1)  # 偶数中心
    return count

思路：中心扩展，每个字符（或两字符之间）为中心向两侧扩。复杂度：时间 O(n²)，空间 O(1)，优于 DP 表的 O(n²) 空间。

三、题 2：爬楼梯（经典 DP，注意变体）

n 阶楼梯，每次爬 1 或 2 阶，有多少种方法到顶？

def climbStairs(n):
    a, b = 1, 1  # dp[0]=1, dp[1]=1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

思路：dp[i] = dp[i-1] + dp[i-2]，滚动变量优化到 O(1) 空间。 Google 变体提醒：常改成「可以爬 1/2/3 阶」（三项递推）或「某些台阶不能踩」（跳过这些 i 设 dp[i]=0）。备考一定要练变体。

四、题 3：二叉树最大路径和（递归）

给二叉树根节点，返回任意非空路径的最大和。

def maxPathSum(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node:
            return 0
        # 负贡献直接砍掉（取 0）
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        # 经过当前节点的路径和（可同时含左右）
        best = max(best, node.val + left + right)
        # 返回给父节点：只能选一条边
        return node.val + max(left, right)
    gain(root)
    return best

关键：区分两个概念——「向下到当前节点的最大路径和」（可返回给父节点，只能选一条边）和「经过当前节点的最大路径和」（可同时含左右，用于更新答案）。复杂度：时间 O(n)，空间 O(h)。

五、题 4：课程表（拓扑排序判环）

numCourses 门课，prerequisites[i] = [a, b] 表示学 a 前必须先学 b。能否修完所有课？

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    indeg = [0] * numCourses
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
        indeg[a] += 1
    # 入度为 0 的先入队
    q = deque([i for i in range(numCourses) if indeg[i] == 0])
    done = 0
    while q:
        node = q.popleft()
        done += 1
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return done == numCourses  # 全部出队 = 无环

思路：本质是有向图判环。拓扑排序维护入度，每次移除入度 0 的节点，最终全部移除则无环。复杂度：时间 O(V + E)，空间 O(V + E)。

六、备战节奏

FAQ

Q1：Google Intern OA 难度怎样？

两题 medium 偏上，30 分钟。不追极难，但今年图算法和变形题比重上升。重点是拆解问题的能力，而不是背原题。

Q2：爬楼梯这种简单题也会考？

会，但通常带变体——能爬 1/2/3 阶，或某些台阶不能踩。光背原题会被改条件卡住，一定要练变体的递推式。

Q3：最大路径和最容易错在哪？

混淆「返回给父节点的路径」（只能一条边）和「经过当前节点的路径」（可含左右）。前者用于递归返回，后者用于更新全局答案，写反就错。

Q4：30 分钟两题来得及吗？

来得及，前提是高频题型练熟、能快速识别套路。卡壳在思路上最耗时。我们提供 OA 辅助：题型预测 + 限时陪练 + 实时给方向，帮你把会的稳稳拿下。

正在准备 Google SWE Intern OA？

Google OA 考拆解能力和变形应对，不是偏题。如果你想要四道高频题的限时陪练、图算法/DP 变体专项，或需要 OA 辅助 的实时对接，欢迎联系交流，发岗位 JD 先做题型预测，再排练习计划。

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

联系方式

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