Google Summer Intern｜SDE 暑期实习｜Google 面经真题

流程概况

今年大部分同学申请 Google intern 都会经历一个漫长的等待期，但一旦简历被捞出进入正式流程，进展通常很快：很多人一周之内就完成了 OA、安排面试并结束两轮 VO。海投和内推差别不大，内推略好一点点。

面试形式

• 两轮技术面，通常安排在同一天，每轮 45 分钟，中间有短暂休息。
• 每场前 5 分钟是寒暄和自我介绍，接着进入 coding。
• Google 的 editor 是一个简单的文本框，不能运行代码，所以写完要自己 dry run 一遍，解释运行过程，并分析时间和空间复杂度。
• 时间充裕的话，面试官会问一两个 follow-up，通常考察可扩展性和优化思路。

下面是一套真题。

第一题：最长无重复子串长度

题目

给定字符串，找出不包含重复字符的最长子串的长度。例如输入 "abcabcbb"，输出 3，对应子串 "abc"。

思路

• 暴力：枚举每个起点，往右扩展并用集合判断是否重复，O(n²)。
• 滑动窗口 + 哈希表：用 left、right 两个指针表示窗口边界，哈希表记录每个字符最近一次出现的位置。右指针遇到重复字符时，把左指针移到该字符上次出现位置的右边，保证窗口内无重复。每步更新 maxLen = max(maxLen, right - left + 1)。时间 O(n)。

Follow-up：输出最长子串本身，而不只是长度。只要在更新最大值时顺便记录窗口的起点即可。

def longest_unique_substring(s):
    """返回最长无重复子串本身；长度就是 len(结果)"""
    last = {}                         # 字符 -> 最近出现的下标
    left = best_start = best_len = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1       # 跳到重复字符上次位置的右边
        last[ch] = right
        if right - left + 1 > best_len:
            best_start, best_len = left, right - left + 1
    return s[best_start:best_start + best_len]

注意判断条件里的 last[ch] >= left：如果字符上次出现的位置已经在窗口外面，就不能把左指针往回移。

第二题：二叉树的右视图

题目

返回一棵二叉树从右侧看过去能看到的节点。例如：

    1
   / \
  2   3
   \   \
    5   4

返回 [1, 3, 4]。

思路

• BFS 层序遍历：用队列逐层扫描，记录每层最后一个节点的值。
• DFS：递归时优先访问右子树，第一次到达某一层时，把当前节点加入结果，这样自然会拿到每层最右边的节点。

两种方法时间都是 O(n)，空间取决于树的高度（BFS 取决于最宽一层的宽度）。

from collections import deque

def right_view_bfs(root):
    res, q = [], deque([root] if root else [])
    while q:
        for i in range(len(q)):
            node = q.popleft()
            if i == 0:
                res.append(node.val)  # 先放右孩子，所以每层第一个就是最右边
            for child in (node.right, node.left):
                if child:
                    q.append(child)
    return res

def right_view_dfs(root):
    res = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(res):         # 第一次到达这一层
            res.append(node.val)
        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)
    dfs(root, 0)
    return res

Follow-up：打印每层的最远节点列表。这里按「每层最左和最右两端的节点」理解，层序遍历时同时记录每层的第一个和最后一个节点即可：

def level_extremes(root):
    """每层 [最左, 最右]；只有一个节点的层返回 [该节点]"""
    res, q = [], deque([root] if root else [])
    while q:
        level = [n.val for n in q]
        res.append([level[0], level[-1]] if len(level) > 1 else level)
        for _ in range(len(q)):
            node = q.popleft()
            for child in (node.left, node.right):
                if child:
                    q.append(child)
    return res

最后留了五分钟 Q&A。

总结

Google 实习的题目风格是纯算法，没有简历深挖，也没有 BQ，重点在于：

• 逻辑清晰
• 边界严谨
• 复杂度优化

面试官通常不会出一模一样的原题，很多时候会有变形，更看重你能否举一反三、条理清晰地把思路讲出来。没有运行环境，平时练习时就要养成手动 dry run 的习惯。