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